36

我读到 HashMap 具有以下实现：

main array 
   ↓
[Entry] → Entry → Entry      ← linked-list implementation
[Entry]
[Entry] → Entry
[Entry]
[null ]

因此，它有一个 Entry 对象数组。

问题：

  1. 我想知道这个数组的索引如何在 hashCode 相同但对象不同的情况下存储多个 Entry 对象。

  2. 这与LinkedHashMap实施有何不同？它的 map 的双向链表实现，但它是否像上面一样维护一个数组，它如何存储指向下一个和前一个元素的指针？

4

5 回答 5

84

HashMap 不维护插入顺序，因此它不维护任何双向链表。

LinkedHashMap 最显着的特点是它维护了键值对的插入顺序。LinkedHashMap 使用双向链表来做到这一点。

LinkedHashMap 的条目如下所示-

  static class Entry<K, V> {
     K key;
     V value;
     Entry<K,V> next;
     Entry<K,V> before, after;        //For maintaining insertion order    
     public Entry(K key, V value, Entry<K,V> next){
         this.key = key;
         this.value = value;
         this.next = next;
     }
  }

通过使用 before 和 after - 我们跟踪 LinkedHashMap 中新添加的条目，这有助于我们维护插入顺序。

Before 指的是上一个条目，after 指的是 LinkedHashMap 中的下一个条目。

LinkedHashMap

有关图表和分步说明，请参阅http://www.javamadesoeasy.com/2015/02/linkedhashmap-custom-implementation.html

谢谢..！！

于 2015-05-04T09:34:10.143 回答
53

所以，它有一个Entry对象数组。

不完全是。Entry它有一个对象链数组。HashMap.Entry对象具有next允许将对象Entry链接为链表的字段。

我想知道这个数组的索引如何Entry在 hashCode 相同但对象不同的情况下存储多个对象。

因为（如您问题中的图片所示）Entry对象是链式的。

这与LinkedHashMap实施有何不同？它的 map 的双向链表实现，但它是否像上面一样维护一个数组，它如何存储指向下一个和前一个元素的指针？

在LinkedHashMap实现中，类通过添加和字段来LinkedHashMap.Entry扩展类。这些字段用于将对象组装成一个独立的双向链表，记录插入顺序。因此，在类中，每个条目对象都位于两个不同的链中：HashMap.EntrybeforeafterLinkedHashMap.EntryLinkedHashMap

  • 有许多通过主哈希数组访问的单链接哈希链。这用于（常规）哈希图查找。

  • 有一个单独的双向链表包含所有条目对象。它以条目插入顺序保存，并在您迭代哈希图中的条目、键或值时使用。

于 2013-11-02T05:02:39.067 回答
13

看看你自己。为了将来参考，你可以谷歌：

java LinkedHashMap源码

HashMap使用 a来处理碰撞，但和LinkedList的区别在于它有一个可预测的迭代顺序，这是通过一个额外的双向链表实现的，它通常保持键的插入顺序。例外情况是重新插入键时，在这种情况下，它会回到列表中的原始位置。 HashMapLinkedHashMapLinkedHashMap

作为参考，遍历 aLinkedHashMap比遍历 a 更有效HashMap，但LinkedHashMap内存效率较低。

如果从我上面的解释中不清楚，散列过程是相同的，所以你得到了普通散列的好处，但你也得到了如上所述的迭代好处，因为你使用的是双向链表维护Entry对象的顺序，这与哈希冲突期间使用的链表无关，以防不明确。

编辑：（响应 OP 的评论）：
AHashMap由一个数组支持，其中一些插槽包含Entry对象链来处理冲突。要遍历所有 (key,value) 对，您需要遍历数组中的所有插槽，然后遍历LinkedLists; 因此，您的总时间将与容量成正比。

使用 aLinkedHashMap时，只需要遍历双向链表，因此总时间与大小成正比。

于 2013-11-02T04:39:30.057 回答
1

由于其他答案都没有真正解释如何实现这样的事情，我会试一试。

一种方法是在（键->值对的）值中包含一些对用户不可见的额外信息，这些信息对插入到哈希映射中的前一个和下一个元素的引用。好处是您仍然可以在恒定时间内删除元素，从哈希映射中删除是恒定时间，在这种情况下从链表中删除是因为您有对条目的引用。您仍然可以在恒定时间内插入，因为哈希映射插入是恒定的，链表通常不是，但在这种情况下，您可以恒定时间访问链表中的某个点，因此您可以在恒定时间内插入，最后检索是恒定时间因为您只需要为它处理结构的哈希映射部分。

请记住，像这样的数据结构并非没有成本。由于所有额外的引用，哈希图的大小将显着增加。每个主要方法都会稍微慢一些（如果它们被重复调用可能很重要）。并且数据结构的间接性（不确定这是否是一个真正的术语：P）增加了，尽管这可能没什么大不了的，因为引用保证指向哈希映射内的东西。

由于这种结构的唯一优点是它保留了顺序，因此在使用时要小心。另外，在阅读答案时请记住，我不知道这是它的实现方式，但如果给定任务，我会这样做。

在oracle 文档中有一个引用证实了我的一些猜测。

此实现与 HashMap 的不同之处在于它维护一个双向链表，该列表贯穿其所有条目。

来自同一网站的另一个相关报价。

此类提供所有可选的 Map 操作，并允许 null 元素。与 HashMap 一样，它为基本操作（添加、包含和删除）提供恒定时间性能，假设哈希函数在桶中正确地分散元素。由于维护链表的额外费用，性能可能略低于 HashMap，但有一个例外：迭代 LinkedHashMap 的集合视图所需的时间与映射的大小成正比，而不管其容量如何. HashMap 的迭代可能更昂贵，需要的时间与其容量成正比。

于 2013-11-02T04:48:23.393 回答
-1

hashCode将通过哈希函数映射到任何桶。如果发生冲突，hashCode则HashMap通过链接解决此冲突，即，它将将该值添加到链接列表中。下面是执行此操作的代码：

for (Entry<K,V> e = table[i]; e != null; e = e.next) {
392             Object k;
393             if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
394         `enter code here`        V oldValue = e.value;
395                 e.value = value;
396                 e.recordAccess(this);
397                 return oldValue;
398             }
399         }

您可以清楚地看到它遍历了链表，如果找到键，则将旧值替换为新的 else 附加到链表。

LinkedHashMap但是和之间的区别HashMap是LinkedHashMap保持插入顺序。来自文档：

这个链表定义了迭代顺序，通常是键插入映射的顺序（插入顺序）。请注意，如果将键重新插入到地图中，则插入顺序不会受到影响。（如果在调用 m.containsKey(k) 将在调用之前立即返回 true 时调用 m.put(k, v)，则将键 k 重新插入到映射 m 中）。

于 2013-11-02T04:39:02.390 回答