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，但假如需要优化的话，要考量详细的利用场景。

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)，提高了链表过长时的机能。