哈希表的进化，从HashMap到ConcurrentHashMap

Posted on | In , | 次阅读

引言

我们熟知，一般数组和链表不能满足我们常用的业务场景，比如说，我想存一种key-val类型的数据结构，其实来说，ArrayList也可以看成一种简单的哈希结构，只是key只能取int类型。那么为什么要有哈希结构呢？就是为了弥补数组与链表之间查询与修改的性能存在问题。

基于数组的顺序表ArrayList 由于占用的是一块连续的内存，故查询修改较快，插入删除较慢。基于Node节点的双向链表LinkedList 由于当前节点指向下一节点的方式，各个节点在内存中不是连续的，故插入删除较快，查询修改较慢。

为了弥补这两种数据结构的短板，哈希结构的数据类型应运而生，最先开始的是Hashtable，由于当时考虑到线程安全，这个类一上来就加synchronized锁，加锁必然消耗性能，但是，我们更多场景的是不需要锁的，所以才有了HashMap。HashMap是一个性能很不错的哈希表，但是线程不安全的。后来又有了线程安全的ConcurrentHashMap，并且他俩在jdk1.8进行了一次较大的升级，接下来的文章，我们就根据jdk1.7 和 jdk1.8 的源码来分析一下 HashMap 和ConcurrenthashMap。

HashMap

jdk1.7

结构

初始化
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public HashMap() {
    this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);  -- 默认初始化大小16、负载因子0.75
}

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

    this.loadFactor = loadFactor;
    threshold = initialCapacity;
    init();
}
实例变量
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

static final int MAXIMUM_CAPACITY = 1 << 30;

static final float DEFAULT_LOAD_FACTOR = 0.75f;

static final Entry<?,?>[] EMPTY_TABLE = {};

transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;

transient int size;

// If table == EMPTY_TABLE then this is the initial capacity at which the
// table will be created when inflated.
int threshold;

final float loadFactor;

java1.7 的hashMap结构如下图：

Entry结构
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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;
    }
}

put方法

思考：往HashMap 添加1000个元素需要扩容多少次？ (Add first)—> 16 —>以后都是两倍的扩容210=1024 ,还需要6次扩容

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public V put(K key, V value) {
    if (table == EMPTY_TABLE) {
        inflateTable(threshold);   // 默认方式扩容
    }
    if (key == null)
        return putForNullKey(value);    // key值为空处理
    int hash = hash(key);								// 找到key的hash值
    int i = indexFor(hash, table.length);   // 找到位于哪个哈希槽，即数组的下标
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        Object k;
        // 遍历哈希桶里的元素，如果有相等的key，直接替换val，返回原来的val
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {   
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }

    modCount++;  
  	// 否则，将元素插入下标为i的哈希桶
    addEntry(hash, key, value, i);   
    return null;
}

addEntry方法

1
2
3
4
5
6
7
8
9
10
11
12
13
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方法

1
2
3
4
5
6
7
8
// 插入元素时，应插入哈希桶的头部，而不是尾部
void createEntry(int hash, K key, V value, int bucketIndex) {
		// 取出槽里的元素
    Entry<K,V> e = table[bucketIndex];    // （第一处）
  	// 将当前新生成的Entry放在槽里，next节点指向之前槽里的元素
    table[bucketIndex] = new Entry<>(hash, key, value, e);
    size++;
}

resize方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void resize(int newCapacity) {
    Entry[] oldTable = table;
    // 原数组的长度 
    int oldCapacity = oldTable.length;
  	// 注意MAXIMUM_CAPACITY=1 << 30，如果1<<31 则成 Intager 的最小值：-2147483648
    if (oldCapacity == MAXIMUM_CAPACITY) {
        threshold = Integer.MAX_VALUE;
        return;
    }

  	// 新建数组
    Entry[] newTable = new Entry[newCapacity]; 						   //（第四处）
  	// 根据hash重新定位元素下标，从旧表迁移到新表
    transfer(newTable, initHashSeedAsNeeded(newCapacity));   //（第二处）
  	// 赋值内部数组（在此步骤完成前，旧表依然可以添加元素，导致数据丢失）
    table = newTable;																				 //（第三处）
  	// 修改阀值
    threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}

get方法

1
2
3
4
5
6
7
public V get(Object key) {
    if (key == null)
        return getForNullKey();
    Entry<K,V> entry = getEntry(key);

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

getEntry方法

1
2
3
4
5
6
7
8
9
10
11
12
13
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;
}

hash方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
final int hash(Object k) {
    int h = hashSeed;
    if (0 != h && k instanceof String) {
        return sun.misc.Hashing.stringHash32((String) k);
    }

    h ^= k.hashCode();

    // This function ensures that hashCodes that differ only by
    // constant multiples at each bit position have a bounded
    // number of collisions (approximately 8 at default load factor).
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

indexFor方法

1
2
3
4
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);
}

remove(key)方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
public V remove(Object key) {
    Entry<K,V> e = removeEntryForKey(key);
    return (e == null ? null : e.value);
}

final Entry<K,V> removeEntryForKey(Object key) {
    if (size == 0) {
        return null;
    }
    int hash = (key == null) ? 0 : hash(key);
    int i = indexFor(hash, table.length);
  	// 找到位于哪个桶
    Entry<K,V> prev = table[i];
    Entry<K,V> e = prev;

    while (e != null) {
      	// next指向下一个节点
        Entry<K,V> next = e.next;
        Object k;
        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k)))) {
            modCount++;
            size--;
          	//  如果在桶里，则将下个节点放入桶里
            if (prev == e)
                table[i] = next;
            else
              	// 否则，前节点的next节点指向删除节点的next节点
                prev.next = next;
            e.recordRemoval(this);
            return e;
        }
      	// 不等的话，逐个遍历
        prev = e;
        e = next;
    }
    return e;
}

并发问题

对象丢失问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
public class MapApplication {
    private static Map hashMap = new HashMap();
    public static void main(String[] args) throws InterruptedException {

        MapApplication mp = new MapApplication();
        Thread1 t1 = mp.new Thread1();
        Thread2 t2 = mp.new Thread2();
        Thread thread1 = new Thread(t1);
        Thread thread2 = new Thread(t2);

        thread1.start();
        thread2.start();

        thread1.join();
        thread2.join();

        System.out.println(hashMap.size());

    }


    class Thread1 implements Runnable {

        @Override
        public void run() {
            for (int i = 1; i <= 100000; i++) {
                hashMap.put(i, i);
            }
        }
    }


    class Thread2 implements Runnable {

        @Override
        public void run() {
            for (int i = 100001; i <= 200000; i++) {
                hashMap.put(i, i);
            }
        }
    }
}

通过程序发现，当每个线程添加元素数据量在1000时，得到的结果并不是2000，而总是小于2000。

说明并发情况下，会导致数据丢失的问题。导致的原因之一是在createEntry方法中的第一处，一个线程的赋值被另一个线程的覆盖了。

同时在resize方法的第二处和第三处也会导致数据丢失。第二处遍历的时候如果有另一个线程将数据插入到已经遍历的桶里面，在步骤（第三处）赋值完也会导致数据丢失。

同时，如果两个线程同时进入到resize的（第四处）代码，newTable = new Entry[newCapacity]，由于是局部变量线程不可见，在resize完赋值之后会覆盖其他线程的操作，导致在“新表”中插入的元素无情的丢失。

原因总结

  • 并发赋值时被覆盖
  • 已遍历区间新增元素会丢失
  • “新表”被覆盖

当数据量在100000时，执行程序就不能永远退出，是因为扩容的时候导致死链的问题。

死链问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public class ResizeMapApplication {

    public static void main(String[] args) {

        Map hashMap = new HashMap();
        // 扩容的阀值是16*0.75=12
        // 第一次扩容发生put第13个元素时
        for (int i = 1; i <= 13; i++) {
            hashMap.put(new UserKey(), i);
        }
        Set<Map.Entry<Integer, Integer>> entrySet = hashMap.entrySet();
        for (Map.Entry<Integer, Integer> entry : entrySet) {
            System.out.println(entry.getKey() + "---" + entry.getValue());
        }
    }
}

class UserKey {
    @Override
    public int hashCode() {
        // 保证在同一个槽
        return 1;
    }

    @Override
    public boolean equals(Object obj) {
        // 保证不是相同的元素
        return false;
    }
}

根据源码可以追踪扩容前内部元素的情况

由于所有的元素都会位于table[1]的哈希桶里，所以只需跟踪table[1]的元素

扩容前：数组的长度为16，阀值为12

12—>11—>10 … … —>2—>1

扩容后：数组的长度为32，阀值为24

13—>1—>2—>3… —>11—>12

当两个线程同时进入resize方法的第二处时，会重新rehash每一个哈希桶里的元素，具体实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void transfer(Entry[] newTable, boolean rehash) {
    int newCapacity = newTable.length;
  	// 使用foreach遍历整个数组下标
    for (Entry<K,V> e : table) {
        // 如果槽上存在元素，则遍历哈希桶，直到e==null，退出循环
        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);
            e.next = newTable[i];
            newTable[i] = e;
            e = next;
        }
    }
}

产生问题的根源是next的指针被并发线程修改。

jdk1.8

在jdk1.8中，HashMap做了比较大的升级，关于升级的内容我们通过源码来验证一下。

  1. jdk1.7是先扩容，再插入元素。而jdk1.8是，先插入元素，再扩容。
  2. jdk1.7HashMap当链表长度过长时，存在遍历性能的问题。jdk1.8引入了红黑树，解决了该问题。
  3. jdk1.7扩容时，哈希桶里的元素会重新rehash，顺序会颠倒。而jdk1.8是不一样的。

结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

static final int MAXIMUM_CAPACITY = 1 << 30;

static final float DEFAULT_LOAD_FACTOR = 0.75f;

/**
 * The bin count threshold for using a tree rather than list for a
 * bin.  Bins are converted to trees when adding an element to a
 * bin with at least this many nodes. The value must be greater
 * than 2 and should be at least 8 to mesh with assumptions in
 * tree removal about conversion back to plain bins upon
 * shrinkage.
 */
static final int TREEIFY_THRESHOLD = 8;

/**
 * The bin count threshold for untreeifying a (split) bin during a
 * resize operation. Should be less than TREEIFY_THRESHOLD, and at
 * most 6 to mesh with shrinkage detection under removal.
 */
static final int UNTREEIFY_THRESHOLD = 6;

/**
 * The smallest table capacity for which bins may be treeified.
 * (Otherwise the table is resized if too many nodes in a bin.)
 * Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts
 * between resizing and treeification thresholds.
 */
static final int MIN_TREEIFY_CAPACITY = 64;

// jdk1.8 使用的是 Node节点，代替1.7的Entry,但叫法不一样，结构是一样的
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;
    }
}

put方法

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

hash方法

1
2
3
4
5
static final int hash(Object key) {
    int h;
    // 加入高位运算，到数组的length比较小的时候，保证高地位bit参到计算中
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

putVal方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
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)))){
          	// 如果key与哈希桶里的key相等，则找到了
            e = p;
        }else if (p instanceof TreeNode)
          	// 哈希槽是否是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);
                    // 如果链表的长度大于等于7（除去哈希槽的元素，由于加上了next指针，这时的长度已经是8了）
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                      	// 将链表转化成红黑树
                        treeifyBin(tab, hash);
                    break;
                }
                // 找到相同的key
                if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k)))){
                    break;
                }
              	// 指向next指针
                p = e;
            }
        }
        // 如果找到相同的key,返回原始val
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    // 判断size+1是否大于阀值
    if (++size > threshold)
      	// 大于的话就进行扩容
        resize();
    afterNodeInsertion(evict);
    return null;
}

可以看到，在jdk1.8中

  1. jdk1.8是，先插入元素，再扩容。
  2. 引入了红黑树，且哈希槽里放的是树的TreeNode结构
  3. 如果哈希桶是链表结构，长度不大于8的话，则追加的节点在链表的末尾。

到此，验证一、验证二 已经得到验证，现在来验证三。

resize方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
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) {
        // 数组不能超过1<<30
        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;
 		// 初始化新的table
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    // 扩容前的table不为空
    if (oldTab != null) {
      	// 逐个遍历哈希桶
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
          	// 哈希槽指针
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
              	// 哈希槽里只有一个元素，则重新hash即可
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
              	// 如果哈希槽是TreeNode节点，则按照树的方式处理
                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;
}

jdk1.8中在计算新位置的时候并没有跟1.7中一样重新进行hash运算，而是用了原位置+原数组长度这样一种很巧妙的方式，而这个结果与hash运算得到的结果是一致的，只是会更快。

get方法

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

getNode方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    if ((tab = table) != null && (n = tab.length) > 0 &&(first = tab[(n - 1) & hash]) != null) {
      	// 判断哈希槽里的元素
        if (first.hash == hash && ((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);
            do {
              	// 遍历链表的元素
                if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k)))){
                    return e;
                }
            } while ((e = e.next) != null);
        }
    }
    // 否则，返回 null 
    return null;
}

简单总结下 HashMap：无论是 1.7 还是 1.8 其实都能看出 JDK 没有对它做任何的同步操作，所以并发会出问题，甚至 1.7 中出现死循环导致系统不可用（1.8 已经修复死循环问题）

ConcurrentHashMap

jdk1.7

由于HashMap是线程不安全的，在多线程下会出现安全问题，故引入了ConcurrentHashMap，支持多并发的场景。

结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
static final int MIN_SEGMENT_TABLE_CAPACITY = 2;
    
static final int MAX_SEGMENTS = 1 << 16; // slightly conservative
// Mask value for indexing into segments. 
// The upper bits of a key's hash code are used to choose the segment.
final Segment<K,V>[] segments;
// Shift value for indexing within segments.
final int segmentMask;

final int segmentShift;
 static final class HashEntry<K,V> {
        final int hash;
        final K key;
        volatile V value;
        volatile HashEntry<K,V> next;

        HashEntry(int hash, K key, V value, HashEntry<K,V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }
}
static final class Segment<K,V> extends ReentrantLock implements Serializable {
   	transient volatile HashEntry<K,V>[] table;
  	transient int count;
  	transient int threshold;
  	final float loadFactor;
  	Segment(float lf, int threshold, HashEntry<K,V>[] tab) {
            this.loadFactor = lf;
            this.threshold = threshold;
            this.table = tab;
    }
  	// PUT方法
  	// REMOVE方法
}

java1.7 的ConcurentHashMap结构如下图：

初始化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
// 无参构造方法  默认值分别为：16，0.75，16
public ConcurrentHashMap() {
    this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR, DEFAULT_CONCURRENCY_LEVEL);
}

public ConcurrentHashMap(int initialCapacity,
                             float loadFactor, int concurrencyLevel) {
  			// 参数校验
        if (!(loadFactor > 0) || initialCapacity < 0 || concurrencyLevel <= 0)
            throw new IllegalArgumentException();
        if (concurrencyLevel > MAX_SEGMENTS)
            concurrencyLevel = MAX_SEGMENTS;
        // Find power-of-two sizes best matching arguments
        int sshift = 0;
        int ssize = 1;
        while (ssize < concurrencyLevel) {
            ++sshift;
            ssize <<= 1;
        }
        this.segmentShift = 32 - sshift;
        this.segmentMask = ssize - 1;
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        int c = initialCapacity / ssize;
        if (c * ssize < initialCapacity)
            ++c;
        int cap = MIN_SEGMENT_TABLE_CAPACITY;
        while (cap < c)
            cap <<= 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;
    }

get方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public V get(Object key) {
    Segment<K,V> s; // manually integrate access methods to reduce overhead
    HashEntry<K,V>[] tab;
    int h = hash(key);
  	// 根据hash找到哪个Segment
    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;
}

get方法是非常高效的，因为没有加锁。是通过HashEntry的value加了volatile修饰符，保证了内存的可见性。

put方法

1
2
3
4
5
6
7
8
9
10
11
12
13
public V put(K key, V value) {
    Segment<K,V> s;
    if (value == null)
        throw new NullPointerException();
    int hash = hash(key);
    int j = (hash >>> segmentShift) & segmentMask;
  	// 找到分段锁桶的位置
    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);
}

Segment.put方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
final V put(K key, int hash, V value, boolean onlyIfAbsent) {
  	// 尝试获取锁
    HashEntry<K,V> node = tryLock() ? null :
        scanAndLockForPut(key, hash, value);       // 获取失败，说明有线程竞争，则自旋获取锁（默认64）
    V oldValue;
    try {
        HashEntry<K,V>[] tab = table;
        // 找到哈希槽下标
        int index = (tab.length - 1) & hash;
        // 获取哈希桶
        HashEntry<K,V> first = entryAt(tab, index);
        // 遍历哈希桶里的元素
        for (HashEntry<K,V> e = first;;) {
            if (e != null) {
                K k;
              	// 遍历是否存在相同的key值
                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 {
              	// 遍历完发现没有相同的key,如果node节点不为空，直接将node节点的next指向哈希桶的第一个节点
                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
                  	// 重新放置HashEntry在桶里
                    setEntryAt(tab, index, node);
                ++modCount;
                count = c;
                oldValue = null;
                break;
            }
        }
    } finally {
        unlock();
    }
    return oldValue;
}

remove方法

1
2
3
4
5
6
public V remove(Object key) {
    int hash = hash(key);
    Segment<K,V> s = segmentForHash(hash);
  	// 注意这里传的value值是空
    return s == null ? null : s.remove(key, hash, null);
}

Segment.remove方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
final V remove(Object key, int hash, Object value) {
    // 尝试获取锁
    if (!tryLock())
      	// 阻塞性获取锁
        scanAndLock(key, hash);
    V oldValue = null;
    try {
        HashEntry<K,V>[] tab = table;
        int index = (tab.length - 1) & hash;
      	// 获取哈希槽
        HashEntry<K,V> e = entryAt(tab, index);
        HashEntry<K,V> pred = null;
        while (e != null) {
            K k;
          	// 下一个节点
            HashEntry<K,V> next = e.next;
            // 找到要删除的key
            if ((k = e.key) == key ||(e.hash == hash && key.equals(k))) {
                V v = e.value;
                // 这里在干嘛，应该是兼容指定value删除
                if (value == null || value == v || value.equals(v)) {
                  	// 如果哈希桶为空，置空
                    if (pred == null)
                        setEntryAt(tab, index, next);
                    else
                      	// 否则，指向pred下一个指针
                        pred.setNext(next);
                    ++modCount;
                    --count;
                  	// 返回原始val
                    oldValue = v;
                }
                break;
            }
            pred = e;
            e = next;
        }
    } finally {
        unlock();
    }
    return oldValue;
}

参考crossoverJie文章