13

LinkedHashMap 本质上是 LIFO 还是 FIFO？如果我的地图是以下形式：

map.put(1,"one");
map.put(2,"two");

如果我要使用键集在地图上迭代，顺序是什么？

编辑：我想我确实混淆了两个不同的概念。让我重新表述这个问题。我使用 entryset 遇到数量的顺序是什么？谢谢你指出这一点。我不打算删除任何条目。

4

4 回答 4

14

在链接的哈希映射中，支持双向链表中的元素被添加到末尾（显然：为了保留迭代顺序），但是当元素从映射中删除时，可以从列表的任何部分中删除，这是不正确的将后备列表（以及扩展名：映射）标记为 LIFO 或 FIFO，两者都不是 - 映射中没有删除顺序的概念，因此不能为链接哈希映射中的后备列表假定删除顺序。

链接哈希映射确实保证迭代其内容（无论是键还是条目）将按照元素插入映射的顺序发生；从文档：

此实现与 HashMap 的不同之处在于它维护一个双向链表，该列表贯穿其所有条目。这个链表定义了迭代顺序，通常是键插入映射的顺序（插入顺序）。

编辑 ：

关于问题的最后一次编辑， aLinkedHashMap 保证的迭代顺序keySet()将与插入元素的顺序相同：1, 2对于问题中的示例。这与 FIFO/LIFO 无关，这些概念涉及从数据结构中删除元素的顺序，与插入元素后的迭代顺序无关。

于 2012-06-16T18:50:05.930 回答
7

引用javadocs的 LinkedHashMap是“Map 接口的哈希表和链表实现，具有可预测的迭代顺序”。所以 keySet 将根据插入的顺序返回键，本质上是一个 FIFO。

于 2012-06-16T18:48:21.223 回答
1

根据 Java 文档，如果您要遍历地图，则键集将按插入顺序排列。因此，您获得的第一个键是输入的第一个键，而不是现有键。请注意，重新插入键值对不会更改原始键位置。

于 2012-06-16T18:54:08.910 回答
1

当不使用访问顺序时（标准情况），您可以将 LHM 视为一个链表，通过键快速访问 O(1)。

在这方面，当访问顺序未使用时，它是 FIFO（查看 c-tors）。当使用访问顺序时，插入顺序无关紧要，get()因为它们重新排序条目时是否有任何操作。看看protected boolean removeEldestEntry(Map.Entry<K,V> eldest) 最年长的=FIFO。

本质上，LHM 是一个很好的双向链表，Map.Entry<Key, Value>在键上具有哈希索引。我自己从来没有像现在的 impl 那样使用 vanilla HashMap。与 LHM 相比，它几乎没有什么好处——内存占用少，但迭代非常糟糕。Java8（或 9）也许最终会修复 HashMap，希望 Doug Lea 能够推动他的实现。

于 2012-06-16T19:36:10.717 回答