HashMap,HashTable,conccurentHashMap的区别

HashMap

HashMap是线程不安全的。可以通过Collections将其包装为线程安全的Map

我们看一下Collections的synchronizedMap方法

public static <K,V> Map<K,V> synchronizedMap(Map<K,V> m) {
        return new SynchronizedMap<>(m);
    }

使用了互斥对象 mutex来带到同步。对所有Publish的方法都采用
synchronized (mutex)方法进行加锁

 private static class SynchronizedMap<K,V>
        implements Map<K,V>, Serializable {
        private static final long serialVersionUID = 1978198479659022715L;

        private final Map<K,V> m;     // Backing Map
        final Object      mutex;        // Object on which to synchronize

        SynchronizedMap(Map<K,V> m) {
            this.m = Objects.requireNonNull(m);
            mutex = this;
        }

        SynchronizedMap(Map<K,V> m, Object mutex) {
            this.m = m;
            this.mutex = mutex;
        }

        public int size() {
            synchronized (mutex) {return m.size();}
        }
        public boolean isEmpty() {
            synchronized (mutex) {return m.isEmpty();}
        }
        public boolean containsKey(Object key) {
            synchronized (mutex) {return m.containsKey(key);}
        }
        public boolean containsValue(Object value) {
            synchronized (mutex) {return m.containsValue(value);}
        }
		}

HashTable

hashtable是线程安全的。实现方法是将涉及到修改hashtable的方法，使用synchronized修饰，如下所示，相当获取当前HashMap实例的锁。和Collections的synchronizedMap方法的差别就是加锁对象的不同

  public synchronized int size() {
        return count;
    }

  
    public synchronized boolean isEmpty() {
        return count == 0;
    }

ConccurentHashMap

无论是Collections的synchronizedMap方法还是HashTable都是串行执行的，效率不高

数据结构

早期的conccurentHashMap

采用分段加锁的方式

现在的conccurentHashMap

只要不发生hash冲突就不进行加锁，而是采用无锁的CAS进行尝试操作

 public V put(K key, V value) {
        return putVal(key, value, false);
    }

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;
	        
	        //采用CSA尝试操作，失败则进入下个循环继续尝试操作
	        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 {
	            	
	  //如果发生Hash碰撞，则对链表或者红黑树的头结点进行加锁
	                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,Hashtable,ConccurentHashpMap三者的区别

其他问题

多线程扩容

ConcurrentHashMap 的 size 方法原理分析