写在前面
HashMap与ConcurrentHashMap在Java开发中作为k-v容器使用频率颇高，在面试中也常见二者身影，其重要性不言而喻。但如果只是说因为应用频率高所以重要，那么可谓说是低估了这两个类型的地位。
HashMap与ConcurrentHashMap之所以重要，更多是因为二者的设计与实现上广泛涉及到了Java核心思想与各类奇技淫巧，能理解透彻这两个类的人自然代码水平不会太差。
可以说吃透HashMap和其并发类型，就是精通了Java代码层的增删改查，入门了高并发。
阅读本文需具有一定《数据结构》知识基础。
本文持续更新，优先级以非经典细节为高（经典细节指扩容、红黑树链表转化等）
HashMap的实现
1. 数据结构
- HashMap的主要数据结构包括：位桶（table）、链表、红黑树。
- 元素以Entry类型节点的形式封装，Entry包含hash, key, value, next四大属性。
- 节点元素按照具体的hash存放在table中，通过向下挂靠节点来解决hash冲突，形成链表或红黑树。
2. hash()与Object.hashCode()
- HashMap并不直接使用key的hashcode，而是通过内部的混淆函数hash()对hashcode处理并设置为节点的hash。混淆函数hash()的设计可谓是极其巧妙：
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
- hashcode的本质是一个int，在场景下我们不关注int的大小，而关注它包含的信息，所以我们可以把它看作一个32位的二进制数（这也是它在内存下本身的样子）。我们不妨设想一下如果采用原本的hashcode去作为节点的hash去做插入table的操作：对于大多数的场景，table的长度并不大，大约是16-128，换算成二进制长度是4-7位，对于插入table的取模运算其实只关注hash的后几位，这就意味着我们有25-28位的信息丢失了，自然而然出现hash冲突的概率就会上升，存放数据的位置对应链表的长度（或红黑树的深度）就会增加，结果则是整体的查询效率下降。
- HashMap给出的处理冲突的方式是将hashcode的高低位混合（高位指前16位，低位指后16位）。先将hashcode无符号右移16位，让高位与原来的低位对其，再做异或运算，最大程度提高低位的混淆度，使低位也融合高位的信息，减小hash碰撞的可能性。
- 为什么选取异或（^）作为融合操作，与（&）和或（｜）为什么不行？我们认为hashCode()输出结果0和1具有随机性，在一位上出现0和1的概率是大致均等的。而与和或分别具有1倾向性和0倾向性。假设1和0出现的概率各是0.5的话，那么与操作有0.75的概率输出1，或运算则有0.75的概率输出0，异或运算则均等输出0和1，从提高混沌度的角度来考虑，异或显然是更好的操作。并且，在移位之后，高位会被全0代替，只有异或操作仍然可以维持相等的混淆度（0和1互换），尤其是或运算，会导致高位信息的丢失。
3. 内部判断key相等的机制
- HashMap不支持相同key的元素插入，对相同key的情况，会做出无视处理。但也因此，为了支持key唯一性，HashMap内部需要提供检测key是否相等的手段。HashMap内部判断是否相等的方法如下：
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
break;
- &&和｜｜是短路运算符，只要判断出true或者false就直接跳过后面的布尔语句，从而达到提升效率的手段，关于短路运算符，可参考我的另一篇文章。
- 在这段代码里，判断相等被细化成了三个流程：判断哈希是否相等、判断引用是否相等、判断空值、执行equals()方法。这样去划分的主要原因是，equals()的执行相对昂贵，譬如对于两个集合类来说，equals()方法需要遍历其中所有的元素，开销很大，需要设计程序尽可能避免equals()方法被调用。hash相等是两个对象严格相等的必要不充分条件，hash如果不等，那么这两个对象一定不相等，并且从概率上来讲，判断hash是否相等能解决大部分对象是否相等的问题，实际执行到equals相等的可能性非常之小。这样一来，判断是否相等的语句也被优化到了一个平均执行时间可以忽略不计的程度。
4. size被设置为2的整次幂
- size指的是table的长度，在HashMap中，size被强制要求设置成2的整次数幂。
- 2的整次幂作为除数时，可以被位运算优化，大幅提高执行效率。
- 在进行table扩容的时候，一半节点的偏移量恰好就是原size。