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 之后，再进行操作，相当于多线程排队执行(比较麻烦，也不建议使用)。
数据不一致
出现数据不一致的情况是很常见的，出现的前提条件是有并发情况下，多个线程都存在写入数据。
- 首先A希望插入一个key-value对到HashMap中，首先计算记录所要落到的桶的索引坐标，然后获取到该桶里面的链表头结点，此时线程A的时间片用完了，发生阻塞。
- 此时线程B开始执行， 假设线程A插入的记录计算出来的桶索引和线程B要插入的记录计算出来的桶索引是一样的，且当线程B成功插入。
- 线程A再次被调度运行，它依然持有
过期的链表头且对线程B已经插入的节点一无所知，以至于它认为它应该这样做，如果线程A插入成功，将会覆盖线程B插入的头节点记录，这样线程B插入的记录就凭空消失了，造成了数据不一致的行为。
java8的改善
1、由 数组+链表 的结构改为 数组+链表+红黑树。当链表长度大于8时则会自动转化为红黑树。
2、新增节点头插法改为尾部插入法。
网友评论