英文:
How does a LinkedHashMap maintain insertion order in the case of hash collisions?
问题
我了解 HashMap 的工作原理，以及在哈希冲突的情况下它会在同一个桶中形成一个链表。
我知道在 LinkedHashMap 中，它通过“before”和“after”字段来保持插入顺序，但是如果像 HashMap 中那样发生哈希冲突，它如何保持插入顺序呢？
更具体地说，数组中的值和特定桶中的值可能在不同的时间间隔内被插入，那么在检索它们时，是否会变得混乱呢？
英文:
I know how HashMap works and that in the case of hash collisions it forms a Linked List in that bucket.
I get that in a LinkedHashMap it maintains insertion order by the 'before' & 'after' fields but how would it maintain the insertion order if there are hash collisions like in a HashMap.
More specifically, the values in the array and any particular bucket could have been inserted at different time intervals, and at the time of retrieving them, wouldn't it be a mess?
答案1
得分: 2
一个 LinkedHashMap 维护了一个双向链表，遍历其所有条目。这意味着每个条目都知道在自身之前和之后插入的条目。因此，不管条目属于哪个 桶，在迭代时，你会按照它们插入的顺序获取条目。
我相信你了解 Map 的概念，它存储由键值对组成的条目。然而，在你的评论中，你错误地提到了仅值（values）。
英文:
A LinkedHashmap maintains a doubly-linked list running through all of its entries. It means that each entry knows the entry inserted before and after itself. Therefore, it doesn't matter which bucket an entry belongs to; while iterating, you get the entries in the order of their insertion.
I am sure you know the concept of Map that it stores entries consisting of a Key-Value pair. However, in your comment, you have mistakenly mentioned about values only.
答案2
得分: 0
每个条目由之前和之后的Entry对象组成。即使在哈希冲突的情况下，冲突的Entry也将具有其先前的Entry。
JVM无需按linkedList的索引或特定bucket进行遍历。它将直接使用之后或之前的Entry跳转。
static class Entry<K,V> extends HashMap.Node<K,V> {
Entry<K,V> before, after;
Entry(int hash, K key, V value, Node<K,V> next) {
super(hash, key, value, next);
}
}
英文:
Each entry is made of before and after Entry object. Even in the case of hash collision, Collided Entry will have its previous Entry.
JVM does not need to travers by index of linkedList or the particular bucket. It will directly jump using the after or before Entry.
static class Entry<K,V> extends HashMap.Node<K,V> {
Entry<K,V> before, after;
Entry(int hash, K key, V value, Node<K,V> next) {
super(hash, key, value, next);
}
}
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论