hashmap的头插法和尾插法_「最完整系列」JAVA-容器篇-
HashMap⾯试最详解
前⾔
在讲技术前有必要讲⼀下这篇⽂章的由来。写java的朋友，⽆论是客户端还是服务端，HashMap基本上都最常⽤的java容器了，正因为最常⽤，所以我们需要去了解的更深，对代码优化和规范都有好处。⽹上关于 hashmap 的讲解也铺天盖地多的是，那为什么我还要写⼀篇这个呢。原因主要在于你可以看⽹上任何的⼀篇讲 hashmap 的⽂章，远远没有这篇⽂章带给你的清晰和完整，甚⾄可以让你靠近⼈家在开发hashmap 时⽤到的思维模式。
说明：以下汇总下jdk1.8以及之后版本中的 HashMap 实现。
简介
⾸先⽤⼀句话说明 HashMap 的结构：
数组+链表，即数组中存放的是指向链表的指针，当链表中数据⼤于阈值(默认为8)，⽤红⿊树代替链表。
上⾯出现了3个结构：数组、链表和红⿊树。那么下⾯依次说明各个结构在 HashMap 中的具体应⽤。
数组
HashMap 中的数组也被叫做哈希桶，本质上是⼀个 Node 类型的数组。
static class Node implements Map.Entry {        final int hash;        final K key;        V value;        Node next;        ...}
可以看到 Node 中存放着 key，value 以及⼀个 hash 值。这个 hash 值的作⽤就是为了确定指定的 key 存放在数组中的哪个桶，它的具体实现：
static final int hash(Object key) {    int h;    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);}
从这个 hash 函数中我们可以看到2点：
1. key 允许为null，为 null 时存放在数组的第⼀个桶(下标为0)中。
2. ⽤到了 key 对象的 hashCode ⽅法获取对象的 hash 值，然后运⽤了⼀些位运算计算下标。
java 中 int 4个字节，h>>>16 相当于获取 h 的⾼位部分，之后的位运算是将 key 的 hashCode 与其⾼位异或操作，相当于将⾼位和低位
综合⼀下，为了减少 hash 碰撞的记录。最终这个扰动函数计算出来的 hash 值会跟数组长度进⾏求余操作来获取 key 存放的桶下标：
// & 可以⽤来取余，i 就是计算出的数组的下标i = (n-1) & hash
为什么需要将⾼低位异或？因为hashCode()是int类型，取值范围是40多亿，只要哈希函数映射的⽐较均匀松散，碰撞⼏率是很⼩
的。但是由于HashMap的哈希桶的长度远⽐hash取值范围⼩，默认是16，所以当对hash值以桶的长度取余，以到存放该key的桶的下标时，由于取余是通过与操作完成的，会忽略hash值的⾼位。因此只有hashCode()的低位参加运算，发⽣不同的hash值，但是得到的index相同的情况的⼏率会⼤⼤增加。
链表
hash 函数总是有可能会存在冲突的，当两个不同的 key 计算的 hash 值相等时，此时它们对应数组的下标也就相等了。因此我们就需要将
数组中的元素以链表的⽅式串联起来，这就是 Node 结构存在⼀个指向下⼀个节点的 next 字段的原因。其中新建的 Node 会插⼊到链表的
尾部。
// 取⼀段 put ⽅法中插⼊到链表尾的代码Node e; K k;for (int binCount = 0; ; ++binCount) {    if ((e = p.next) == null) {        // 到达链表尾部        p.next = newNode(ha
思考⼀下为什么要插⼊到链表尾部，⽽不是头插法(插⼊到头部)呢？ 让我们来算下时间复杂度，尾插法需要遍历整个链表，时间复杂
度为O(N)，头插法只需要将数组下标中值存放成新 Node，然后将新 Node 的 next 指向旧的头，复杂度为O(1)，明明头插更快啊，为什么会变成尾插呢？答案请看扩容章节。
红⿊树
java技术专家上⾯的代码中我们还能看到⼀个常量 TREEIFY_THRESHOLD，它指代的是链表的最⼤长度，超过这个长度后链表需要被转化为红⿊树，
默认这个变量为 8。
static final int TREEIFY_THRESHOLD = 8;
什么是红⿊树？请看我之后的数据结构篇。
为什么要把长的链表转换成红⿊树呢，因为你们可以看到上⾯的插⼊操作在查的过程中⽤了⼀个 for 循环到尾部，时间复杂度是
O(n)，⽽红⿊树可以让搜索的复杂度降到O(logn)，对于数据量⼤的情况，效率下降的⽐链表慢。
下⾯是链表转换为红⿊树的过程：
final void treeifyBin(Node[] tab, int hash) {    int n, index; Node e;    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)        resize();    else if ((e = tab[in 扩容
当我们不断的往hash桶放数据，整个桶会变得越来越臃肿，操作效率⼤幅降低，这时候我们需要去给 hashmap 扩容。
假定 hashmap 的容量是 capacity，⽬前存放着 size 个元素，当 size > threshold 时，hashmap 需要扩容，threshold = capacity *
load factor。load factor 是负载因⼦，默认是 0.75。
static final float DEFAULT_LOAD_FACTOR = 0.75f;// 很多地⽅通过如下判断进⼊ resize 流程if(size > threshold) resize();
关于容量，⼤家都知道 hashmap 的默认容量是 16。你有想过为什么是16吗？这其实还是要回过头看到我们计算数组下标的代码 (n-1) & hash， n 指代容量，只要n是2的幂，那么 n-1肯定是⼀个⼆进制值全为1的数字.例如 n = 16，那么 15 的⼆进制就是 1111，1111 与其他数 & 操作后的值就是后4位本⾝的值，所以达到最终⽬的，均匀的 hash(你可以对⽐下⽤ 5，7等数跟别的数 & 的结果，碰撞⼏率明
显上升)。⽽ 16 恰巧是那个合适的默认值，不⼤不⼩。这个道理跟负载因⼦是 0.75⼀样，为啥是 0.75 呢，也是折中过后取的值，如果因⼦为1，那么允许不扩容的⼤⼩就越⼤，hash 碰撞发⽣⼏率⾼，如果⼩了，动不动就扩容也不⾏，内存消耗⼤了(我猜测 0.75 应该是专家实验统计出来的结果)。
hashmap 中还存在⼀个最⼤容量的常量，值是 2^30 次⽅，当容量到了这个级别就不会在扩容了。正常情况下，扩容时会先创建⼀个长度为原来2倍的数组，然后经过rehash 把原先的Node放进新数组中。
下⾯看下 resize 的具体过程：
final Node[] resize() {    Node[] oldTab = table;    int oldCap = (oldTab == null) ? 0 : oldTab.length;    int oldThr = threshold;    int newCap, newThr = 0;    if (
⼤家可以看到 rehash 的部分也是尾插的形式重新⽣成链表，由此它保证了 Node 的顺序依然是之前链
表的顺序，如果是头插呢，顺序就变了。顺序变了会产⽣什么样的问题呢：可能会导致 resize 死循环。
尾插法：原链表 1->2->3->4rehash后链表可能是      1->2->3    4头插法：原链表    1->2->3->4rehash后链表可能是    3->2->1    4
头插法中死循环是怎么发⽣的？
假设现在是头插法有2个线程，线程A resize 执⾏遍历到了1，然后线程B执⾏，执⾏完了整个 resize，链表变成了 3->2->1。然后线程A
回来继续执⾏，那么它在rehash 1后继续rehash 2，这时候发现2的next是1，这就形成了⼀个环，所以会⼀直循环下去直到资源耗尽。⽽尾插法很好的避免的这个问题，所以即使牺牲了⼀点点搜索的性能(也没有差很多)，解决了这个多线程的问题。
由此你也能看到，hashmap 是线程不安全的。想要⽤线程安全的 hashmap 就⽤ ConcurrentHashMap，它给很多操作都加了同步锁，具体细节之后请关注多线程篇。