主要从底层数据结构,线程安全,执行效率,是否允许Null值,初始容量及扩容,hash值计算来进行分析。
1.底层数据结构
transient Node<K,V>[] table; //HashMap
transient volatile Node<K,V>[] table;//ConcurrentHashMap
private transient Entry<?,?>[] table;//HashTable
HashMap=数组+链表+红黑树
HashMap的底层数据结构是一个数组+链表+红黑树,数组的每个元素存储是一个链表的头结点,链表中存储了一组哈希值冲突的键值对,通过链地址法来解决哈希冲突的。为了避免链表长度过长,影响查找元素的效率,当链表的长度>8时,会将链表转换为红黑树,链表的长度<6时,将红黑树转换为链表(但是红黑树转换为链表的时机不是在删除链表时,而是在扩容时,发现红黑树分解后的两个链表<6,就按链表处理,否则就建立两个小的红黑树,设置到扩容后的位置)。之所以临界点为8是因为红黑树的查找时间复杂度为logN,链表的平均时间查找复杂度为N/2,当N为8时,logN为3,是小于N/2的,正好可以通过转换为红黑树减少查找的时间复杂度。
Hashtable=数组+链表
Hashtable底层数据结构跟HashMap一致,底层数据结构是一个数组+链表,也是通过链地址法来解决冲突,只是链表过长时,不会转换为红黑树来减少查找时的时间复杂度。Hashtable属于历史遗留类,实际开发中很少使用。
ConcurrentHashMap=数组+链表+红黑树
ConcurrentHashMap底层数据结构跟HashMap一致,底层数据结构是一个数组+链表+红黑树。只不过使用了volatile来进行修饰它的属性,来保证内存可见性(一个线程修改了这些属性后,会使得其他线程中对于该属性的缓存失效,以便下次读取时取最新的值)。
2.线程安全
HashMap 非线程安全
HashMap是非线程安全的。(例如多个线程插入多个键值对,如果两个键值对的key哈希冲突,可能会使得两个线程在操作同一个链表中的节点,导致一个键值对的value被覆盖)
HashTable 线程安全
HashTable是线程安全的,主要通过使用synchronized关键字修饰大部分方法,使得每次只能一个线程对HashTable进行同步修改,性能开销较大。
ConcurrentHashMap 线程安全
ConcurrentHashMap是线程安全的,主要是通过CAS操作+synchronized来保证线程安全的。
CAS操作
往ConcurrentHashMap中插入新的键值对时,如果对应的数组下标元素为null,那么通过CAS操作原子性地将节点设置到数组中。
//这是添加新的键值对的方法
final V putVal(K key, V value, boolean onlyIfAbsent) {
...其他代码
if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value, null))) break; // 因为对应的数组下标元素为null,所以null作为预期值,new Node<K,V>(hash, key, value, null)作为即将更新的值,只有当内存中的值与即将预期值一致时,才会进行更新,保证原子性。
}
...其他代码
}
static final <K,V> boolean casTabAt(Node<K,V>[] tab, int i,
Node<K,V> c, Node<K,V> v) {
return U.compareAndSwapObject(tab, ((long)i << ASHIFT) + ABASE, c, v);
}
synchronized锁
往ConcurrentHashMap中插入新的键值对时,如果对应的数组下标元素不为null,那么会对数组下标存储的元素(也就是链表的头节点)加synchronized锁, 然后进行插入操作,
Node<K,V> f = tabAt(tab, i = (n - 1) & hash));
synchronized (f) {//f就是数组下标存储的元素
if (tabAt(tab, i) == f) {
if (fh >= 0) {
binCount = 1;
for (Node<K,V> e = f;; ++binCount) {
K ek;
if (e.hash == hash &&
((ek = e.key) == key ||
(ek != null && key.equals(ek)))) {
oldVal = e.val;
if (!onlyIfAbsent)
e.val = value;
break;
}
Node<K,V> pred = e;
if ((e = e.next) == null) {
pred.next = new Node<K,V>(hash, key,
value, null);
break;
}
}
}
else if (f instanceof TreeBin) {
Node<K,V> p;
binCount = 2;
if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
value)) != null) {
oldVal = p.val;
if (!onlyIfAbsent)
p.val = value;
}
}
}
}
3.执行效率
因为HashMap是非线程安全的,执行效率会高一些,其次是ConcurrentHashMap,因为HashTable在进行修改和访问时是对整个HashTable加synchronized锁,所以效率最低。
4.是否允许null值出现
HashMap的key和null都可以为null,如果key为null,那么计算的hash值会是0,最终计算得到的数组下标也会是0,所以key为null的键值对会存储在数组中的首元素的链表中。value为null的键值对也能正常插入,跟普通键值对插入过程一致。
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
HashTable的键和值都不能为null,如果将HashTable的一个键值对的key设置为null,因为null值没法调用hashCode()方法获取哈希值,所以会抛出空指针异常。同样value为null时,在put方法中会进行判断,然后抛出空指针异常。
public synchronized V put(K key, V value) {
// Make sure the value is not null
if (value == null) {
throw new NullPointerException();
}
Entry<?,?> tab[] = table;
int hash = key.hashCode();
...其他代码
}
ConcurrentHashMap的键和值都不能为null,在putVal方法中会进行判断,为null会抛出空指针异常。
final V putVal(K key, V value, boolean onlyIfAbsent) {
if (key == null || value == null) throw new NullPointerException();
int hash = spread(key.hashCode());
...其他代码
}
5.初始容量及扩容
不指定初始容量
如果不指定初始容量,HashMap和ConcurrentHashMap默认会是16,HashTable的容量默认会是11。
不指定初始容量
如果制定了初始容量,HashMap和ConcurrentHashMap的容量会是比初始容量稍微大一些的2的幂次方大小,HashTable会使用初始容量,
扩容
扩容时,HashMap和ConcurrentHashMap扩容时会是原来长度的两倍,HashTable则是2倍加上1.
6.hash值计算
HashTable会扩容为2n+1,HashTable之所以容量取11,及扩容时是是2n+1,是为了保证 HashTable的长度是一个素数,因为数组的下标是用key的hashCode与数组的长度取模进行计算得到的,而当数组的长度是素数时,可以保证计算得到的数组下标分布得更加均匀
public synchronized V put(K key, V value) {
...其他代码
// Makes sure the key is not already in the hashtable.
Entry<?,?> tab[] = table;
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
...其他代码
}
HashMap和ConcurrentHashMap的hash值都是通过将key的hashCode()高16位与低16位进行异或运算(这样可以保留高位的特征,避免一些key的hashCode高位不同,低位相同,造成hash冲突),得到hash值,然后将hash&(n-1)计算得到数组下标。(n为数组的长度,因为当n为2的整数次幂时,hash mod n的结果在数学上等于hash&(n-1),而且计算机进行&运算更快,所以这也是HashMap的长度总是设置为2的整数次幂的原因)
//HashMap计算hash值的方法
static int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
//ConcurrentHashMap计算hash值的方法
static int spread(int h) {//h是对象的hashCode
return (h ^ (h >>> 16)) & HASH_BITS;// HASH_BITS = 0x7fffffff;
}
原创文章,作者:9IM,如若转载,请注明出处:https://www.9im.cn/668.html