Hashmap的实现原理

HashMap是一个数组链表，当一个key/Value对被加入时，首先会通过对key的Hash算法定位出这个键值对要放入的桶（数组的索引），然后就把它插到相应桶中。

如果这个桶中已经有元素了，那么发生了哈希碰撞，这样会在这个桶中形成一个链表,如果链表太长的话，hashmap的查询时间复杂度由O(1)将会退化为O(n)。

一般来说，避免查询复杂度退化为O(n),在有数据要插入HashMap时，都会检查容量有没有超过设定的thredhold，如果超过，需要增大HashMap的尺寸，一般扩容为2倍（需要思考一个问题：为什么每次扩容都是2倍）,扩容的过程叫做重hash。

不安全体现在俩方面

出现死循环

死循环问题发生在 JDK 1.7 版本中，hashmap出现死循环的必要条件有俩个

• 出现并发
• 出现重hash操作
• 头节点插入

先看一下jdk 1.7中的rehash的代码，如下

void resize(int newCapacity)
{
    Entry[] oldTable = table;
    int oldCapacity = oldTable.length;
    ......
    //创建一个新的Hash Table
    Entry[] newTable = new Entry[newCapacity];
    //将Old Hash Table上的数据迁移到New Hash Table上
    transfer(newTable);
    table = newTable;
    threshold = (int)(newCapacity * loadFactor);
}
//迁移操作：将原数组的key/value迁移到新数组上
void transfer(Entry[] newTable)
{
    //旧数组
    Entry[] src = table;
   //新数组的容量
    int newCapacity = newTable.length;
    //下面这段代码的意思是：
    // 遍历旧数组
    for (int j = 0; j < src.length; j++) {
        //e为数组链接的头节点
        Entry<K,V> e = src[j];
        if (e != null) {
            //释放原数组
            src[j] = null;
            //开始遍历该桶下的链表
            do {
                //元素组中的当前节点的下一个节点
                Entry<K,V> next = e.next;
                //计算元素e在新数组上的索引(桶)
                int i = indexFor(e.hash, newCapacity);
                e.next = newTable[i];
                newTable[i] = e;
                e = next;
            } while (e != null);
        }
    }
}

其实这段代码中的最重要的俩行代码就是下面这俩行：表示的是将节点e插入到新数组的索引i上的链表中。

e.next = newTable[i];
newTable[i] = e;

newTable[i]表示的是新数组索引i的头节点，而e.next = newTable[i]表示的是e节点后置节点连接到索引i的头节点，然后newTable[i] = e重新将新数组索引i的头节点指向了e节点，可以发现，插入一个新节点时是使用的头节点插入方式,其实新增节点使用头节点插入的这种方式是出现死循环的根本原因，这也是jdk 1.8改进的地方。

可能文字有点苍白哈，接下来使用图的方式来进一步解释：为什么在并发的情况下出现rehash会形成死循环。

假设一个容量为2大小的hashmap,数据存储如下

rehash时会扩容一个容量为4大小的hashmap,rehash过程采用头节点插入的方式，正常的迁移过程如下：

上面的迁移过程是没有并发多线程操作的,那么下面模拟如果存在并发，且多线程同时迁移时回发生情况？

线程1开始执行rehash操作，但是还没有发生迁移。当执行到当前节点e为key为3，next节点为key为7时，线程1时间片用完发生阻塞操作，如下图：

线程2此时也发生rehash操作，且已经迁移了key为3和key为7的俩个节点了，迁移到新数组的数据分布如下，此时线程2时间片用完，发生了阻塞。

原数组种key为3的next节点为key为7，key为7的next指针为key为5，但是经过线程2的rehash后，发现此时key为7的next指向的是key为3，可通过上图看出出。

此时线程1激活，恢复到线程1切换之前的状态，切换之前e指向key为3，开始执行rehash操作，将key为3的节点插入到新数组的头节点。

此时死循环出现。

解决方案

• 使用线程安全容器 ConcurrentHashMap 替代(推荐使用此方案)。
• 使用线程安全容器 Hashtable 替代(性能低，不建议使用)。
• 使用 synchronized 或 Lock 加锁 HashMap 之后，再进行操作，相当于多线程排队执行(比较麻烦，也不建议使用)。

数据不一致

出现数据不一致的情况是很常见的，出现的前提条件是有并发情况下，多个线程都存在写入数据。

1. 首先A希望插入一个key-value对到HashMap中，首先计算记录所要落到的桶的索引坐标，然后获取到该桶里面的链表头结点，此时线程A的时间片用完了，发生阻塞。
2. 此时线程B开始执行， 假设线程A插入的记录计算出来的桶索引和线程B要插入的记录计算出来的桶索引是一样的，且当线程B成功插入。
3. 线程A再次被调度运行，它依然持有过期的链表头且对线程B已经插入的节点一无所知，以至于它认为它应该这样做，如果线程A插入成功，将会覆盖线程B插入的头节点记录，这样线程B插入的记录就凭空消失了，造成了数据不一致的行为。

java8的改善

1、由 数组+链表 的结构改为 数组+链表+红黑树。当链表长度大于8时则会自动转化为红黑树。
2、新增节点头插法改为尾部插入法。