java HashMap 内部使用 LinkedList
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/15768695/
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
HashMap uses LinkedList internally
提问by Learner
public V get(Object key) {
if (key == null)
return getForNullKey();
int hash = hash(key.hashCode());
for (Entry<K,V> e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
return e.value;
}
return null;
}
What I knew is, if you want to get a object from HashMap, first of all it searches the hash bucket based on hashcode/hash value and then iterates through the LinkedListin that hashbucket(suppose the diff objects have same hash code, thus in the same hash bucket).
我所知道的是，如果你想从中获取一个对象HashMap，首先它会根据哈希码/哈希值搜索哈希桶，然后在该哈希桶中迭代LinkedList（假设 diff 对象具有相同的哈希码，因此在相同的哈希桶）。
But after looking at the code above, I am not able to understand when it iterates through the LinekedList(and where is the LinkedList)
但是在查看上面的代码之后，我无法理解它何时遍历 LinekedList（以及 LinkedList 在哪里）
回答by Jon Skeet
The bucket isthe linked list, effectively. The tablearray is an array of Entryelements, and each Entryis a linked list, in that each entry knows about the next one in the list, until you reach the end when the nextreference is null. The forloop you've shown iterates over the linked list.
存储桶是有效的链表。该table数组是一个Entry元素数组，每个元素Entry都是一个链表，因为每个条目都知道列表中的下一个，直到next引用为空时到达末尾。在for循环中，您已经证明在链表迭代。
It's not a LinkedListas in a java.util.LinkedList- it's a separate (simpler) implementation just for the map.
这不是一个LinkedList在一个java.util.LinkedList-它是一个独立的（简单）的实施只是地图。
回答by Marek Piechut
It does use linked list, but not java.util.LinkedListclass.
它确实使用链表，但不使用java.util.LinkedList类。
Basically e.nextis something you're looking for.
Each entry has a reference to next entry in bucket - it's a linked list implementation.
基本上e.next是你正在寻找的东西。每个条目都有一个对存储桶中下一个条目的引用——它是一个链表实现。
回答by Vignesh T I
e.nextis what you're looking for. Each entry has a reference to next entry in the bucket; it's a linked list implementation.
e.next就是你要找的。每个条目都有一个对桶中下一个条目的引用；它是一个链表实现。
回答by Uts
The bucket is linkedlist.
table is an array which stores address of first entry(linkedlist) at an element of array.
Say at position0 in table array, two entry object needs to be stored then table[0] will store address of entry1(linkedlist) and entry1 will store address of entry2. For loops helps iterate through these entry objects.table[0] --> entry1 --> entry2 --> null // Hence output is entry2 of get().
存储桶是链表。
table 是一个数组，它将第一个条目（链表）的地址存储在数组的元素中。
说在表数组的位置0，需要存储两个条目对象，然后表[0]将存储条目1（链表）的地址，条目1将存储条目2的地址。For 循环有助于遍历这些入口对象。table[0] --> entry1 --> entry2 --> null // Hence output is entry2 of get().
But the world has changed since Java 8 as tree is used to store entry object.
但是自从 Java 8 以来世界发生了变化，因为树被用来存储条目对象。
