Author 2020-03-19
PDF
HashTable1阅读笔记：ConcurrentHashMap刨根问底并发编程ContentsCollections.synchronizedMap ....................................................................... 1HashTable ............................................................................................. 1ConcurrentHashMap ................................................................................. 2操作操作我们知道不是的，而内部采取了同步操作，是线程安全的。然而有趣的是你去看的文档，它会建议你：如果不要你就用吧，否则你用好了。一般如果对线程安全有要求，我们有如下的一些选择：Collections.synchronizedMap这个实现很粗暴，实际上就是将的各个操作都进行了包装和同步：private static class SynchronizedMap<K,V> implements Map<K,V>, Serializable { private final Map<K,V> m; // Backing Map final Object mutex; SynchronizedMap(Map<K,V> m) { this.m = Objects.requireNonNull(m); mutex = this; }在构造函数中传入了原来的，以及一个对象锁（如果不传那就默认是了）。然后，所有的操作都进行了同步处理：public boolean containsValue(Object value) { synchronized (mutex) {return m.containsValue(value);}}public V get(Object key) { synchronized (mutex) {return m.get(key);}}// ...HashTable实现线程安全的方式与上面有些类似，对所有需要同步的地方直接进行了同步：public synchronized int size() { return count;} ConcurrentHashMap2那么和有什么区别呢？除了同步之外，总结下来有以下几点：允许一个的，也可以为；但是不允许作为或者是才引入的是基于接口实现的（以及）都是不允许值作为和的，主要的原因是因为要支持并发，假设调用get(key)得到了，你是不能确认是不存在，还是说存在但是值为。在非并发场景下可以通过contains(key)来判断是否真的存在，但是在并发场景下，很可能会被其他线程修改。在注释中有这样的解释：ConcurrentHashMap在和中实现差别较大，在中采用分段锁的方式实现，将分为许多个（继承自）操作的时候，只会去占用某一个，而其他的不会受到影响。而在中直接使用来实现。其在内存中的结构与几乎相同了。get操作public V get(Object key) { Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek; // 得到最终的hash值（将高位混合到低位去避免哈希冲突） int h = spread(key.hashCode()); if ((tab = table) != null && (n = tab.length) > 0 && // (n-1) & h 计算出所在的index值（与HashMap相同） (e = tabAt(tab, (n - 1) & h)) != null) { // 如果哈希值相同，则直接定位到节点，再判断是否equal即可 if ((eh = e.hash) == h) { // 这里比较key是否equal，单纯只凭hashCode是不够的。 // 首先比较内存地址是否一致；然后再调用equals方法，是一种优化手段。 if ((ek = e.key) == key || (ek != null && key.equals(ek))) return e.val; } /* Hash值的首位被用作标记位，为负数的hash值是特殊的节点（也就是红黑树化了） ConcurrentHashMap3 */ // 如果根据哈希值没有匹配到，那证明可能有哈希冲突，为负数是红黑树则在树中查找 else if (eh < 0) return (p = e.find(h, key)) != null ? p.val : null; // 否则是普通的链表，在链表中一直朝下找即可 while ((e = e.next) != null) { if (e.hash == h && ((ek = e.key) == key || (ek != null && key.equals(ek)))) return e.val; } } return null;}可见操作没有加任何的锁，而是通过将transient volatile Node<K,V>[] table;将设置为来保证可见性的。transient volatile Node<K,V>[] table;static class Node<K,V> implements Map.Entry<K,V> { final int hash; final K key; volatile V val; volatile Node<K,V> next; //...}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) { // 尝试CAS插入节点到空桶中，如果失败，则会重新走上面的流程进来 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; ConcurrentHashMap4 // f为当前定位到的桶中的第一个节点，将其同步进行后续操作 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); ConcurrentHashMap5 return null;}

HTML view coming soon.

Download PDF for the full formatted version.