HashMap 是在 Java 内部使用 LinkedList 还是 Array 实现的？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/18992101/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Is HashMap internally implemented in Java using LinkedList or Array?
提问by dexterousashish
How is HashMapinternally implemented? I read somewhere that it uses LinkedListwhile other places it mentions Arrays.
HashMap内部如何实施？我在某个地方读到了它使用的内容，LinkedList而其他地方则提到了数组。
I tried studying the code for HashSetand found Entryarray. Then where is LinkedListused?
我尝试研究代码HashSet并找到了Entry数组。那么在哪里LinkedList使用呢？
采纳答案by Bernhard Barker
It basically looks like this:
它基本上是这样的：
this is the main array
↓
[Entry] → Entry → Entry ← here is the linked-list
[Entry]
[Entry] → Entry
[Entry]
[null ]
[null ]
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 functionbefore being mod'ed, but, as a basic implementation, just modding will work.
回答by piet.t
Each HashMaphas an Array and in that Array it places each Entryin a position according to its key's hash code (e.g. int position = entry.getKey().hashCode() % array.length). The position where an Entryis stored is called a bucket.
每个HashMap都有一个 Array 并且在该 Array 中，它Entry根据其键的哈希码（例如int position = entry.getKey().hashCode() % array.length）将每个放置在一个位置。Entry存储an 的位置称为bucket。
If more than one Entryends up in the same bucket, those Entries are combined in a LinkedList(also see @Dukeling's answer). Thus the bucket metaphor: each Array index is a "bucket" where you dump in all matching keys.
如果Entry在同一个存储桶中结束了多个条目，则这些条目将合并为一个LinkedList（另请参阅 @Dukeling 的回答）。因此，桶比喻：每个数组索引都是一个“桶”，您可以在其中转储所有匹配的键。
You have to use an Array for the buckets in order to achieve the desired constant timeperformance for random access. Within a bucket you have to traverse all elements to find the desired key anyways, so you can use a LinkedListas it is easier to append to (no resize needed).
您必须为存储桶使用 Array 以实现随机访问所需的恒定时间性能。在一个存储桶中，您必须遍历所有元素以找到所需的键，因此您可以使用 a ，LinkedList因为它更容易附加（无需调整大小）。
This also shows the need for a good hash function, because if all keys hash to only a few values you will get long LinkedLists to search and a lot of (fast to access) empty buckets.
这也表明需要一个好的散列函数，因为如果所有键散列到只有几个值，你将得到很长的LinkedLists 来搜索和很多（快速访问）空桶。
回答by piet.t
HashMap has an array of HashMap.Entry objects :
HashMap 有一个 HashMap.Entry 对象数组：
/**
* The table, resized as necessary. Length MUST Always be a power of two.
*/
transient Entry<K,V>[] table;
We can say that Entry is a one-way linked list (such HashMap.Entry linkage is called "Bucket") but it is not actually a java.util.LinkedList.
我们可以说 Entry 是一个单向链表（这种 HashMap.Entry 链接被称为“Bucket”）但它实际上并不是一个 java.util.LinkedList。
See for yourself :
你自己看 ：
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next;
int hash;
/**
* Creates new entry.
*/
Entry(int h, K k, V v, Entry<K,V> n) {
value = v;
next = n;
key = k;
hash = h;
}
public final K getKey() {
return key;
}
public final V getValue() {
return value;
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
public final boolean equals(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry e = (Map.Entry)o;
Object k1 = getKey();
Object k2 = e.getKey();
if (k1 == k2 || (k1 != null && k1.equals(k2))) {
Object v1 = getValue();
Object v2 = e.getValue();
if (v1 == v2 || (v1 != null && v1.equals(v2)))
return true;
}
return false;
}
public final int hashCode() {
return (key==null ? 0 : key.hashCode()) ^
(value==null ? 0 : value.hashCode());
}
public final String toString() {
return getKey() + "=" + getValue();
}
/**
* This method is invoked whenever the value in an entry is
* overwritten by an invocation of put(k,v) for a key k that's already
* in the HashMap.
*/
void recordAccess(HashMap<K,V> m) {
}
/**
* This method is invoked whenever the entry is
* removed from the table.
*/
void recordRemoval(HashMap<K,V> m) {
}
}
回答by Ankit Mittal
HashMap internally uses Entry for storing key-value pair. Entry is of LinkedList type.
HashMap 内部使用 Entry 来存储键值对。条目是 LinkedList 类型。
Entry contains following ->
K key,
V value and
Entry next > i.e. next entry on that location of bucket.
条目包含以下 ->
K键，
V 值和
下一个条目 > 即存储桶该位置的下一个条目。
static class Entry<K, V> {
K key;
V value;
Entry<K,V> next;
public Entry(K key, V value, Entry<K,V> next){
this.key = key;
this.value = value;
this.next = next;
}
}
HashMap diagram -
HashMap图——
From : http://www.javamadesoeasy.com/2015/02/hashmap-custom-implementation.html
来自：http: //www.javamadesoeasy.com/2015/02/hashmap-custom-implementation.html
