ハッシュマップのバケットは正確には何ですか？

Question

最近、インタビューでハッシュマップのバケツはどういうものなのですか？それは配列かarraylistか何であるかどうか？

私は混乱しました。私は、ハッシュマップが配列によってサポートされていることを知っています。だから私は、バケットは、最初に16の容量のハッシュコードを格納する配列であり、リンクされたリストはスタートポインタを持っていると言うことができますか？

私はハッシュマップが内部的にどのように動作するのか知っていますが、ちょうどデータ構造の点でバケツが何であるかを知りたかっただけです。

Answer 1

いいえ、バケットは、あなたが参照している配列の各要素です。以前のJavaバージョンでは、各バケットにマップエントリのリンクリストが含まれていました。新しいJavaバージョンでは、各バケットにはツリー構造のエントリまたはリンクされたエントリのリストが含まれています。 Javaの8で実装Notesから

：

/* 
* Implementation notes. 
* 
* This map usually acts as a binned (bucketed) hash table, but 
* when bins get too large, they are transformed into bins of 
* TreeNodes, each structured similarly to those in 
* java.util.TreeMap. Most methods try to use normal bins, but 
* relay to TreeNode methods when applicable (simply by checking 
* instanceof a node). Bins of TreeNodes may be traversed and 
* used like any others, but additionally support faster lookup 
* when overpopulated. However, since the vast majority of bins in 
* normal use are not overpopulated, checking for existence of 
* tree bins may be delayed in the course of table methods. 
... 

Answer 2

私は、これはあなたがよくハッシュマップの実装を理解するのを助けることができる願っています。

Answer 3

バケットは基本的に、オペレーティングシステムのページングアルゴリズムで使用されているデータ構造です。非常にLaymans言語になること。特定のハッシュコードを表す

オブジェクトは、そのバケット内に格納されている。（基本的には、バケットの用語で表されるハッシュコード値にリンクされたリストデータ構造のヘッダを考慮することができる）

参照のオブジェクトがリンクリストに格納されている場合、そのヘッダーはハッシュコードの値を表します。

JVMがそれらを作成し、サイズは、JVMによって割り当てられるメモリによって異なります。

Answer 4

バケット正確にはは、ノードの配列です。したがって、単一バケットはjava.util.HashMap.Nodeクラスのインスタンスです。各ノードはLinkedListに似たデータ構造ですが、TreeMap（Java 8以降）のように、HashMapはパフォーマンス上の方が良いと判断します。バケットをLinkedListまたはTreeMapとして保持します。 TreeMapは、多くのエントリが単一のバケットに配置されるときに、うまく設計されていないhashCode（）関数の場合にのみ選択されます。 バケットがHashMapの中でどのように見えるかを参照してください：

/** 
    * The table, initialized on first use, and resized as 
    * necessary. When allocated, length is always a power of two. 
    * (We also tolerate length zero in some operations to allow 
    * bootstrapping mechanics that are currently not needed.) 
    */ 
    transient Node<K,V>[] table;