HashMap

hashMap1.7的数据结构

1.7的结构如下图，底层是一个大的Entry数组，每个数组元素为一个链表。图中同时可以看出put和get的流程。下面对put和get的部分代码用图示方式展示，同时可以参考源码自己分析。

HashMap1.7.png

put方法源码

public V put(K key, V value) {
        if (table == EMPTY_TABLE) {
            // 初始化桶
            inflateTable(threshold);
        }
        if (key == null)
            return putForNullKey(value);
        int hash = hash(key);
        int i = indexFor(hash, table.length);
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }

        modCount++;
        addEntry(hash, key, value, i);
        return null;
    }

void addEntry(int hash, K key, V value, int bucketIndex) {
        if ((size >= threshold) && (null != table[bucketIndex])) {
            // 此处扩容
            resize(2 * table.length);
            hash = (null != key) ? hash(key) : 0;
            bucketIndex = indexFor(hash, table.length);
        }
        // 创建键值对并加入map中
        createEntry(hash, key, value, bucketIndex);
    }

void createEntry(int hash, K key, V value, int bucketIndex) {
        Entry<K,V> e = table[bucketIndex];
        table[bucketIndex] = new Entry<>(hash, key, value, e);
        size++;
    }

get方法源码

public V get(Object key) {
        if (key == null)
            return getForNullKey();
        Entry<K,V> entry = getEntry(key);

        return null == entry ? null : entry.getValue();
    }

hashMap1.8的数据结构

1.8的数据结构如下图，同时跟1.7一样，put个get操作的大体流程也绘制在图中了。朋友们可以对照着源码和图自行消化一下。

HashMap 1.8 的数据结构.png

老规矩，源码说话。

put方法

public V put(K key, V value) {
        // 先计算hashcode，key为0时直接返回0
        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;
        // 创建Map时并未初始化table，第一次put时先进行初始化操作  
        if ((tab = table) == null || (n = tab.length) == 0)
            // 初始化也是通过resize来实现的
            n = (tab = resize()).length;
        // 根据hashcode和table长度计算index，确定对应index下是否已经有值。
        if ((p = tab[i = (n - 1) & hash]) == null只
            // 为空时直接创建Node并插入
            tab[i] = newNode(hash, key, value, null);
        else {
            // 否则先判断key是否与表头元素相同，相同则直接返回node节点
            Node<K,V> e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            // 不同时判断是否为树节点，若为树节点则通过红黑树插入元素
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
                // 不是树节点说明还是链表，遍历链表
                for (int binCount = 0; ; ++binCount) {
                    // 判断是否为链尾，链尾的话直接插入
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        // 插入元素后判断元素个数是否超过阈值，超过则将链表转成红黑树
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    // 不是链尾就继续判断是否和key相同，相同则将node返回
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            // 如果改key已经存在，则根据onlyIfAbsent参数或旧值是否为空判断是否要覆盖元素
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        // 修改modCount
        ++modCount;
        // 修改map的size并判断是否需要扩容
        if (++size > threshold)
            // 扩容
            resize();
        afterNodeInsertion(evict);
        return null;
    }

get方法

public V get(Object key) {
        Node<K,V> e;
        // 同样还是先计算hashcode，然后通过getNode返回的节点获取value
        return (e = getNode(hash(key), key)) == null ? null : e.value;
    }

final Node<K,V> getNode(int hash, Object key) {
        Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
        // 当map不为空且根据hash与table.length计算得到的index处元素不为空时
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (first = tab[(n - 1) & hash]) != null) {
            // 这里判断头元素是否与给定key相同，相同就返回该node
            if (first.hash == hash && // always check first node
                ((k = first.key) == key || (key != null && key.equals(k))))
                return first;
            // 如果不是尾节点
            if ((e = first.next) != null) {
                // 为红黑树时调用红黑树的方法获取元素
                if (first instanceof TreeNode)
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                // 否则遍历链表获取指定key的元素
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }
        return null;
    }

HashMap 1.7和1.8的区别

主要有如下几点区别：

• 1.7与1.8在数据结构上来说底层都是一个大数组来存储，唯一的区别是数组的每个元素类型不同，1.7下是一个链表。1.8为了优化链表的检索速度将数组其结构改成了链表+红黑树。默认情况下在链表长度大于等于8时会将链表转成红黑树，在长度小于等于6时会退回链表。

• 在put时1.7采用的是头插法，而1.8采用的是尾插法。感兴趣的朋友可以继续深入看看为什么会有这种修改。

• 1.7的扩容发生在addEntry之前，而1.8的扩容发生在put结束之后。

如果还有其他的区别还请大家和我联系，我会补充上去。

ConcurrentHashMap

ConcurrentHashMap1.7的数据结构

1.7中ConcurrentHashMap采用了分段锁+Entry数组的结构，每个Segment其实是ReentrantLock的子类。因此天然拥有加锁的功能，其数据结构如下图。

ConcurrentHashMap1.7.png

1.7中的put和get流程如上图所示。其实并不复杂，由于表示数据的几个关键变量都被volatile修饰。因此大部分操作不需要加锁，仅在put时对所操作的分段加锁。get操作不加锁，size方法视具体情况而定，下面单独分析。

ConcurrentHashMap1.7的几处关键代码

初始化ConcurrentHashMap时确定分段大小即其他分段参数。

    public ConcurrentHashMap(){
        // ...省略其他代码
        int sshift = 0;
        // 分段大小
        int ssize = 1;
        // 默认concurrencyLevel是16，这里ssize每次 * 2，即循环可以执行4次，此时sshift=4，ssize = 16
        while (ssize < concurrencyLevel) {
            ++sshift;
            ssize <<= 1;
        }
        // 从上方计算结果可以得到，segmentShift = 28
        this.segmentShift = 32 - sshift;
        // segmentMark = 15
        this.segmentMask = ssize - 1;
        // ...省略其他代码
        // create segments and segments[0]
        Segment<K,V> s0 =
            new Segment<K,V>(loadFactor, (int)(cap * loadFactor),
                             (HashEntry<K,V>[])new HashEntry[cap]);
        Segment<K,V>[] ss = (Segment<K,V>[])new Segment[ssize];
        UNSAFE.putOrderedObject(ss, SBASE, s0); // ordered write of segments[0]
        this.segments = ss;
    }

segments数组的大小仅在上述初始化创建代码中确定，一旦map创建成功后分段个数不会改变，每次扩容也只针对某个分段内的桶进行扩容。

put方法

public V put(K key, V value) {
        Segment<K,V> s;
        if (value == null)
            throw new NullPointerException();
        int hash = hash(key);
        // 通过segmentShift和segmentMask计算key所在的分段位置
        int j = (hash >>> segmentShift) & segmentMask;
        // 如果分段尚未初始化(==null),则初始化该分段(即使用第一分段为原型创建新对象)
        if ((s = (Segment<K,V>)UNSAFE.getObject          // nonvolatile; recheck
             (segments, (j << SSHIFT) + SBASE)) == null) //  in ensureSegment
            s = ensureSegment(j);
        // 委托给分段的put方法
        return s.put(key, hash, value, false);
    }

private Segment<K,V> ensureSegment(int k) {
        final Segment<K,V>[] ss = this.segments;
        long u = (k << SSHIFT) + SBASE; // raw offset
        Segment<K,V> seg;
        if ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u)) == null) {
            // 使用第一个分段作为原型
            Segment<K,V> proto = ss[0]; // use segment 0 as prototype
            int cap = proto.table.length;
            float lf = proto.loadFactor;
            int threshold = (int)(cap * lf);
            HashEntry<K,V>[] tab = (HashEntry<K,V>[])new HashEntry[cap];
            if ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u))
                == null) { // recheck
                Segment<K,V> s = new Segment<K,V>(lf, threshold, tab);
                while ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u))
                       == null) {
                    if (UNSAFE.compareAndSwapObject(ss, u, null, seg = s))
                        break;
                }
            }
        }
        return seg;
    }

final V put(K key, int hash, V value, boolean onlyIfAbsent) {
            // 尝试获取锁，这里肯定能拿到锁，否则会挂起，直到拿到锁为止
            HashEntry<K,V> node = tryLock() ? null :
                scanAndLockForPut(key, hash, value);
            V oldValue;
            try {
                HashEntry<K,V>[] tab = table;
                // scanAndLockForPut方法中获取node节点时bucket的index计算方法与此处计算方法不同，下面对node进行操作时有什么影响？
                int index = (tab.length - 1) & hash;
                HashEntry<K,V> first = entryAt(tab, index);
                for (HashEntry<K,V> e = first;;) {
                    if (e != null) {
                        K k;
                        if ((k = e.key) == key ||
                            (e.hash == hash && key.equals(k))) {
                            oldValue = e.value;
                            if (!onlyIfAbsent) {
                                e.value = value;
                                ++modCount;
                            }
                            break;
                        }
                        e = e.next;
                    }
                    else {
                        // node不为null说明获取锁的时候创建了node对象，直接将node插入表头即可
                        if (node != null)
                            node.setNext(first);
                        else
                            node = new HashEntry<K,V>(hash, key, value, first);
                        int c = count + 1;
                        // 判断是否需要扩容
                        if (c > threshold && tab.length < MAXIMUM_CAPACITY)
                            rehash(node);
                        else
                            setEntryAt(tab, index, node);
                        ++modCount;
                        count = c;
                        oldValue = null;
                        break;
                    }
                }
            } finally {
                // 释放锁
                unlock();
            }
            return oldValue;
        }

get方法

 public V get(Object key) {
        Segment<K,V> s; // manually integrate access methods to reduce overhead
        HashEntry<K,V>[] tab;
        int h = hash(key);
        long u = (((h >>> segmentShift) & segmentMask) << SSHIFT) + SBASE;
        if ((s = (Segment<K,V>)UNSAFE.getObjectVolatile(segments, u)) != null &&
            (tab = s.table) != null) {
            for (HashEntry<K,V> e = (HashEntry<K,V>) UNSAFE.getObjectVolatile
                     (tab, ((long)(((tab.length - 1) & h)) << TSHIFT) + TBASE);
                 e != null; e = e.next) {
                K k;
                if ((k = e.key) == key || (e.hash == h && key.equals(k)))
                    return e.value;
            }
        }
        return null;
    }

size方法

public int size() {
        // Try a few times to get accurate count. On failure due to
        // continuous async changes in table, resort to locking.
        final Segment<K,V>[] segments = this.segments;
        int size;
        boolean overflow; // true if size overflows 32 bits
        long sum;         // sum of modCounts
        long last = 0L;   // previous sum
        int retries = -1; // first iteration isn't retry
        try {
            for (;;) {
                // RETRIES_BEFORE_LOCK默认为2，说明先尝试3次，如果其中连续两次结果一样则直接返回。如果没有则对所有分段加锁，在计算。随后解锁
                if (retries++ == RETRIES_BEFORE_LOCK) {
                    for (int j = 0; j < segments.length; ++j)
                        ensureSegment(j).lock(); // force creation
                }
                sum = 0L;
                size = 0;
                overflow = false;
                for (int j = 0; j < segments.length; ++j) {
                    Segment<K,V> seg = segmentAt(segments, j);
                    if (seg != null) {
                        sum += seg.modCount;
                        int c = seg.count;
                        // 如果大小溢出的话标识位设为true
                        if (c < 0 || (size += c) < 0)
                            overflow = true;
                    }
                }
                // last用来记录上次循环的计算结果，sum为本次循环的计算结果。如果连续两次结果一致则退出循环
                if (sum == last)
                    break;
                last = sum;
            }
        } finally {
            // 如果重试次数超过加锁所需的次数，则对所有分段解锁
            if (retries > RETRIES_BEFORE_LOCK) {
                for (int j = 0; j < segments.length; ++j)
                    segmentAt(segments, j).unlock();
            }
        }
        // 如果溢出则返回Integer.MAX_VALUE，否则返回正确size
        return overflow ? Integer.MAX_VALUE : size;
    }

ConcurrentHashMap1.8的数据结构

未完待续

ConcurrentHashMap与hashtable的区别

未完待续