内部，Hashmaps使用hashfunction查找查询的key所属的bin。每一个bins本身就是一个LinkedList。
我不明白如果这些LinkedLists可以变得很长，LinkedLists没有恒定的访问时间，而是线性访问时间，访问时间怎么可能是恒定的。
Java Collections库如何保证恒定的访问时间，即使箱子因为某种原因变得太大?内部发生了什么?Java内部做了什么来最小化这种负面影响?
每个容器中元素的平均数目由一个小常数限定。这是通过保持垃圾箱的数量至少与条目总数乘以负载因子(其默认值为0.75)一样高来维护的。
为了保持这个不变，箱子的数量随着条目的数量而增加。
下面是相关代码(Java 7):
void addEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] = new Entry<>(hash, key, value, e);
if (size++ >= threshold)
resize(2 * table.length);
}
其中size为条目数，table.length为箱子数，threshold为table.length * loadFactor。
如果您使用默认的负载因子0.75(或任何负载因子<1)，箱子的数量总是高于条目的数量，所以除非你的键类有一个非常糟糕的hashCode，否则每个箱子平均不会有超过一个条目。
我不明白如果这些链表可以变得很长，访问时间怎么可能是恒定的
HashMap不提供保证的恒定访问时间。它提供了平摊常数时间，这是另一回事:n项的总体访问平均为O(1)，但每个单独的访问可能为O(n)。
而且，只有当哈希函数是"好的"时，才能实现平摊常数时间。当哈希函数不好时(例如，返回一个常量，这是一个有效的，但非常糟糕的哈希函数)，库是无能为力的:访问时间将是线性的，无论实现试图做什么。
当多个哈希码相同时，链表将增长，对桶的数量取模。然而，由于HashMap选择质数作为其桶计数，因此链表变得非常长的最常见情况是许多哈希码实际上是相同的，而不考虑模。因此，简单地将桶的数量增加到一个更大的素数并不会减少列表的长度:它要么将列表移动到另一个桶中，要么将其保留在原来的位置，但列表的长度不会减少。
文档告诉你，如果负载系数太高会发生什么:
HashMap实例有两个影响其性能的参数:初始容量和负载因子。容量是哈希表中桶的数量，初始容量是创建哈希表时的容量。负载因子衡量的是哈希表在容量自动增加之前允许达到的满程度。当哈希表中的条目数超过负载因子和当前容量的乘积时，对哈希表进行重哈希(即重建内部数据结构)，使哈希表的桶数大约增加一倍。
此外，您可以查看源代码，其中包含大量实现注释。最重要的是:
这个映射通常作为一个binned(桶)哈希表，但是当bin变得太大时，它们被转换成treenode的bin，每个bins的结构与java.util.TreeMap中的相似。
及后续:
因为treenode的大小大约是常规节点的两倍，我们只在bin包含足够的节点以保证使用时才使用它们(参见TREEIFY_THRESHOLD)。当它们变得太小(由于移除或调整大小)时，它们被转换回普通的垃圾箱。
简而言之:
- 当单个箱子变得太大时，它们的元素被转换成树节点，你得到
O(ln(t))搜索，t是箱子的大小。所以大的箱子上悬挂着一棵二叉树。 - 当整个地图的负载系数变得很高时，垃圾箱的数量会翻倍，整个地图会被重新散列(这可能仍然会导致一些垃圾箱再次成为树垃圾箱)。
如果散列表太满，则需要重新散列。要重新散列表，需要创建另一个包含更多bucket的表，并将所有元素插入新表中。原表被丢弃
负载因子决定何时重新散列。默认值是0.75，所以当表的满率超过75%时，它会自动用两倍的桶重新散列。
为了在表中找到一个位置，计算哈希码并对桶的数量取模。这个想法是哈希函数应该随机分布对象，所以碰撞的次数应该很低，所以不应该有太多的比较。