在 hashmap 中，向桶的内部链表添加新元素总是在最后.为什么? [英] In a hashmap, the addition of a new element to the internal linked list of a bucket is always at the end. Why?

问题描述

在哈希图中，当我们有相同的哈希码时，我们将对象作为链接列表插入，然后将其转换为 TreeNode.每个具有相同哈希码的新对象都被添加到所附链表的最后一个.所以，我的问题是为什么我们不添加新元素作为附加到存储桶的内部链表的第一个元素?为什么要遍历到最后一个元素，然后再添加新元素.

In a hashmap, when we have the same hashcodes, we insert objects as a linked list which are later converted to TreeNode. Every New object with the same hashcode is added to the last of the linked list attached. So, my question here is why don't we add the new element as first element of the internal linked list attached to the bucket? Why do we traverse till the last element, and then add the new element.

链接列表花费的时间:

在开始处插入新元素 = O(1)

Insert New element at start = O(1)

在末尾插入新元素 = O(n)

Insert New element at end = O(n)

---

一个可能的答案可能是，因为 hashmap 不是线程安全的，从单个位置并发读取和写入元素会导致异常.例如，有两个事务:

---

A probable answer could be, since, hashmap is not thread-safe, concurrent reading and writing of elements, from single position can lead to anomalies. For example, There are two transactions:

T1 -- 将新对象添加到映射中，哈希图中已存在哈希码.

T1 -- adding of new object to the map having a hashcode already present in the hashmap.

T2 -- 从映射中读取新对象，哈希映射中已经存在一个哈希码.

T2 -- reading of new object from the map, again having a hashcode already present in the hashmap.

当这两个事务同时发生，并且我们开始将新元素添加到开头而不是最后一个位置时，由于在第一个位置进行了更改，读取操作可能会受到影响的可能性很小.

When these two transactions take place simultaneously, and we start adding the new elements to the start instead of last place, there might be a slight probability that reading operation gets affected, due to changes being made at the first position.

如果有人对此有更好的见解，请发表评论.

If anyone could have a better insight on this,please comment.

推荐答案

因为当哈希码相同时，您不能只添加元素.当哈希码相同时，它必须检查每个链表节点中键的equals.因此，它需要遍历整个链表来检查是否已经存在任何相等的键.

Because you can't just add the element when the hash code is the same. When the hash code is the same, it has to check equals on the key in each linked list node. So, it needs to traverse the whole linked list to check if there is any equal key already present.

这篇关于在 hashmap 中，向桶的内部链表添加新元素总是在最后.为什么?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！