面试题分析思路: 该题是一个数据结构问题,可以从HashMap的底层数据结构进行分析;建议从多个不同jdk版本进行分析
JDK1.8版本的,内部使用数组 + 链表红黑树
一般如果 new HashMap() 不传值,默认大小是16,负载因子是0.75, 如果自己传入初始大小k,初始
化大小为 大于k的 2的整数次方,例如如果传10,大小为16。(补充说明:实现代码如下)
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
123456789
hash函数是先拿到 key 的hashcode,是一个32位的int值,然后让hashcode的高16位和低16位进行异
或操作。
这么设计有二点原因:
bucketIndex = indexFor(hash, table.length);
static int indexFor(int h, int length) {
return h & (length-1);
}
12345
这也正好解释了为什么HashMap的数组长度要取2的整数幂。因为这样(数组长度-1)正好相当于一个
“低位掩码”。“与”操作的结果就是散列值的高位全部归零,只保留低位值,用来做数组下标访问。以初
始长度16为例,16-1=15。2进制表示是00000000 00000000 00001111。和某散列值做“与”操作如
下,结果就是截取了最低的四位值。
10100101 11000100 00100101
& 00000000 00000000 00001111
----------------------------------
00000000 00000000 00000101 //高位全部归零,只保留末四位
1234
但这时候问题就来了,这样就算我的散列值分布再松散,要是只取最后几位的话,碰撞也会很严重。更
要命的是如果散列本身做得不好,分布上成等差数列的漏洞,如果正好让最后几个低位呈现规律性重
复。
此时“扰动函数”的价值就体现出来了,说到这里大家应该猜出来了。看下面这个图,
右移16位,正好是32bit的一半,自己的高半区和低半区做异或,就是为了混合原始哈希码的高位和低
位,以此来加大低位的随机性。而且混合后的低位掺杂了高位的部分特征,这样高位的信息也被变相保
留下来。
最后我们来看一下Peter Lawley的一篇专栏文章《An introduction to optimising a hashing strategy》里的的一个实验:他随机选取了352个字符串,在他们散列值完全没有冲突的前提下,对它
们做低位掩码,取数组下标。
结果显示,当HashMap数组长度为512的时候(29),也就是用掩码取低9位的时候,在没有扰动函数
的情况下,发生了103次碰撞,接近30%。而在使用了扰动函数之后只有92次碰撞。碰撞减少了将近
10%。看来扰动函数确实还是有功效的。
另外Java1.8相比1.7做了调整,1.7做了四次移位和四次异或,但明显Java 8觉得扰动做一次就够了,做
4次的话,多了可能边际效用也不大,所谓为了效率考虑就改成一次了。
下面是1.7的hash代码:
static int hash(int h) {
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
1234
不是,在多线程环境下,1.7 会产生死循环、数据丢失、数据覆盖的问题,1.8 中会有数据覆盖的问
题,以1.8为例,当A线程判断index位置为空后正好挂起,B线程开始往index位置的写入节点数据,这
时A线程恢复现场,执行赋值操作,就把A线程的数据给覆盖了;还有++size这个地方也会造成多线程同
时扩容等问题。
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null) //多线程执行到这里
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode) // 这里很重要
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold) // 多个线程走到这,可能重复resize()
resize();
afterNodeInsertion(evict);
return null;
}
123456789101112131415161718192021222324252627282930313233343536373839404142
Java中有HashTable、Collections.synchronizedMap、以及ConcurrentHashMap可以实现线程安全的
Map。
HashTable是直接在操作方法上加synchronized关键字,锁住整个数组,粒度比较大,
Collections.synchronizedMap是使用Collections集合工具的内部类,通过传入Map封装出一个
SynchronizedMap对象,内部定义了一个对象锁,方法内通过对象锁实现;ConcurrentHashMap使用
分段锁,降低了锁粒度,让并发度大大提高
ConcurrentHashMap的分段锁的实现原理吗?
链表转红黑树是链表长度达到阈值,这个阈值是多少?为什么?
HashMap内部节点是有序的吗?
讲讲LinkedHashMap怎么实现有序的?
讲讲TreeMap怎么实现有序的?
通过CAS 和 synchronized结合实现锁粒度的降低,讲讲CAS 的实现以及synchronized的实现原理
吗?