源码分析--ConcurrentHashMap与HashTable(JDK1.8)
程序员文章站
2023-03-31 23:50:40
ConcurrentHashMap和Hashtable都是线程安全的K-V型容器。本篇从源码入手,简要说明它们两者的实现原理和区别。 与HashMap类似,ConcurrentHashMap底层也是以数组+链表+红黑树实现的,以Node节点封装K-V和hash。 val和next以volatile关 ......
concurrenthashmap和hashtable都是线程安全的k-v型容器。本篇从源码入手,简要说明它们两者的实现原理和区别。
与hashmap类似,concurrenthashmap底层也是以数组+链表+红黑树实现的,以node节点封装k-v和hash。
static class node<k,v> implements map.entry<k,v> { final int hash; final k key; volatile v val; volatile node<k,v> next; }
val和next以volatile关键字进行修饰,保证内存可见性。
看一下它的put()方法:
final v putval(k key, v value, boolean onlyifabsent) { if (key == null || value == null) throw new nullpointerexception(); int hash = spread(key.hashcode()); int bincount = 0; for (node<k,v>[] tab = table;;) { node<k,v> f; int n, i, fh; if (tab == null || (n = tab.length) == 0) tab = inittable(); else if ((f = tabat(tab, i = (n - 1) & hash)) == null) { if (castabat(tab, i, null, new node<k,v>(hash, key, value, null))) break; // no lock when adding to empty bin } else if ((fh = f.hash) == moved) tab = helptransfer(tab, f); else { v oldval = null; synchronized (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; } } } } if (bincount != 0) { if (bincount >= treeify_threshold) treeifybin(tab, i); if (oldval != null) return oldval; break; } } } addcount(1l, bincount); return null; }
- 与hashmap不同,不允许空键值
- 计算hashcode
- 判断是否初始化
- 如果当前位置为空,利用cas算法,放置节点
- 如果当前hashcode == moved,进行扩容
- 利用synchronized锁,进行链表或者红黑树的节点放置
- 链表数量大于8,转为红黑树
concurrenthashmap的get()方法没有使用同步锁机制。
jdk1.8以后,concurrenthashmap的线程安全都是利用cas + synchronized来实现的。效率较高。
对于hashtable,它底层为数组+链表结构,也不允许空键值。以entry封装k-v和hash。
主要get()和put()方法:
public synchronized v get(object key) { entry<?,?> tab[] = table; int hash = key.hashcode(); int index = (hash & 0x7fffffff) % tab.length; for (entry<?,?> e = tab[index] ; e != null ; e = e.next) { if ((e.hash == hash) && e.key.equals(key)) { return (v)e.value; } } return null; } public synchronized v put(k key, v value) { // make sure the value is not null if (value == null) { throw new nullpointerexception(); } // makes sure the key is not already in the hashtable. entry<?,?> tab[] = table; int hash = key.hashcode(); int index = (hash & 0x7fffffff) % tab.length; @suppresswarnings("unchecked") entry<k,v> entry = (entry<k,v>)tab[index]; for(; entry != null ; entry = entry.next) { if ((entry.hash == hash) && entry.key.equals(key)) { v old = entry.value; entry.value = value; return old; } } addentry(hash, key, value, index); return null; }
hashtable不仅因为没有红黑树,对于数据遍历的效率就比较低,而且在get()方法都加了synchronized关键字,而且get()和put()方法都是直接加在方法上。这样一来效率就比concurrenthashmap低得多了。所以,如果要在并发情况下使用k-v容器,使用concurrenthashmap更好。
推荐阅读
-
JDK1.8中的ConcurrentHashMap使用及场景分析
-
JDK源码分析(10)之 Hashtable 相关
-
Android getJSONObject与optJSONObject的区别结合源码分析
-
Android getJSONObject与optJSONObject的区别结合源码分析
-
Spring Cloud动态配置实现原理与源码分析
-
[Abp vNext 源码分析] - 7. 权限与验证
-
HashMap源码分析--jdk1.8
-
Spring Cloud动态配置实现原理与源码分析
-
[Abp vNext 源码分析] - 11. 用户的自定义参数与配置
-
spring源码分析系列5:ApplicationContext的初始化与Bean生命周期