聊聊JAVA中的HashMap和ConcurrentHashMa

Map是一个"Key Value"数据结构的集合，在Java企业级项目里使用频率非常高，仅次于List。

Map大家族里面成员非常多，有HashMap，TreeMap，LinkedHashMap，ConcurrentHashMap等等，这里重点聊一下HashMap和ConcurrentHashMap。

HashMap

HashMap的存储结构是基于数组+链表组成的，不过在jdk1.8之后有了一定的改变，当链表达到一定的长度就会转变成红黑树。HashMap在存储数据的时候有三个基本概念：

名称	说明
table	存储所有节点的数组
slot	哈希槽，即table[i]这个位置
bucket	哈希桶，table[i]上所有元素的集合

如下图所示，每一个紫色箭头指向的即是哈希槽，它仅仅是一个位置的标识。哈希桶即是哈希槽上形成的链表或树上所有元素的集合。那么我们可以得知一个Map的size大小就等于所有哈希桶的元素总和。

hashMap存储结构图

HashMap如何存放数据

HashMap里面每一个元素都是一个Node类型，JDK1.8之前每一个元素是Map.Entry类型，它和Node的属性是一样的。

static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;

        Node(int hash, K key, V value, Node<K,V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }

        ......
    }

其中key和value就是我们存放键值对对应的属性，next属性链接链表的下一个元素，hash是HashMap的hash方法通过每一个对象的hashcode值位移运算计算出来的。

 static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

我们再来看一下hashMap的核心方法put，put方法逻辑其实比较容易理解，大概就是判断这个元素放到什么位置，table容量是否需要扩容，存放元素。

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

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        //1、判断hash桶是否为空，为空的话就初始化一个桶
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
       //2、根据当前key的hash值计算出这个元素所存放的hash槽是否为空，为空就直接新建一个元素存放进去
        if ((p = tab[i = (n - 1) & hash]) == null)  
            tab[i] = newNode(hash, key, value, null);
       //3、如果该hash槽不为空就走下面的逻辑
        else {   
            Node<K,V> e; K k;
       //4、判断是否有hash冲突已经key值是否相等，如果key值相等就直接复制给临时变量，并统一放到后面处理
            if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k)))) 
                e = p;
        //5、判断当前桶是否是红黑树结构，如果是的话就以红黑数的方式写入数据
            else if (p instanceof TreeNode)  
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
         //6、当前桶如果不是红黑树就存放到桶内最后一个元素的末尾形成链表
            else {  
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {  
                        p.next = newNode(hash, key, value, null);
         //7.判断当前链表的长度是否大于等于阈值，是的话就把链表转换成红黑树
                        if (binCount >= TREEIFY_THRESHOLD - 1) 
                            treeifyBin(tab, hash);
                        break;
                    }
                    if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
          //8.判断传入的key是否存在，存在的话就直接覆盖
            if (e != null) {
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
       //9.判断是否需要扩容
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
}

HashMap如何获取数据

HashMap获取数据逻辑比较简单，看一下get方法。

public V get(Object key) {
        Node<K,V> e;
        return (e = getNode(hash(key), key)) == null ? null : e.value;
 }

    /**
     * Implements Map.get and related methods
     *
     * @param hash hash for key
     * @param key the key
     * @return the node, or null if none
     */
final Node<K,V> getNode(int hash, Object key) {
        Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
        // 1、判断table里面是否有数据，有数据就走下面的逻辑如果没有直接返回null
        if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) {
        // 2、判断hash槽的第一个元素的hash值和key是否一致，一致就直接返回hash槽的第一个元素
            if (first.hash == hash && ((k = first.key) == key || (key != null && key.equals(k))))
                return first;
            if ((e = first.next) != null) {
         //3、判断hash槽内的结构是否是红黑数，是的话就以红黑树的方式取数据
                if (first instanceof TreeNode)
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);
         //4、否则迭代链表，找到对应的元素并返回
                do {
                    if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }
        return null;
 }

HashMap如何扩容

通常HashMap扩容逻辑是复杂且耗时的，所以通常在初始化一个HashMap的时候按照预计插入的数据量设置一个初始容量initialCapacity是一个不错的选择。

 /**
     * Constructs an empty <tt>HashMap</tt> with the specified initial
     * capacity and the default load factor (0.75).
     *
     * @param  initialCapacity the initial capacity.
     * @throws IllegalArgumentException if the initial capacity is negative.
     */
public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

 public HashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);
        this.loadFactor = loadFactor;
      
        this.threshold = tableSizeFor(initialCapacity);
    }

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;
}

那么设置多大的容量比较合适呢，我们可以看一下resize方法。

final Node<K,V>[] resize() {
        Node<K,V>[] oldTab = table;
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        int oldThr = threshold;
        int newCap, newThr = 0;
        if (oldCap > 0) {
            if (oldCap >= MAXIMUM_CAPACITY) {
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY)
                newThr = oldThr << 1; // double threshold
        }
        else if (oldThr > 0) // initial capacity was placed in threshold
            newCap = oldThr;
        else {               // zero initial threshold signifies using defaults
            newCap = DEFAULT_INITIAL_CAPACITY;
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        if (newThr == 0) {
            float ft = (float)newCap * loadFactor;
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                      (int)ft : Integer.MAX_VALUE);
        }
        threshold = newThr;
       ......

可以看到传入的初始化容量initialCapacity并不会直接使用，而是调用tableSizeFor方法转换成一个为2的N次幂的数newCap，然后当HashMap的size大于newCap * loadFactor(默认是0.75)的时候就会进行扩容。例如initialCapacity是10那么最终HashMap的初始容量就是16，当HashMap的size大于12(16 * 0.75)的时候就进行第一次扩容。initialCapacity是1000那么最终HashMap的初始容量就是1024，当HashMap的size大于768(1024 * 0.75)的时候就进行第一次扩容。

所以可以得出结论，你HashMap初始化可以设置为(需要存储的元素个数 / 负载因子) +1，例如你需要存7个元素那么应该设置map的初始值为7/0.75 +1 = 10。然后通过tableSizeFor方法的转换HashMap初始的initialCapacity就会变成16，这就大大减少了扩容的几率。

ConcurrentHashMap

考虑到线程并发安全性 ConcurrentHashMap 是比 HashMap 更加推荐的一种哈希式集合。其底层的数据结构依然是数组+链表+红黑数。JDK8对ConcurrentHashMap进行了脱胎换骨的改造，不再使用分段锁Segment来保证线程安全问题。进而使用的是CAS加synchronized来保证线程安全。

ConcurrentHashMap初始化容量

ConcurrentHashMap初始化容量的逻辑和HashMap略有不同。ConcurrentHashMap会把存入的初始容量加上其1/2然后再加上1，进而再通过tableSizeFor方法转换成一个2的N幂的数。这样初始化数组的的值会比HashMap要大，避免了哈希碰撞。

    public ConcurrentHashMap(int initialCapacity,
                             float loadFactor, int concurrencyLevel) {
        if (!(loadFactor > 0.0f) || initialCapacity < 0 || concurrencyLevel <= 0)
            throw new IllegalArgumentException();
        if (initialCapacity < concurrencyLevel)   // Use at least as many bins
            initialCapacity = concurrencyLevel;   // as estimated threads
        long size = (long)(1.0 + (long)initialCapacity / loadFactor);
        int cap = (size >= (long)MAXIMUM_CAPACITY) ?
            MAXIMUM_CAPACITY : tableSizeFor((int)size);
        this.sizeCtl = cap;
    }

ConcurrentHashMap是如何存放数据

ConcurrentHashMap会先初始化出一个数组，元素会优先插入到数组的槽点中，如果槽点有元素就锁住该槽点存放元素。

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;
            //第一次put数据的时候会线初始化一个table，再继续循环存入第一数据
            if (tab == null || (n = tab.length) == 0)
                tab = initTable();
            //f 即为当前 key 定位出的槽点位置，如果为空表示当前槽点位置可以写入数据，利用 CAS 尝试写入，失败则自旋保证成功。
            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;
                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;
    }

ConcurrentHashMap如何取出数据

get的逻辑相对比较简单，通过hashcode来寻址，如果直接在hash槽找到数据就直接返回，如果在hash桶里就根据链表遍历或红黑树遍历来查找数据。

public V get(Object key) {
        Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
        int h = spread(key.hashCode());
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (e = tabAt(tab, (n - 1) & h)) != null) {
            if ((eh = e.hash) == h) {
                if ((ek = e.key) == key || (ek != null && key.equals(ek)))
                    return e.val;
            }
            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;
    }

ConcurrentHashMap如何更新元素数量

ConcurrentHashMap主要由两个属性来存储元素数量，baseCount和counterCells。

private transient volatile long baseCount;

@sun.misc.Contended static final class CounterCell {
        volatile long value;
        CounterCell(long x) { value = x; }
}

private transient volatile CounterCell[] counterCells;

• 当并发量比较小的时候，优先使用CAS的方式直接更新baseCount。
• 当更新baseCount冲突，则会通过启用counterCells减少线程竞争，通过CAS的方式把总数更新情况记录在counterCells对应的位置上。
• 如果更新counterCells上的某个位置出现了多次失败，则会通过扩容counterCells的方式减少冲突。
• 当counterCells处在扩容期间时，会尝试更新baseCount值。
  对于元素总数的统计逻辑就很简单了，用baseCount加上各counterCells内的数据就可以得到ConcurrentHashMap总元素值，完全不需要加锁。