如何在java中使用linkedlist或array在内部实现hashmap [英] how is hashmap internally implemented in java using linkedlist or array

问题描述

如何在内部实现hashmap？我在某处读到它使用链表，而在某些地方它被称为数组。

how is hashmap internally implemented? I read somewhere that it uses linked list while at some places it is mentioned as arrays.

我尝试研究hashset的代码并找到了入口数组，然后在哪里使用了linkslist

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.

这篇关于如何在java中使用linkedlist或array在内部实现hashmap的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！