对于JDK1.8之后的hashMap,底层采用数组+链表、红黑树的实现方式。
我们都知道对于给定的key先计算其hashcode然后hashcode再对数组的长度取余从而得到其所在的数组下标,当出现hash冲突时从,采用的链地址法将相同位置的Entry串到一条链表上,但是随着链表长度的增大,会极大的降低查找速率,因此当链表长度大于8时会由链表转为红黑树。(使用红黑树而不直接使用经典的AVL树的原因是红黑树与AVL树查询效率相当,但是红黑树牺牲一部分的平衡性从而提高了插入删除的效率,总体效率得到提升)。
1.7中的的hash算法很容易构造出hash值相等的key,产生长链表,使用如此大量的key可以对服务器进行大量请求,并进一步进行dos攻击。
1.7中的扩容会带来死循环问题。
给定一个key其所在的数组下标的计算:
index = hashcode & (n - 1)
上述式子中n指的是当前数组的长度,其值必须为2的整数次幂。
hashcode对长度取余的操作是通过hashcode与n - 1的与运算实现的,例如n = 16 hashcode = 20,取余等于4
n = 1 0 0 0 0
n - 1 = 0 1 1 1 1
hashcode = 1 1 0 0 0
hashcode & (n - 1) = 0 1 0 0 0
通过该例子我们发现了,当n是2的整数次幂的时候,其-1的值就为后面一个连0串+连1串,与该值相与的结果就恰好为对n取余的结果。
此外jdk1.8之后hashcode的计算变为如下
hashcode = hashcode ^ (hashcode >>> 16)
如此为了处理hashcode高位不同低位相同产生hash冲突的情况。
例如N = 2^16 ,若使用旧的计算方式,当低16相同时对于高16位取任意值其hashcode总是相同的
当前的桶数目达到最大数组*0.75之后时,会进行扩容操作,每次增加一倍。
除了一般线程安全问题,hashmap的扩容还存在一个致命的线程问题。
扩容过程为首先创建一个新的数组,再对旧数组的结点重新计算数组下标(毕竟数组长度变了),然后复制过去。
1.7中的扩容会带来死循环问题。其复制源码如下
// jdk1.7 HashMap
void transfer(Entry[] newTable)
{
// oldTable
Entry[] src = table;
int newCapacity = newTable.length;
for (int j = 0; j < src.length; j++) {
Entry<K,V> e = src[j];
if (e != null) {
// 将旧位置置null
src[j] = null;
do {
Entry<K,V> next = e.next;
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
} while (e != null);
}
}
}
上述过程就是一个链表的头插法的过程。第一步保存其后一个结点,第二步将该节点插入到新表的头部,第三步换头
单线程操作毫无问题,并发操作时当第一个线程刚执行完第一步时,第二个线程抢占了处理机,然后完成整个过程。
上述第一张图为线程一刚执行完第一步,第二张图为线程2抢占完完成整个过程后线程一执行第二步,第三张图为线程1执行完第三步的结果。
jdk1.8之后使用尾插法的方式解决该问题。那么jdk1.7版本中为何不使用尾插法呢?由于jdk1.7版本中不存在红黑树只有链表结点,如果都采用尾插法会极大地降低效率,此外hashMap并不是线程安全的容器,多线程场景下还是采用concurrentHashMap。
document.querySelectorAll('.github-emoji') .forEach(el => { if (!el.dataset.src) { return; } const img = document.createElement('img'); img.style = 'display:none !important;'; img.src = el.dataset.src; img.addEventListener('error', () => { img.remove(); el.style.color = 'inherit'; el.style.backgroundImage = 'none'; el.style.background = 'none'; }); img.addEventListener('load', () => { img.remove(); }); document.body.appendChild(img); });