HashMap 是在 Java 内部使用 LinkedList 还是 Array 实现的? [英] Is HashMap internally implemented in Java using LinkedList or Array?

问题描述

HashMap 是如何在内部实现的?我在某处读到它使用 LinkedList 而其他地方它提到数组.

How is HashMap internally implemented? I read somewhere that it uses LinkedList while other places it mentions Arrays.

我尝试研究了 HashSet 的代码并找到了 Entry 数组.那么LinkedList用在哪里?

I tried studying the code for HashSet and found Entry array. Then where is LinkedList used?

推荐答案

基本上是这样的:

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

所以你有一个主数组，其中每个索引对应一些哈希值(mod'ed* 到数组的大小).

So you have the main array where each index corresponds to some hash value (mod'ed* to the size of the array).

然后他们每个人都将指向下一个具有相同哈希值的条目(再次mod'ed*).这就是链表的用武之地.

Then each of them will point to the next entry with the same hash value (again mod'ed*). This is where the linked-list comes in.

*:作为技术说明，在被mod'ed，但是，作为基本实现，只需修改即可.

*: As a technical note, it's first hashed with a different function before being mod'ed, but, as a basic implementation, just modding will work.

这篇关于HashMap 是在 Java 内部使用 LinkedList 还是 Array 实现的?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！