Java 数据结构之 HashMap

JDK 1.7

HashMap

HashMap:了解其数据结构、hash 冲突如何解决(链表和红黑树)、扩容时机、扩容时避免 rehash 的优化

HashMap 可以存储 null 键和 null 值,

代码分析

package top.waterlaw.array;

import java.util.HashMap;

public class HashMapTest {


    public static void main(String[] args) {
        HashMap<String, String> m = new HashMap<>(8);
        m.put(null, null);
        System.out.println(m.get(null));
    }
}

1.7 版本的 hashmap 结构如下

 * @author  Doug Lea
 * @author  Josh Bloch
 * @author  Arthur van Hoff
 * @author  Neal Gafter
 * @see     Object#hashCode()
 * @see     Collection
 * @see     Map
 * @see     TreeMap
 * @see     Hashtable
 * @since   1.2
 */

public class HashMap<K,V>
    extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable
{
    // 默认数组大小
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
    // 最大数组大小
    static final int MAXIMUM_CAPACITY = 1 << 30;
    // 默认加载因子,put 时判断数组长度超过初始长度的比例即开始扩容
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    // 不扩容时为空数组
    static final Entry<?,?>[] EMPTY_TABLE = {};
    // 存放 Map 元素的数组, Entry 是一个链表, 有 next 指针
    transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
    // 当前数组长度,每次 put 会加 1
    transient int size;
    // 下次扩容时的数组大小
    int threshold;
    // 实际的加载因子
    final float loadFactor;
    // 数组的修改次数
    transient int modCount;
    // 扩容后数组最大的大小
    static final int ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE;
    // 未知, 先不管, 对初始容量不超过 Integer.MAX_VALUE 没影响
    transient int hashSeed = 0;
    // 存放元素的数组, 这个结构就是个链表
    static class Entry<K,V> implements Map.Entry<K,V> {
        final K key;
        V value;
        Entry<K,V> next;
        int hash;

        /**
         * Creates new entry.
         */
        Entry(int h, K k, V v, Entry<K,V> n) {
            value = v;
            next = n;
            key = k;
            hash = h;
        }
       // ...
    }
}

我们来分析下原始的三行代码,

HashMap<String, String> m = new HashMap<>(8);

构造函数有三个, 实际调用的是最后一个 public HashMap(int initialCapacity, float loadFactor)

    public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }
    public HashMap() {
        this(DEFAULT_INITIAL_CAPACITY, 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;
        threshold = initialCapacity;
        init(); // 空函数
    }

可见这个构造函数除了设置初始参数 loadFactor 和 threshold, 什么都没干。

再来看 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;
    }

如果 table 为空, table 默认就是空(EMPTY_TABLE), 初始化一个数组,inflateTable(threshold);

    private void inflateTable(int toSize) {
        // Find a power of 2 >= toSize
        // 寻找一个大于等于 toSize 的 2 的 n 次方
        int capacity = roundUpToPowerOf2(toSize);

        threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
        table = new Entry[capacity];
        initHashSeedAsNeeded(capacity);
    }

hashmap 采用数组加链表的方法, 将 key 的 hashcode 值一样的元素放在同一个链表中,相当于把数组比较平均地分成 table.length 个。

对 key 为 null 做特别处理...

int hash = hash(key); // 这行代码利用到扰动技术,防止 hash 冲突频繁
int i = indexFor(hash, table.length); // 根据 key 的 hash 值寻找对应的链表

indexFor 就一行代码, hashcode & table.length -1, 因为 table.length = 2^n, 所以相当于

hashcode & 0x111111(n 个 1) 也即取 hashcode 二进制中的最后 n 位低位。

    static int indexFor(int h, int length) {
        // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
        return h & (length-1);
    }

for 循环则遍历, 如果存在 hash 值一样且 key 内容一样的元素, 则更新该元素对应的 value 值。

否则, 添加一个新元素

addEntry(hash, key, value, i);

addEntry 方法会先判断当前 size 是否大于等于 threshold, 如果是则进行 2 倍扩容 resize(2 * table.length)。

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

        createEntry(hash, key, value, bucketIndex);
    }

扩容后再添加新元素 createEntry(hash, key, value, bucketIndex)

resize 则是新建一个 2 倍原来长度的数组, 然后 transfer 函数将原来的数组 copy 到新数组。

    void resize(int newCapacity) {
        Entry[] oldTable = table;
        int oldCapacity = oldTable.length;
        if (oldCapacity == MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return;
        }

        Entry[] newTable = new Entry[newCapacity];
        transfer(newTable, initHashSeedAsNeeded(newCapacity));
        table = newTable;
        threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
    }

这里 transfer 用到的是将旧链表上的元素添加到新数组对应链表中, 这里使用的是反转原来的链表

    void transfer(Entry[] newTable, boolean rehash) {
        int newCapacity = newTable.length;
        for (Entry<K,V> e : table) {
            while(null != e) {
                Entry<K,V> next = e.next;
                if (rehash) {
                    e.hash = null == e.key ? 0 : hash(e.key);
                }
                int i = indexFor(e.hash, newCapacity);
                // 这个是反转的写法 start, jdk1.7 默认的实现
                e.next = newTable[i];
                newTable[i] = e;
                e = next;
                // 反转 end
                // 这个是不反转的写法 start, 不反转效率低
                Entry<K,V> newEntry = newTable[i];
                e.next = null;
                if(newEntry != null){
                    while(true){
                        if(newEntry.next == null){
                            newEntry.next = e;
                            break;
                        }
                        newEntry = newEntry.next;
                    }
                 }else{
                     newTable[i] = e;
                 } 
                e = next;
                // 不反转 end
            }
        }
    }

最重要的 transfer 方法在多线程环境中会带来死循环的问题,如 map 中已有一条链, 扩容后为两条链

A-->B-->C

正常扩容后

B-->A

C

线程 A 和线程 B 同时 put 到达扩容点, A, B 同时进行扩容, 由于是对旧的 table 进行操作, 且两个线程都未能更新旧的 table 时,

A 线程:

e = A
next = B
==================
newTable[i]=> null

B 线程:

e = A
next = B
==================
newTable[i]=> null

假设 B 线程获得 CPU 执行时间

e = B
next = C
==================
newTable[i]=> A

当 B 线程在如下这部卡住时, B.next = A, A.next = null

e = C
next = null
==================
newTable[i]=> B->A

如果此时 A 线程获得 CPU 执行时间

e = B
next = A
=================
newTable[i]=>A
e = A
next = null
=================
newTable[i]=>B->A
e = null
next = null
=================
newTable[i]=>A->B->A

最后数组中一条链表变成 A->B->A, 当执行 get 遍历 map 时正好卡在该链表时, 会出现死循环。

我们来看下 get 函数

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

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

先根据 key 的 hash 值定位到链表, 然后判断元素的 hash 和 key 是否与给定的一样

    final Entry<K,V> getEntry(Object key) {
        if (size == 0) {
            return null;
        }

        int hash = (key == null) ? 0 : hash(key);
        for (Entry<K,V> e = table[indexFor(hash, table.length)];
             e != null;
             e = e.next) {
            Object k;
            if (e.hash == hash &&
                ((k = e.key) == key || (key != null && key.equals(k))))
                return e;
        }
        return null;
    }

如果扩容时出现 A->B->A, 那么 for 循环就会卡住, 无法中止。

新元素添加到链表头部

void createEntry(int hash, K key, V value, int bucketIndex) 的实现是将新元素加到链表的头部,将新元素加到链表的头部会导致死循环问题,这一点在 JDK1.8 改进为添加新元素到链表尾部。

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

ConcurrentHashMap

ConcurrentHashMap 不可以存储 null 键和 null 值

JDK7 分段锁技术 Segment

static final class Segment<K,V> extends ReentrantLock implements Serializable

jdk7 的 ConcurrentHashMap 源代码写的太不雅观了, jdk 8 写的比较好。

JDK1.8

HashMap

HashMap 可以存储 null 键和 null 值,

代码分析

package top.waterlaw.array;

import java.util.HashMap;

public class HashMapTest {


    public static void main(String[] args) {
        HashMap<String, String> m = new HashMap<>(8);
        m.put(null, null);
        System.out.println(m.get(null));
    }
}

1.8 版本的 hashmap 结构如下, 接着我们只讲和 jdk7 不同的部分, 当然相同部分也会提及

 * @author  Doug Lea
 * @author  Josh Bloch
 * @author  Arthur van Hoff
 * @author  Neal Gafter
 * @see     Object#hashCode()
 * @see     Collection
 * @see     Map
 * @see     TreeMap
 * @see     Hashtable
 * @since   1.2
 */
public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable {

    private static final long serialVersionUID = 362498820763181265L;
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    // 数组元素个数超过此值则使用红黑树
    static final int TREEIFY_THRESHOLD = 8;
    static final int MIN_TREEIFY_CAPACITY = 64;
    // 和 jdk7 同样的链表结构,当数组元素小于 TREEIFY_THRESHOLD 时使用链表,跟 jdk7 没区别
    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;
        }
        //...
    }

}

我们来分析下原始的三行代码,

HashMap<String, String> m = new HashMap<>(8);

构造函数有三个, 实际调用的是最后一个 public HashMap(int initialCapacity, float loadFactor)

    public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }
    public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
    }
    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);
    }

tableSizeFor(initialCapacity) 和 JDK7 中 put 方法中的 inflateTable(threshold) 功能一样, 显然 threshold 始终为 2 的 n 次方, 这点 JDK8 的代码给人的感觉更清晰, 直接在构造方法中算最接近 initialCapacity 的 2 ^n

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;
        @SuppressWarnings({"rawtypes","unchecked"})
            Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        table = newTab;
        if (oldTab != null) {
            for (int j = 0; j < oldCap; ++j) {
                Node<K,V> e;
                if ((e = oldTab[j]) != null) {
                    oldTab[j] = null;
                    if (e.next == null)
                        newTab[e.hash & (newCap - 1)] = e;
                    else if (e instanceof TreeNode)
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    else { // preserve order
                        Node<K,V> loHead = null, loTail = null;
                        Node<K,V> hiHead = null, hiTail = null;
                        Node<K,V> next;
                        do {
                            next = e.next;
                            if ((e.hash & oldCap) == 0) {
                                if (loTail == null)
                                    loHead = e;
                                else
                                    loTail.next = e;
                                loTail = e;
                            }
                            else {
                                if (hiTail == null)
                                    hiHead = e;
                                else
                                    hiTail.next = e;
                                hiTail = e;
                            }
                        } while ((e = next) != null);
                        if (loTail != null) {
                            loTail.next = null;
                            newTab[j] = loHead;
                        }
                        if (hiTail != null) {
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        return newTab;
    }

我们只关心下面这部分代码

                        do {
                            next = e.next;
                            // oldCap 为扩容前数组长度
                            if ((e.hash & oldCap) == 0) {
                                // 如果扩容前数组有n位, e 的 hashcode 第n+1位为0则进入此代码块
                                if (loTail == null)
                                    loHead = e;
                                else
                                    loTail.next = e;
                                loTail = e;
                            }
                            else {
                                // 如果扩容前数组有n位, e 的 hashcode 第n+1位不为0则进入此代码块
                                if (hiTail == null)
                                    hiHead = e;
                                else
                                    hiTail.next = e;
                                hiTail = e;
                            }
                        } while ((e = next) != null);
                        if (loTail != null) {
                            loTail.next = null;
                            // 元素的 hashcode 第n+1位为0,保持原来位置不变
                            newTab[j] = loHead;
                        }
                        if (hiTail != null) {
                            hiTail.next = null;
                            // 元素的 hashcode 第n+1位为1,在原来位置上再移动 oldCap=2^n
                            newTab[j + oldCap] = hiHead;
                        }

我们来看下 put 部分的代码吧

    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            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);
                        // 元素大于 8 个转为红黑树
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

可以看到新元素是添加到链表尾部的,这一点和 JDK1.7 是不同的, 而且若链表长度大于 8, 则转为红黑树存储。

而且 JDK1.8 是将元素添加到链表后才会扩容,这点和 JDK1.7 先判断容量是否扩容再添加新元素是不一样的。

ConcurrentHashMap

ConcurrentHashMap 不可以存储 null 键和 null 值

JDK1.8 的 put 使用 synchronized 关键字和 CAS 操作以实现扩容, 同时还支持多线程扩容。

先来看下 ConcurrentHashMap 类结构

public class ConcurrentHashMap<K,V> extends AbstractMap<K,V>
    implements ConcurrentMap<K,V>, Serializable {
    private static final long serialVersionUID = 7249069246763182397L;
    private static final int MAXIMUM_CAPACITY = 1 << 30;
    private static final int DEFAULT_CAPACITY = 16;
    static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
    // 并发级别, 允许同时多少个线程同时访问
    private static final int DEFAULT_CONCURRENCY_LEVEL = 16;
    private static final float LOAD_FACTOR = 0.75f;
    static final int TREEIFY_THRESHOLD = 8;    
    static final int UNTREEIFY_THRESHOLD = 6;
    static final int MIN_TREEIFY_CAPACITY = 64;    
    private static final int MIN_TRANSFER_STRIDE = 16;    
    private static int RESIZE_STAMP_BITS = 16;
    private static final int MAX_RESIZERS = (1 << (32 - RESIZE_STAMP_BITS)) - 1;
    private static final int RESIZE_STAMP_SHIFT = 32 - RESIZE_STAMP_BITS;

    static final int MOVED     = -1; // hash for forwarding nodes
    static final int TREEBIN   = -2; // hash for roots of trees
    static final int RESERVED  = -3; // hash for transient reservations
    static final int HASH_BITS = 0x7fffffff; // usable bits of normal node hash

    /** Number of CPUS, to place bounds on some sizings */
    static final int NCPU = Runtime.getRuntime().availableProcessors();

    static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        volatile V val; // volatile 属性
        volatile Node<K,V> next; // volatile 属性

        Node(int hash, K key, V val, Node<K,V> next) {
            this.hash = hash;
            this.key = key;
            this.val = val;
            this.next = next;
        }
        //..
    }
    static final class ForwardingNode<K,V> extends Node<K,V> {
        final Node<K,V>[] nextTable; // table 的一个拷贝
        ForwardingNode(Node<K,V>[] tab) {
            // hash 值默认为 MOVED(-1)
            super(MOVED, null, null, null);
            this.nextTable = tab;
        }

        Node<K,V> find(int h, Object k) {
            // loop to avoid arbitrarily deep recursion on forwarding nodes
            outer: for (Node<K,V>[] tab = nextTable;;) {
                Node<K,V> e; int n;
                if (k == null || tab == null || (n = tab.length) == 0 ||
                    (e = tabAt(tab, (n - 1) & h)) == null)
                    return null;
                for (;;) {
                    int eh; K ek;
                    if ((eh = e.hash) == h &&
                        ((ek = e.key) == k || (ek != null && k.equals(ek))))
                        return e;
                    if (eh < 0) {
                        if (e instanceof ForwardingNode) {
                            tab = ((ForwardingNode<K,V>)e).nextTable;
                            continue outer;
                        }
                        else
                            return e.find(h, k);
                    }
                    if ((e = e.next) == null)
                        return null;
                }
            }
        }
    }    
    transient volatile Node<K,V>[] table;
    // 扩容时放到这里
    private transient volatile Node<K,V>[] nextTable;
    private transient volatile long baseCount;
    // 扩容标志
    /* 
     * Hash表的初始化和调整大小的控制标志。为负数,Hash 表正在初始化或者扩容;
     * (-1表示正在初始化,-N 表示有 N-1 个线程在进行扩容)
     * 否则,当表为null时,保存创建时使用的初始化大小或者默认0;
     * 初始化以后保存下一个调整大小的尺寸。
     */
    private transient volatile int sizeCtl;

    /**
     * The next table index (plus one) to split while resizing.
     */
    private transient volatile int transferIndex;    

Node的一个子类 ForwardingNodes 也是一个重要的结构,它主要作为一个标记,在处理并发时起着关键作用,有了 ForwardingNodes,也是 ConcurrentHashMap 有了分段的特性,提高了并发效率。

构造方法

    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);
        // sizeCtl 在构造方法中表示最接近 initialCapacity / loadFactor 的 2^x 
        this.sizeCtl = cap;
    }

sizeCtl 这个参数起到一个控制标志的作用,在 ConcurrentHashMap 初始化和扩容都有用到。 ConcurrentHashMap 构造函数只是设置了一些参数,并没有对 Hash 表进行初始化。当在从插入元素时,才会初始化 Hash 表。在开始初始化的时候,首先判断 sizeCtl 的值,如果 sizeCtl < 0,说明有线程在初始化,当前线程便放弃初始化操作。否则,将 SIZECTL 设置为-1,Hash 表进行初始化。初始化成功以后,将 sizeCtl 的值设置为下次扩容时机的容量。

    private final Node<K,V>[] initTable() {
        Node<K,V>[] tab; int sc;
        while ((tab = table) == null || tab.length == 0) {
            // sizeCtl 小于0,正在初始化
            if ((sc = sizeCtl) < 0)
                // 调用 yield()函数,使线程让出 CPU 资源
                Thread.yield(); // lost initialization race; just spin
            // 设置 SIZECTL 为-1,表示正在初始化
            else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
                try {
                    if ((tab = table) == null || tab.length == 0) {
                        int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
                        // 区别于HashMap:n 为最接近 initialCapacity / loadFactor 的 2^x
                        // sizeCtl 变量做了临时工,帮忙设置初始化数组大小
                        @SuppressWarnings("unchecked")
                        Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
                        table = tab = nt;
                        // n-(1/4)n,即默认的容量(n * loadFactor)                        
                        sc = n - (n >>> 2);
                    }
                } finally {
                    // 初始化成功以后,将 sizeCtl 的值设置为当前的容量值
                    sizeCtl = sc;
                }
                break;
            }
        }
        return tab;
    }

put 方法

如果 key 或者 value为 null,则抛出空指针异常;

如果 table 为 null 或者 table 的长度为0,则初始化 table,调用 initTable() 方法。

计算当前键值的索引位置,如果 Hash 表中当前节点为 null,则将元素直接插入。(注意,这里使用的就是前面锁说的 CAS 操作)

如果当前位置的节点元素的 hash 值为-1,说明这是一个 ForwaringNodes 节点,即正在进行扩容。那么当前线程加入扩容。

当前节点不为 null,对当前节点加锁,将元素插入到当前节点。在 Java8 中,当节点长度大于8时,就将节点转为树的结构。

    /** Implementation for put and putIfAbsent */
    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) {
                // f 所在的链表不存在,则使用 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)
                // f 节点所在的链表正在扩容, 帮助其扩容
                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;
    }

扩容机制

    private final void addCount(long x, int check) {
        // ...
        if (check >= 0) {
            Node<K,V>[] tab, nt; int n, sc;
            while (s >= (long)(sc = sizeCtl) && (tab = table) != null &&
                   (n = tab.length) < MAXIMUM_CAPACITY) {
                int rs = resizeStamp(n);
                if (sc < 0) {
                    if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
                        sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
                        transferIndex <= 0)
                        break;
                    if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
                        transfer(tab, nt);
                }
                else if (U.compareAndSwapInt(this, SIZECTL, sc,
                                             (rs << RESIZE_STAMP_SHIFT) + 2))
                    //- 开始扩容
                    transfer(tab, null);
                s = sumCount();
            }
        }
    }

当 ConcurrentHashMap 中元素的数量达到 cap * loadFactor 时,就需要进行扩容。扩容主要通过 transfer() 方法进行,当有线程进行 put 操作时,如果正在进行扩容,可以通过 helpTransfer() 方法加入扩容。也就是说,ConcurrentHashMap 支持多线程扩容,多个线程处理不同的节点。

开始扩容,首先计算步长,也就是每个线程分配到的扩容的节点数(默认是16)。这个值是根据当前容量和 CPU 的数量来计算 (stride = (NCPU > 1) ? (n >>> 3) / NCPU : n),最小是16。

接下来初始化临时的 Hash 表 nextTable,如果 nextTable 为 null,初始化 nextTable 长度为原来的2倍;

通过计算出的步长开始遍历 Hash 表,其中坐标是通过一个原子操作(compareAndSetInt)记录。通过一个 while 循环,如果在一个线程的步长内便跳过此节点。否则转下一步;

如果当前节点为空,之间将此节点在旧的Hash表中设置为一个 ForwardingNodes 节点,表示这个节点已经被处理过了。

如果当前节点元素的 hash 值为 MOVED(f.hash == -1),表示这是一个 ForwardingNodes 节点,则直接跳过。否则,开始重新处理节点;

对当前节点进行加锁,在这一步的扩容操作中,重新计算元素位置的操作与 HashMap 中是一样的,即当前元素键值的 hash 与长度进行&操作,如果结果为0则保持位置不变,为1位置就是 i+n。其中进行处理的元素是最后一个符合条件的元素,所以扩容后可能是一种倒序,但在 Hash 表中这种顺序也没有太大的影响。

最后如果是链表结构直接获得高位与低位的新链表节点,如果是树结构,同样计算高位与低位的节点,但是需要根据节点的长度进行判断是否需要转化为树的结构。

    /**
     * Moves and/or copies the nodes in each bin to new table. See
     * above for explanation.
     */
    private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) {
        int n = tab.length, stride;
        // 根据长度和 CPU 的数量计算步长,最小是 16
        if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE)
            stride = MIN_TRANSFER_STRIDE; // subdivide range
        if (nextTab == null) {            // initiating
            try {
                @SuppressWarnings("unchecked")
                // 初始化新的 Hash 表,长度为原来的2倍
                Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n << 1];
                nextTab = nt;
            } catch (Throwable ex) {      // try to cope with OOME
                sizeCtl = Integer.MAX_VALUE;
                return;
            }
            nextTable = nextTab;
            transferIndex = n;
        }
        int nextn = nextTab.length;
        // 初始化 ForwardingNodes 节点
        ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab);
        boolean advance = true; // 是否跨过节点的标记
        boolean finishing = false; // to ensure sweep before committing nextTab
        for (int i = 0, bound = 0;;) {
            Node<K,V> f; int fh;
            // 根据步长判断是否需要跨过节点
            while (advance) {
                int nextIndex, nextBound;
                // 到达没有处理的节点下标
                if (--i >= bound || finishing)
                    advance = false;
                else if ((nextIndex = transferIndex) <= 0) {
                    // 所有节点都已经接收处理
                    i = -1;
                    advance = false;
                }
                else if (U.compareAndSetInt
                         (this, TRANSFERINDEX, nextIndex,
                          nextBound = (nextIndex > stride ?
                                       nextIndex - stride : 0))) {
                    // 更新下表 transferIndex,在步长的范围内都忽略
                    bound = nextBound;
                    i = nextIndex - 1;
                    advance = false;
                }
            }
            // 所有节点都被接收处理或者已经处理完毕
            if (i < 0 || i >= n || i + n >= nextn) {
                int sc;
                // 处理完毕
                if (finishing) {
                    nextTable = null;
                    table = nextTab;
                    // 更新 sizeCtl
                    sizeCtl = (n << 1) - (n >>> 1);
                    return;
                }
                // 判断所有节点是否全部被处理
                if (U.compareAndSetInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {
                    if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)
                        return;
                    finishing = advance = true;
                    i = n; // recheck before commit
                }
            }
            // 如果节点为 null,直接标记为已接收处理
            else if ((f = tabAt(tab, i)) == null)
                advance = casTabAt(tab, i, null, fwd);
            // 键值的 hash 为-1,表示这是一个 ForwardingNodes 节点,已经被处理
            else if ((fh = f.hash) == MOVED)
                advance = true; // already processed
            else {
                // 对当前节点进行加锁
                synchronized (f) {
                    if (tabAt(tab, i) == f) {
                        Node<K,V> ln, hn;
                        if (fh >= 0) {
                            // 索引位置是否改变的标志
                            int runBit = fh & n;
                            Node<K,V> lastRun = f; // 最后一个元素
                            for (Node<K,V> p = f.next; p != null; p = p.next) {
                                int b = p.hash & n;
                                // 重新计算更新直到最后一个元素
                                if (b != runBit) {
                                    runBit = b;
                                    lastRun = p;
                                }
                            }
                            // runBit = 0,保持位置不变
                            if (runBit == 0) {
                                ln = lastRun;
                                hn = null;
                            }
                            // runBit = 1,位置时i+n
                            else {
                                hn = lastRun;
                                ln = null;
                            }
                            // 重新遍历节点元素
                            for (Node<K,V> p = f; p != lastRun; p = p.next) {
                                int ph = p.hash; K pk = p.key; V pv = p.val;
                                // 构建低位(位置不变)新的链表
                                if ((ph & n) == 0)
                                    ln = new Node<K,V>(ph, pk, pv, ln);
                                // 构建高位(i+n)新的链表
                                else
                                    hn = new Node<K,V>(ph, pk, pv, hn);
                            }
                            // 将新的链表设置到新的 Hash 表中相应的位置
                            setTabAt(nextTab, i, ln);
                            setTabAt(nextTab, i + n, hn);
                            // 将原来的 Hash 表中相应位置的节点设置为 ForwardingNodes 节点
                            setTabAt(tab, i, fwd);
                            advance = true;
                        }
                        // 如果节点是树的结构
                        else if (f instanceof TreeBin) {
                            TreeBin<K,V> t = (TreeBin<K,V>)f;
                            TreeNode<K,V> lo = null, loTail = null;
                            TreeNode<K,V> hi = null, hiTail = null;
                            int lc = 0, hc = 0;
                            for (Node<K,V> e = t.first; e != null; e = e.next) {
                                int h = e.hash;
                                TreeNode<K,V> p = new TreeNode<K,V>
                                    (h, e.key, e.val, null, null);
                                // 同样的方式计算新的索引位置
                                if ((h & n) == 0) {
                                    // 构建新的链表结构
                                    if ((p.prev = loTail) == null)
                                        lo = p;
                                    else
                                        loTail.next = p;
                                    loTail = p;
                                    ++lc;
                                }
                                else {
                                // 构建新的链表结构
                                    if ((p.prev = hiTail) == null)
                                        hi = p;
                                    else
                                        hiTail.next = p;
                                    hiTail = p;
                                    ++hc;
                                }
                            }
                            // 判断是否需要转化为树
                            ln = (lc <= UNTREEIFY_THRESHOLD) ? untreeify(lo) :
                                (hc != 0) ? new TreeBin<K,V>(lo) : t;
                            // 判断是否需要转化为树
                            hn = (hc <= UNTREEIFY_THRESHOLD) ? untreeify(hi) :
                                (lc != 0) ? new TreeBin<K,V>(hi) : t;
                            // 将新的链表设置到新的 Hash 表中相应的位置
                            setTabAt(nextTab, i, ln);
                            setTabAt(nextTab, i + n, hn);
                            // 将原来的 Hash 表中相应位置的节点设置为 ForwardingNodes 节点
                            setTabAt(tab, i, fwd);
                            advance = true;
                        }
                    }
                }
            }
        }
    }

总结

总结下大概如下:

两个版本 HashMap 共同点

  • 底层数组+链表/底层数组+链表+红黑树 实现
  • 初始 size 为 16,扩容:newsize = oldsize*2,size 一定为 2 的 n 次幂
  • 当 Map 中元素总数超过 Entry 数组的 75%,触发扩容操作,为了减少链表长度,元素分配更均匀
  • 计算 index 方法:index = hash & (tab.length – 1)

HashMap 的初始值还要考虑加载因子:

  • 哈希冲突:若干 Key 的哈希值按数组大小取模后,如果落在同一个数组下标上,将组成一条 Entry 链,对 Key 的查找需要遍历 Entry 链上的每个元素执行 equals() 比较。
  • 加载因子:为了降低哈希冲突的概率,默认当 HashMap 中的键值对达到数组大小的75%时,即会触发扩容。因此,如果预估容量是 100,即需要设定100/0.75=134的数组大小。
  • 空间换时间:如果希望加快 Key 查找的时间,还可以进一步降低加载因子,加大初始大小,以降低哈希冲突的概率。

两个版本 HashMap 区别

JDK1.7

  • 底层数组+链表

  • 扩容针对整个 Map,每次扩容时,原来数组中的元素依次重新计算存放位置,并重新插入,需要 rehash

  • 插入元素前就判断该不该扩容
  • 新元素插入在链表头部,扩容时会造成其他线程 get 死循环
  • hash 函数效率较低

JDK1.8

  • 底层数组+链表+红黑树

  • 扩容针对整个 Map,每次扩容时,原来数组中的元素依次重新计算存放位置,并重新插入, 不需要 rehash, 若扩容后数组大小为 2^(N+1), 则原来 hash 值第 N+1 位为 0 的元素不需要动,N+1位为1的右移 2^N 个位置

  • 插入元素后才判断该不该扩容,有可能无效扩容
  • 新元素插入在链表尾部,扩容时数据可能会丢失
  • 改进 hash 函数

两个版本 ConccurentHashMap 区别

JDK1.7

  • 采用 segment 分段锁(ReentrantLock)实现线程安全

JDK1.8

  • 采用 node(Node + ForwardingNode),锁住 node 来实现减小锁粒度,使用 synchronized + CAS 操作来确保 node 的一些操作的原子性
  • 设计了 MOVED 状态,支持多线程扩容,当 resize 的中过程中 线程2 还在 put 数据,线程2会帮助 resize
  • sizeCtl 的不同值来代表不同含义,起到了控制的作用

两个版本 HashMap 和 ConccurentHashMap 区别

JDK1.7

  • HashMap 线程不安全, ConccurentHashMap 线程不安全
  • HashMap 使用 Entry 存放元素,ConccurentHashMap 使用 Segment 数组存放元素

JDK1.8

  • HashMap 线程不安全, ConccurentHashMap 线程不安全
  • HashMap 初始化数组大小为最接近 initialCapacity 的 2 的 N 次方, ConccurentHashMap 初始化数组大小为最接近 initialCapacity/loadFactor + 1 的 2 的 N 次方

发表评论

评论内容
 

评论列表, 共 0 条评论