LinkedHashMap是LIFO还是FIFO？

Question

LinkedHashMap是LIFO还是FIFO的数据结构？ 如果我的Map的形式为：

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

如果我使用keyset迭代map，那么顺序会是什么？

编辑：我想我实际上混淆了两个不同的概念。让我重新表示问题。如果我使用entryset，我会以什么顺序遇到数量？顺便感谢指出这一点。我不打算删除任何条目。

- BlahBlah

---

点赞，因为我认为负评是不应该的。 - Dancrumb

它是“最后进入”，但根据您的使用方式，可以从任何地方删除。 - Tooraj Jam

Answer 1

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

链式哈希映射所保证的是，在其内容（无论是键还是条目）上进行迭代时，会按照元素插入地图的顺序进行；来自documentation：

这种实现与HashMap不同之处在于，它维护通过所有条目的双向链接列表。该链接列表定义了迭代顺序，通常是将键插入地图的顺序（插入顺序）。

编辑：

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

- Óscar López

---

(1) LinkedHashMap 中的顺序被定义为插入顺序，因此 (2) 有关排序的概念确实存在，而且 (3) 问题中没有提到“删除顺序”，无论那是什么意思。你在编辑中添加的第二段与你的第一段相矛盾。 - user207421

@EJP LIFO 意味着当进行删除操作时，最后添加的元素将是第一个被删除的元素。FIFO 意味着当进行删除操作时，最先添加的元素将是第一个被删除的元素。因此，你可以看到，LIFO/FIFO 与删除有关，而与迭代或排序无关。OP 混淆了不同的概念，你也一样。 - Óscar López

我想我实际上混淆了两个不同的概念。让我重新表述问题。使用entryset时，我会遇到这些数量的顺序是什么？顺便说一下，感谢你指出来。我不打算删除任何条目。 - BlahBlah

@user1453077 我编辑了我的答案，迭代顺序将与插入顺序相同。 - Óscar López

答案几乎正确，除了LHM可以有访问顺序。但仍然是FIFO。 - bestsss

Answer 2

从javadocs引用的LinkedHashMap是"Map接口的哈希表和链表实现，具有可预测的迭代顺序"。因此，keySet将返回基于插入顺序的键，本质上是先进先出。

- Biju Kunjummen

Answer 3

当未使用访问顺序（标准情况）时，您可以将LHM视为具有非常快速的按键访问O（1）的链表。

在这方面，当未使用访问顺序时，它是FIFO（先进先出）（请查看c-tors）。当使用访问顺序时，如果有任何get()操作，则插入顺序不重要，因为它们会重新排序条目。请查看protected boolean removeEldestEntry(Map.Entry<K,V> eldest) eldest=FIFO。

本质上，LHM是一个很好的Map.Entry<Key, Value>双向链表，具有键的哈希索引。我自己从不使用vanilla HashMap，因为在其当前实现中，它与LHM相比几乎没有什么好处——内存占用更低，但迭代可怕。Java8（或9）可能会最终修复HashMap，希望Doug Lea会推动他的实现。

- bestsss

Answer 4

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

- user845279