HashMap是否使用LinkedList或Array在Java内部实现？

Question

HashMap在内部如何实现？我读到某处使用LinkedList，而其他地方提到了Arrays。

我尝试研究HashSet的代码并发现Entry数组。然后在哪里使用LinkedList？

Answer 1

基本上看起来像这样：

 this is the main array
   ↓
[Entry] → Entry → Entry      ← here is the linked-list
[Entry]
[Entry] → Entry
[Entry]
[null ]
[null ]

因此，您拥有主数组，其中每个索引对应于某个哈希值（mod ed *对应于数组的大小。

然后，它们中的每一个都将指向具有相同散列值（再次为mod'ed *）的下一个条目。这是链接列表的来源。

*：作为技术说明，在it's first hashed with a different function之前先添加mod，但是，作为基本实现，只需进行修改即可。

Answer 2

每个HashMap具有一个数组，并且在该数组中，每个Entry根据其键的哈希码（例如int position = entry.getKey().hashCode() % array.length）放置在一个位置。 Entry的存储位置称为bucket。

[如果有多个Entry最终出现在同一个存储桶中，则这些条目将合并到一个LinkedList中（另请参见@Dukeling的答案）。因此是存储桶的隐喻：每个数组索引都是一个“存储桶”，您可以在其中存储所有匹配的键。

您必须为存储桶使用数组，以实现所需的随机访问性能。在存储桶中，无论如何，您都必须遍历所有元素以找到所需的键，因此可以使用LinkedList，因为附加起来更容易（不需要调整大小）。这也表明需要一个良好的散列函数，因为如果所有键仅散列为几个值，您将需要很长的LinkedList来搜索，并且会有很多（快速访问）空存储桶。

Answer 3

HashMap具有HashMap.Entry对象的数组：

Answer 4

HashMap在内部使用Entry来存储键值对。条目为LinkedList类型。