关于HashMap的一些疑问

Question

HashMap以非常简单的方式实现，但它需要一个天才来理解它是如何实现的。所以，我已阅读了关于java文档中的HashMap。我有一个关于HashMap一些小问题：

1. 我知道HashMap默认容量为16。Java文档，他们给默认的初始容量 - 必须是二的幂。。这背后的任何具体原因？
2. 我知道一点点如何HashMap基于HashCode，Bucket和LinkedList如果我没有错。那么如何增加HashMap的尺寸。我的意思是如何管理桶大小和LinkedList大小。
3. 这可能是个愚蠢的问题。当我们在HashMap中添加新元素时，在HashCode的基础上，它直接访问那个特定的存储桶而不像在LinkedList中那样旅行。我对吗？而其他的一点是，它增加了元素而不是尾巴。这是什么原因。在桶内存在LinkedList的头部添加新元素以避免尾部遍历。我的想法是否正确？

Answer 1

1. 使用的两个大国，简化实施和提高其性能。
   例如要找到一个哈希码可以使用哈希&（SIZE -1）水桶代替ABS（散）％SIZE

2. ，直到你知道你将如何HashMap的工作原理完全不能够回答这个问题。如果地图的大小超过由负载因子（例如，如果加载因子是.75，它将在填充75％后重新调整地图大小。与ArrayList等其他集合类相似，Java HashMap通过创建一个尺寸为前一个大小HashMap的两倍的新存储区阵列来重新调整大小，然后开始将每个旧元素放入新的存储区阵列中。这个过程被称为重新哈希，因为它也应用哈希函数来查找新的存储桶位置。

3. 我们每一个新的元素存储在链表的头，以避免尾部横动，因此在调整中链表对象的整个序列时被逆转，在此期间，有无限循环的机会。

在这里阅读更多：

• http://java.dzone.com/articles/hashmap-internal
• http://javarevisited.blogspot.in/2011/02/how-hashmap-works-in-java.html

Answer 2

1. 我会假设，两个规定的权力是有加快采摘桶。如果你有16个桶和一个578123的索引，你可以使用一个简单的AND来选择一个桶，而不必计算578123 mod 16，这是较慢的。

2. HashMap有一个加载因子，默认为0.75。如果对象的数量>桶的数量*加载因子，HashMap的容量会增加以保持性能。我会认为它只是将桶的数量加倍并重新分配所有元素。

3. 对不起，我不知道我是否正确理解这个问题。

Answer 3

1. 之所以提出的容量的2的幂是（我认为）主要是为了简化代码。性能优势很小，但几乎可以忽略不计。

2. 它是这样的：当您尝试添加新条目

   • 一个HashMap扩大。它发生（粗略地说）当map.size() * load_factor > array.length。 （请参阅代码以了解详细信息。）

   • 当展开HashMap时，数组的大小加倍。有一个硬限制...由Java中的数组大小所强加。之后，HasMap的数组不会扩展。 （相反，你只是得到更长和更长的哈希链......）

   • 没有做任何事情来管理单个哈希链的长度。相反，当HashMap展开时，每个旧链中的条目都会移至展开表中的相应链中。 （至少在最近实现中，每个链节点保持为条目缓存散列值，所以不需要表膨胀期间重新评估散列函数。）

3. 基本上，是的是。新的条目被添加到每个哈希链的开始，因为这是最有效的（时间和空间）来做到这一点。由于哈希链中元素的顺序不代表任何内容，所以在链的尾部插入新条目没有意义。这也意味着在典型的HashMap实现中，展开表反转哈希链条目的顺序。

---

注意，实际行为和HashMap实际实施细则对Java的不同版本不同。唯一确定的方法是阅读您正在使用的Java版本的源代码。