Java Hashmap 尾部遍历

Question

在Java Hashmap中，“tail traversing”是什么意思？Java会反转有多个元素的（链表）桶。这种反转操作是为了避免“tail traversing”以及将元素添加到头部。我无法理解这个概念。

- Dhananjayan Santhanakrishnan

---

你在谈论哪种 Hashmap 的实现？ - Ted Hopp

我能找到的“tail traversing”或“tail traversal”术语的所有用法似乎都可以追溯到一些可疑的博客文章。没有官方来源使用这个术语。源代码或文档中也没有任何关于它的说明。我建议不要使用这个术语。 - user2357112

TedHopp，我在谈论哈希映射耗尽空间并尝试将其大小加倍时可能发生的竞态条件。 - Dhananjayan Santhanakrishnan

@user2357112 那这背后的机制是什么？还有其他的工作方式吗？ - Dhananjayan Santhanakrishnan

Answer 1

我来到这个博客是为了寻找关于尾遍历的答案，现在我有所领悟。

Dhananjayan，这基本上意味着尾遍历是链表中的一个概念。我将试着通过例子来解释。 假设您想要将以下元素添加到单向链表中： 23, 65, 44, 12, 90

好的，现在您已经添加了5个元素。因此，在一段时间后，您需要添加一个新元素10。如果我们的算法在链表末尾添加元素，则必须遍历这五个元素才能找到尾巴，对于长度较长的链表来说开销可能很大。因此，一种有效的方法是将新元素添加到头部而不是尾部，并将头指针更改为指向新头。因此，在这种情况下，当您添加一个新元素10时，链表将如下所示 10, 23, 65, 44, 12, 90

正如您所看到的，这是一种非常高效的方法。

现在我回答你的第二个问题(他们说的反转是什么意思？) 因此，在哈希映射中，当它们重新调整大小/重新哈希时，它们从链表中的头开始提取元素并制作一个新的链接列表，并按顺序添加后续元素，因此每次迭代的结果如下： 10 23 10 65 23 10 44 65 23 10 12 44 65 23 10 90 12 44 65 23 10

所以这就是添加新元素到头部的结果。 简而言之，这是一种后进先出（LIFO）结构。

菲利普

- Philip George

---

Philip，你能解释一下为什么将新元素放在头部是更好的优化吗？因为总有一天我可能需要访问尾部的值，例如在10-23-65-44-12-90中，我不必总是需要调用 get() 方法获取值为 10 的节点。我总有一天需要 90，这意味着我无论如何都要去到尾部。 此外，为什么要翻转链表？这是否增加了效率？我可以始终按相同顺序（未翻转）从一个链表复制到另一个链表并保持相同的效率。 - Asif

他们正在将新元素放在链表头部，因为如果我们在尾部添加元素(像队列一样)，那么我们必须遍历整个链表来找到尾巴，这是浪费时间的，而我们可以把它放在头部并走人。在算法术语中，将元素添加到结尾的效率为O(n)，添加到头部的效率为O(1)。是的，也许有一天你需要访问第90个元素，如果你认为添加到头部会节省你的时间，那如果我们需要第10或12个呢？所以我的观点是，对于在线性列表中搜索元素，你必须全部遍历，其时间复杂度为O(n)。 - Philip George

Mustaffa，续...所以他们无法在搜索中保存任何内容。所以他们想：“我们还是增加插入的效率吧。”您可能知道时间局部性，它说最后使用的变量有很高的再次使用机会。所以有很大的机会10将在不久的将来被使用（只是猜测，没有官方文档说明）。复制链接列表行不通，因为当我们调整大小时，哈希值必须重新计算，并且这些元素很可能分散到不同的存储桶中。对于一个简短的问题，解释得有点长，我知道！... - Philip George

谢谢Philip - 你的解释和http://mailinator.blogspot.hu/2009/06/beautiful-race-condition.html让它非常清晰明了。 - Asif

@PhilipGeorge 为什么我们需要在插入节点时遍历链表？ - Dhiraj

@PhilipGeorge 单向链表在平均和最坏情况下添加元素的时间复杂度为O(1)。 - Dhiraj

Answer 2

回答Sufian的问题。是的，对于遍历，我们需要遍历整个链表。但是这个线程仅与哈希冲突解决有关。解决哈希冲突的方法之一是重新构造存储在桶中的整个链表。因此，哈希映射从旧链表创建一个新的链表。而这种尾部遍历仅在重建期间发生。

- sarbajit

Answer 3

Philiph在上面的回答中解释了什么是尾部遍历以及为什么会发生反转。在Java HashMap中，当元素被插入时，它会进行尾部遍历，以通过对每个单独元素执行equals（）操作来检查链接列表中是否存在重复项。我看到很多人主张在HashMap中添加元素时将其添加到头部具有优势，但如果您已经进行了尾部遍历，那么为什么不在找不到匹配项并且从尾部击中空链接时将其添加到尾部呢？对我来说，在头部添加元素没有任何优势，因为它需要进行尾部遍历以检查键是否已经存在。因此，我认为仅将元素添加到头部的唯一原因是像Philiph所提到的那样的时间局部性。这是否会影响到它被添加到头部？因为您访问最后插入的元素是不确定的。

- Naveen

Answer 4

在 HashMap 中，即使特定索引处存在链接列表以检查键是否匹配，我们仍然需要遍历该链表。

for (Entry<K,V> e = table[i]; e != null; e = e.next) {
    ......................
}

即使在顶部添加新条目，它如何避免尾遍历，因为我们仍然需要遍历以进行键检查？ 最后，在检查后，如果我们找不到相同的键，则可以将新条目添加到末尾。

- user3769931