HashMap是常考点，而一般不问List的几个实现类(偏简单)。以下基于JDK1.8.0_102分析。

内部存储

HashMap的内部存储是一个数组（bucket），数组的元素Node实现了是Map.Entry接口(hash, key, value, next)，next非空时指向定位相同的另一个Entry，如图：

容量(capacity)和负载因子(loadFactor)

简单的说，capacity就是bucket的大小，loadFactor就是bucket填满程度的最大比例。当bucket中的entries的数目(而不是已占用的位置数)大于capacity*loadFactor时就需要扩容，调整bucket的大小为当前的2倍。同时，初始化容量的大小也是2的次幂（大于等于设定容量的最小次幂），则bucket的大小在扩容前后都将是2的次幂（非常重要，resize时能带来极大便利）。

Tips:
默认的capacity为16，loadFactor为0.75，但如果需要优化的话，要考量具体的使用场景。

• 如果对迭代性能要求高，不要把capacity设置过大，也不要把loadFactor设置过小，否则会导致bucket中的空位置过多，浪费性能
• 如果对随机访问的性能要求很高的话，不要把loadFactor设置的过大，否则会导致访问时频繁碰撞，时间复杂度向O(n)退化
• 如果数据增长很快的话，或数据规模可预知，可以在创建HashMap时主动设置capacity

hash与定位

作为API的设计者，不能假定用户实现了良好的hashCode方法，所以通常会对hashCode再计算一次hash：

static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

hashCode方法

注意key.hashCode()的多态用法。重点是hash方法。

hash方法的实现和定位

前面已经说过，在get和put计算下标时，先对hashCode进行hash操作，然后再通过hash值进一步计算下标，如下图所示：

回顾hash方法的源码可知，hash方法大概的作用就是：高16bit不变，低16bit和高16bit做了一个异或。

javadoc这样说：

Computes key.hashCode() and spreads (XORs) higher bits of hash to lower. Because the table uses power-of-two masking, sets of hashes that vary only in bits above the current mask will always collide. (Among known examples are sets of Float keys holding consecutive whole numbers in small tables.) So we apply a transform that spreads the impact of higher bits downward. There is a tradeoff between speed, utility, and quality of bit-spreading. Because many common sets of hashes are already reasonably distributed (so don’t benefit from spreading), and because we use trees to handle large sets of collisions in bins, we just XOR some shifted bits in the cheapest possible way to reduce systematic lossage, as well as to incorporate impact of the highest bits that would otherwise never be used in index calculations because of table bounds.

在设计hash函数时，因为目前的table长度n为2的次幂，所以计算下标的时候，可使用按位与&代替取模%：

(n - 1) & hash

设计者认为这方法很容易发生碰撞。为什么这么说呢？不妨思考一下，在n – 1为15(0×1111)时，散列真正生效的只是低4bit的有效位，当然容易碰撞了。

因此，设计者想了一个顾全大局的方法(综合考虑了速度、作用、质量)，就是把高16bit和低16bit异或了一下。设计者还解释到因为现在大多数的hashCode的分布已经很不错了，就算是发生了碰撞也用O(logn)的tree去做了。仅仅异或一下，既减少了系统的开销，也不会造成因为高位没有参与下标的计算(table长度比较小)时，引起的碰撞。

但我没有理解为什么“很”容易发生碰撞。如此设计的话，hash的分布是均匀的，且极其简单；将高16bit与低16bit异或之后，hash的分布变的复杂一些，更“接近”随机，但仍然是均匀的。估计作者是从实际使用的角度出发，因为一般情况下，key的分布也符合“局部性原理”，低比特位相同的概率大于异或后仍然相同的概率，从而降低了碰撞的概率。

碰撞

调用put方法时，尽管我们设法避免碰撞以提高HashMap的性能，还是可能发生碰撞。据说碰撞率还挺高，平均加载率到10%时就会开始碰撞。我们使用开放散列法来处理碰撞节点。

将旧entry的引用赋值给新entry的next属性，改将新entry放在该位置——即在该位置上存储一个链表，冲突节点从链表头部插入，这样插入新entry时不需要遍历链表，时间复杂度为O(1)。但如果链表过长，查询性能仍将退化到O(n)。Java8中对链表长度增加了一个阈值，超过阈值链表将转化为红黑树，查询时间复杂度降为O(logn)，提高了链表过长时的性能。

调用get方法时，定位到该位置，再遍历红黑树，比较key值找到所需元素：