03月
10

集合源码学习（1）

发表于 被 人浏览

map类相关知识点总结

主要关注map相关的源码

HashTable、HashMap、HashSet 、TreeMap…

HashTable

基于位桶+链表实现。

  • 继承Dictionary（陈旧）
  • 实现Cloneable，可被克隆
  • 实现Serializable，可被序列化

hash

1
2
3
int hash = key.hashCode();
//0x7FFFFFFF转换为10进制之后是Intger.MAX_VALUE,也就是2^31 - 1
int index = (hash & 0x7FFFFFFF) % tab.length;

很容易看出Hashtable的hash算法首先使得hash的值小于等于整型数的最大值，再通过%运算实现均匀散射。

==由于计算机是底层的运算是基于2进制的，所以HashMap的hash算法使用&运算代替%运算，在运算速度上明显HashMap的hash算法更优。==

为什么一般hashtable的桶数会取一个素数

属性

构造

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public Hashtable(int initialCapacity, float loadFactor) {
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal Load: "+loadFactor);

    if (initialCapacity==0)
        initialCapacity = 1;
    this.loadFactor = loadFactor;
    table = new Entry<?,?>[initialCapacity];
    threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
}

public Hashtable() {
    this(11, 0.75f);
}

Hashtable底层数组的长度可以为任意值，这就造成了当底层数组长度为合数的时候，Hashtable的hash算法散射不均匀，容易产生hash冲突。所以，可以清楚的看到Hashtable的默认构造函数底层数组长度为11（质数），至于为什么Hashtable的底层数组用质数较好，请参考博文；

方法

put

  • value不能为null
  • 线程安全
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
public synchronized V put(K key, V value) {
    // Make sure the value is not null
    if (value == null) {
        throw new NullPointerException();
    }

    // Makes sure the key is not already in the hashtable.
    Entry<?,?> tab[] = table;
    int hash = key.hashCode();
    int index = (hash & 0x7FFFFFFF) % tab.length;
    @SuppressWarnings("unchecked")
    Entry<K,V> entry = (Entry<K,V>)tab[index];
    for(; entry != null ; entry = entry.next) {
        if ((entry.hash == hash) && entry.key.equals(key)) {
            V old = entry.value;
            entry.value = value;
            return old;
        }
    }

    addEntry(hash, key, value, index);
    return null;
}

private void addEntry(int hash, K key, V value, int index) {
    modCount++;

    Entry<?,?> tab[] = table;
    if (count >= threshold) {
        // Rehash the table if the threshold is exceeded
        rehash();

        tab = table;
        hash = key.hashCode();
        index = (hash & 0x7FFFFFFF) % tab.length;
    }

    // Creates the new entry.
    @SuppressWarnings("unchecked")
    Entry<K,V> e = (Entry<K,V>) tab[index];
    tab[index] = new Entry<>(hash, key, value, e);
    count++;
}

可以看出HashTable到了jdk1.8了内部结构并没有实质优化，继续使用数组+链表的方式实现。

rehash

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
protected void rehash() {
    int oldCapacity = table.length;
    Entry<?,?>[] oldMap = table;

    // overflow-conscious code
    int newCapacity = (oldCapacity << 1) + 1;
    if (newCapacity - MAX_ARRAY_SIZE > 0) {
        if (oldCapacity == MAX_ARRAY_SIZE)
            // Keep running with MAX_ARRAY_SIZE buckets
            return;
        newCapacity = MAX_ARRAY_SIZE;
    }
    Entry<?,?>[] newMap = new Entry<?,?>[newCapacity];

    modCount++;
    threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
    table = newMap;

    for (int i = oldCapacity ; i-- > 0 ;) {
        for (Entry<K,V> old = (Entry<K,V>)oldMap[i] ; old != null ; ) {
            Entry<K,V> e = old;
            old = old.next;

            int index = (e.hash & 0x7FFFFFFF) % newCapacity;
            //使用头插法将链表反序
            e.next = (Entry<K,V>)newMap[index];
            newMap[index] = e;
        }
    }
}

Hashtable的扩容将先创建一个长度为原长度2倍的数组，再使用头插法将链表进行反序。

和HashMap的不同之处

HashMap Hashtable
继承机制 继承AbstractMap 继承Dictionary
线程安全 线程不安全 put、remove等方法均被synchronized修饰，同步，线程安全
参数设置 key、value均可为null key、value均不可为null
结构 由位桶+链表+红黑树构成 由位桶+链表构成
添加entry 添加新entry时，放置链表尾部 添加新entry时，放置链表头部
构造上 底层数组的长度必须为2^n ,默认长度16 底层数组的长度可以为任意值，默认长度11
Hash算法上 hash算法通过非常规的设计，将底层table长度设计为2^n（合数）并使用了&运算来代替%运算以减少性能上面的损耗 hash算法首先使得hash的值小于等于整型数的最大值，再通过%运算实现均匀散射
扩容机制上 扩容不需要链表反转，用hashCode新增的bit位查看是否插入旧数组还是插入新数组位置 头插法扩容

知乎：hashMap和hashTable的区别

HashMap

HashMap就是典型的拉链法哈希表结构。·

他实际上是一个线性数组。他的静态内部类继承了一个Entry接口。这里注意，在jdk1.8中，在链表中加入了红黑树（平衡二分查找树）。所以1.8版本的HashMap是由数组+（链表+红黑树）实现的。

hash

基本概念

Hash，即散列，把任意长度的输入，通过散列算法变成固定长度的输出。由于是不定长到定长的压缩映射，输出值域小于输入值域，所以不同的输入可能有相同的输出，即hash碰撞。

hash算法

1
2
3
4
5
6
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
//手写的，源码在不存在这一句，但是原理是类似的，详情可以去看putVal方法
int i = (table.length-1) & hash(key)

这里Hash算法的本质是取key的hashCode值、高位运算、取模运算 ·

在JDK1.8的实现中，优化了高位运算的算法，通过hashCode()的高16位异或低16位实现的：(h = k.hashCode()) ^ (h >>> 16)，主要是从速度、功效、质量来考虑的，这么做可以在数组table的length比较小的时候，也能保证考虑到高低Bit都参与到Hash的计算中，同时不会有太大的开销。

属性

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
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable {
    int threshold;             // 所能容纳的key-value对极限 
     final float loadFactor;    // 负载因子
    //modCount字段主要用来记录HashMap内部结构发生变化的次数，主要用于迭代的快速失败。强调一点，内部结构发生变化指的是结构发生变化，例如put新键值对，但是某个key对应的value值被覆盖不属于结构变化
     int modCount;  
     int size;
    ......
    static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;//hash code value for this map entry
        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;
        }

        public final K getKey()        { return key; }
        public final V getValue()      { return value; }
        public final String toString() { return key + "=" + value; }

        public final int hashCode() {
            return Objects.hashCode(key) ^ Objects.hashCode(value);
        }

        public final V setValue(V newValue) {
            V oldValue = value;
            value = newValue;
            return oldValue;
        }

        public final boolean equals(Object o) {
            if (o == this)
                return true;
            if (o instanceof Map.Entry) {
                Map.Entry<?,?> e = (Map.Entry<?,?>)o;
                if (Objects.equals(key, e.getKey()) &&
                    Objects.equals(value, e.getValue()))
                    return true;
            }
            return false;
        }
    }
    ......
}

构造

可以看出HashMap的底层数组的长度必须为2^n，这样做的好处是为以后的hash算法做准备

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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);
}

//该方法返回大于等于cap的最小2次幂的整数
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;
}

方法

所有方法集合

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void clear() // 移除所有键值
Object    clone() // 浅复制，键值本身不会复制
V    compute(K key, BiFunction<? super K,? super V,? extends V> remappingFunction) // 尝试为指定的键和它当前映射的值计算一个映射（没有则返回null）
V    computeIfAbsent(K key, Function<? super K,? extends V> mappingFunction) // 如果指定的键没有关联值（或关联null），使用指定的映射函数计算值，非空则加入map
V    computeIfPresent(K key, BiFunction<? super K,? super V,? extends V> remappingFunction) // 如果指定键关联了非空值，尝试用给定的键值计算一个映射
boolean    containsKey(Object key) // 是否包含某键
boolean    containsValue(Object value) // 是否包含某值
Set<Map.Entry<K,V>>    entrySet()  // 键值对的Set集合
void    forEach(BiConsumer<? super K,? super V> action) // 为每个键值对指定特定函数，抛出异常则中断
V    get(Object key) // 获取某键的值
V    getOrDefault(Object key, V defaultValue) // 获取某键的值，没有则返回默认值
boolean    isEmpty() // map是否为空容器
Set<K>    keySet() // 键的Set集合
V    merge(K key, V value, BiFunction<? super V,? super V,? extends V> remappingFunction) // 如果指定的键没有关联值或关联null，则用给定的非空值关联它
V    put(K key, V value) // 添加键值对
void    putAll(Map<? extends K,? extends V> m) // 添加给定map中所有键值对
V    putIfAbsent(K key, V value) // 如果指定的键没有关联值或关联null，将它关联新值，并返回原值
V    remove(Object key) // 移除某键
boolean    remove(Object key, Object value) // 移除某键值对
V    replace(K key, V value) // 替换键值对
boolean    replace(K key, V oldValue, V newValue) // 原值相同则替换键值对
void    replaceAll(BiFunction<? super K,? super V,? extends V> function) // 调用函数替换每个键值对，抛出异常中断
int    size() // map大小
Collection<V>    values() // map的值集合

get/getNode

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
public V get(Object key) {
    Node<K,V> e;
    //key是否存在，存在返回key的value值，不存在返回null 
    //hash(key)获得key的hash值
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node<K,V> getNode(int hash, Object key) {
        Node<K,V>[] tab; //Entry数组
        Node<K,V> first, e; 
        int n; //数组长度
        K k;
        // 1. 定位键值对所在桶的位置
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (first = tab[(n - 1) & hash]) != null) {
            //2.判断键值的hashcode相等，对象相等
            if (first.hash == hash && // always check first node
                ((k = first.key) == key || (key != null && key.equals(k))))
                return first;
            if ((e = first.next) != null) {
                // 3..如果 first 是 TreeNode 类型，则调用黑红树查找方法
                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);
            }
        }
        return null;
    }

具体逻辑：

  1. 计算桶在桶数组的位置(first = tab[(n - 1) & hash]) != null

    1
    a % b == (b-1) & a ,当b是2的指数时，等式成立。

  1. 判断hashcode是否相等,对象是否相等

  2. 判断是否是TreeNode类型

put/putVal

img 
1
2
3
public V put(K key, V value) {
       return putVal(hash(key), key, value, false, true);//1. onlyIfAbsent参数
   }
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;
       // 初始化桶数组 table
       if ((tab = table) == null || (n = tab.length) == 0)
           //扩容方法
           n = (tab = resize()).length;
       // 当前key不存在，新建键值对加入
       if ((p = tab[i = (n - 1) & hash]) == null)

           tab[i] = newNode(hash, key, value, null);

       else {
           Node<K,V> e; K k;
           // 如果键的值以及节点 hash 等于链表中的第一个键值对节点时，则将 e 指向该键值对
           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)//1.onlyIfAbsent 判断
                   e.value = value;
               afterNodeAccess(e);
               return oldValue;
           }
       }
       ++modCount;
       if (++size > threshold)
           resize();
       afterNodeInsertion(evict);
       return null;
   }

具体逻辑：

  1. 初始化桶数组，判断是否需要扩容
  2. 判断key是否存在，若不存在就新创建一个 节点
  3. 若存在，首先判断键的值和节点的hash值是否是链表第一个节点，是则插入
  4. 其次判断是否是树节点，是则执行树的插入
  5. 如果都不是就遍历链表，插入节点，大于阙值就树化，遇到相等的节点就覆盖（hash相等，键相等）

onlyIfAbsent参数

put的onlyIfAbesent的false，putIfAbsent的onlyIfAbsent是true

在放入数据时，如果存在重复的key，那么putIfAbsent不会放入值。
如果传入key对应的value已经存在，就返回存在的value，不进行替换。如果不存在，就添加key和value，返回null

resize

resize()只有在两种情况下会被调用：·

  • 由于HashMap实行了懒加载: 新建HashMap时不会对table进行赋值, 而是到第一次插入时, 进行resize时构建table;
  • 当HashMap的size值大于 threshold时, 会进行resize(); 看一下threshold在源码中的注解:
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
86
 final Node<K,V>[] resize() {

    Node<K,V>[] oldTab = table;//将当前table暂存到oldtab来操作

    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;//阈值设置为Integer的最大值，好像是2147483647，远大于默认的最大容量
            return oldTab;//直接返回当前table，不用扩容
        }

        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // 双倍扩大老内存和老阈值并赋给新的table
        
    }else if (oldThr > 0) // 初始化HashMap时添加了初始容量参数
        newCap = oldThr;

    else {               //这种情况是初始化HashMap时啥参数都没加
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);        
    }

    if (newThr == 0) {//当只满足老阈值大于0的条件时，新阈值等于新容量*默认扩容因子
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr;//把新的阈值赋给当前table

    @SuppressWarnings({"rawtypes","unchecked"})
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];//创建容量为newCap的新table
    table = newTab;
    if (oldTab != null) {
        for (int j = 0; j < oldCap; ++j) {//对老table进行遍历
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {//遍历到的赋给e进行暂存，同时将老table对应项赋值为null
                oldTab[j] = null;
                if (e.next == null)//将不为空的元素复制到新table中
                    newTab[e.hash & (newCap - 1)] = e;//只有一个节点时等于是创建一个新的空table然后重新进行元素的put，这里的table长度是原table的两倍
                else if (e instanceof TreeNode)// 红黑树进行旋转
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else { // preserve order
                    //HashMap在JDK1.8的时候改善了扩容机制，原数组索引i上的链表不需要再反转。
                    // 扩容之后的索引位置只能是i或者i+oldCap（原数组的长度）
                    // 所以我们只需要看hashcode新增的bit为0或者1。
                   // 假如是0扩容之后就在新数组索引i位置，新增为1，就在索引i+oldCap位置
                    Node<K,V> loHead = null, loTail = null;//用于保存put后不移位的链表
                    Node<K,V> hiHead = null, hiTail = null;//用于保存put后移位的链表
                    Node<K,V> next;
                    do {
                        next = e.next;
                        if ((e.hash & oldCap) == 0) {//如果与的结果为0，表示不移位，将桶中的头结点添加到lohead和lotail中，往后如果桶中还有不移位的结点，就向tail继续添加
                            if (loTail == null)//在后面遍历lohead和lotail保存到table中时，lohead用于保存头结点的位置，lotail用于判断是否到了末尾
                                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;
}

具体逻辑

  1. 若table为null或容量为0，则使用默认值16扩容，临界值为16*0.75，否则2
  2. 若容量是否超过设定的最大容量，重置临界值不扩容返回，否则3
  3. 容器容量加倍，临界值加倍·
  4. 若容器原来不为空，则需迁移数据
  5. oldTab[i]链表中数据分别移至newTab[i]和newTab[i+oldTab.length]中

经过观测可以发现，我们使用的是2次幂的扩展(指长度扩为原来2倍)，所以，元素的位置要么是在原位置，要么是在原位置再移动2次幂的位置

jdk1.8对扩容进行优化，使得扩容不再需要进行链表的反转，只需要知道hashcode新增的bit位为0还是1。如果是0就在原索引位置，新增索引是1就在oldIndex+oldCap位置。

推荐看一下这篇重新认识HashMap，对扩容写的很清楚

线程安全性

反例，会造成无限环

主要原因在于 并发下的Rehash 会造成元素之间会形成一个循环链表。不过，jdk 1.8 后解决了这个问题，但是还是不建议在多线程下使用 HashMap,因为多线程下使用 HashMap还是会存在其他问题比如数据丢失。并发环境下推荐使用 ConcurrentHashMap。·

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class HashMapInfiniteLoop {  

    private static HashMap<Integer,String> map = new HashMap<Integer,String>(2，0.75f);  
    public static void main(String[] args) {  
        map.put(5， "C");  

        new Thread("Thread1") {  
            public void run() {  
                map.put(7, "B");  
                System.out.println(map);  
            };  
        }.start();  
        new Thread("Thread2") {  
            public void run() {  
                map.put(3, "A);  
                System.out.println(map);  
            };  
        }.start();        
    }  
}

简单介绍线程安全的ConcurrentHashMap·

jdk1.7

  • 底层采用分段的数组+链表实现，线程安全
  • 通过把整个Map分为N个Segment，可以提供相同的线程安全，但是效率提升N倍，默认提升16倍。(读操作不加锁，由于HashEntry的value变量是 volatile的，也能保证读取到最新的值。)
  • Hashtable的synchronized是针对整张Hash表的，即每次锁住整张表让线程独占，ConcurrentHashMap允许多个修改操作并发进行，其关键在于使用了锁分离技术
  • 有些方法需要跨段，比如size()和containsValue()，它们可能需要锁定整个表而而不仅仅是某个段，这需要按顺序锁定所有段，操作完毕后，又按顺序释放所有段的锁
  • 扩容：段内扩容（段内元素超过该段对应Entry数组长度的75%触发扩容，不会对整个Map进行扩容），插入前检测需不需要扩容，有效避免无效扩容

jdk1.8

  • 底层数据结构： JDK1.7的 ConcurrentHashMap底层采用 分段的数组+链表 实现，JDK1.8 采用的数据结构跟HashMap1.8的结构一样，数组+链表/红黑二叉树。Hashtable和 JDK1.8 之前的 HashMap的底层数据结构类似都是采用 数组+链表 的形式，数组是 HashMap的主体，链表则是主要为了解决哈希冲突而存在的；

  • 实现线程安全的方式（重要）：

    ① 在JDK1.7的时候，ConcurrentHashMap（分段锁） 对整个桶数组进行了分割分段(Segment)，每一把锁只锁容器其中一部分数据，多线程访问容器里不同数据段的数据，就不会存在锁竞争，提高并发访问率。 到了 JDK1.8 的时候已经摒弃了Segment的概念，而是直接用 Node 数组+链表+红黑树的数据结构来实现，并发控制使用 synchronized 和 CAS来操作。（JDK1.6以后 对 synchronized锁做了很多优化） 整个看起来就像是优化过且线程安全的 HashMap，虽然在JDK1.8中还能看到 Segment的数据结构，但是已经简化了属性，只是为了兼容旧版本；

    ② Hashtable(同一把锁) :使用 synchronized来保证线程安全，效率非常低下。当一个线程访问同步方法时，其他线程也访问同步方法，可能会进入阻塞或轮询状态，如使用 put 添加元素，另一个线程不能使用 put 添加元素，也不能使用 get，竞争会越来越激烈效率越低。

WeakHashMap

HashMap和WeakHashMap的相同点

  1. 它们都是散列表，存储的是“键值对”映射。
  2. 它们都继承于AbstractMap，并且实现Map基础。
  3. 它们的构造函数都一样。
    它们都包括4个构造函数，而且函数的参数都一样。
  4. 默认的容量大小是16，默认的加载因子是0.75。
  5. 它们的“键”和“值”都允许为null。
  6. 它们都是“非同步的”。

HashMap和WeakHashMap的不同点

HashMap实现了Cloneable和Serializable接口，而WeakHashMap没有。
HashMap实现Cloneable，意味着它能通过clone()克隆自己。
HashMap实现Serializable，意味着它支持序列化，能通过序列化去传输。

HashMap的“键”是“强引用(StrongReference)”，而WeakHashMap的键是“弱引用(WeakReference)”。
WeakReference的“弱键”能实现WeakReference对“键值对”的动态回收。当“弱键”不再被使用到时，GC会回收它，WeakReference也会将“弱键”对应的键值对删除。

这个“弱键”实现的动态回收“键值对”的原理呢？其实，通过WeakReference(弱引用)和ReferenceQueue(引用队列)实现的。 首先，我们需要了解WeakHashMap中：
第一，“键”是WeakReference，即key是弱键。
第二，ReferenceQueue是一个引用队列，它是和WeakHashMap联合使用的。当弱引用所引用的对象被垃圾回收，Java虚拟机就会把这个弱引用加入到与之关联的引用队列中。 WeakHashMap中的ReferenceQueue是queue。
第三，WeakHashMap是通过数组实现的，我们假设这个数组是table。

动态回收步骤

1
将WeakHashMap中的key设置null，并执行gc()。系统会回收key
  1. 新建WeakHashMap，将“键值对”添加到WeakHashMap中。
    将“键值对”添加到WeakHashMap中时，添加的键都是弱键。
实际上，WeakHashMap是通过数组table保存Entry(键值对)；每一个Entry实际上是一个单向链表，即Entry是键值对链表。
  2. 当某“弱键”不再被其它对象引用，并被GC回收时。在GC回收该“弱键”时，这个“弱键”也同时会被添加到queue队列中。
    例如，当我们在将“弱键”key添加到WeakHashMap之后；后来将key设为null。这时，便没有外部外部对象再引用该了key。
接着，当Java虚拟机的GC回收内存时，会回收key的相关内存；同时，将key添加到queue队列中。
  3. 当下一次我们需要操作WeakHashMap时，会先同步table和queue。table中保存了全部的键值对，而queue中保存被GC回收的“弱键”；同步它们，就是删除table中被GC回收的“弱键”对应的键值对。

HashSet

HashSet基于HashMap来实现的，底层是使用HashMap的Key保存元素，Value统一为类的常量Object对象。

继承AbstractCollection，实现Set、Serializable、Cloneable接口。

  • Serializable：可被序列化
  • Cloneable：可被克隆

特性：

  • 无序
  • 唯一
  • 可为null
  • 不同步（非线程安全）

属性

1
2
3
4
// 使用map的Key保存元素
private transient HashMap map;
// map的Value均指向PRESENT，不设置为null是为了防止NullPointerException
private static final Object PRESENT = new Object();

构造

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 使用HashMap的初始容量0和默认加载因子0.75f来初始化（JDK1.8）
public HashSet() {
    map = new HashMap<>();
}
public HashSet(Collection<? extends E> c) {
    // 容量为c的4/3倍和16的最大值
    map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
    // 添加所有元素
    addAll(c);
}
// 指定初始容量
public HashSet(int initialCapacity) {
    map = new HashMap<>(initialCapacity);
}
// 指定初始容量，加载因子（dummy未使用）
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
    map = new LinkedHashMap<>(initialCapacity, loadFactor);
}

方法

1
2
3
4
5
6
7
8
9
boolean add(E e) // 添加元素
void clear() // 清除
Object clone() // 浅复制
boolean contains(Object o) // 是否包含
boolean isEmpty() // 是否为空
Iterator<E> iterator() // 迭代器
boolean remove(Object o) // 移除
int size() // 集合大小
Spliterator<E> spliterator()

add

1
2
3
4
public boolean add(E e) {
    // 调用HashMap.put(key, value)方法（key=e，value=PRESENT）
    return map.put(e, PRESENT)==null;
}

方法声明只有当元素尚未存在于集合中时才会添加元素。如果成功添加了元素，则该方法返回true，否则返回false。

remove

1
2
3
4
public boolean remove(Object o) {
    //调用HashMap.remove(key)方法
    return map.remove(o)==PRESENT;
}

HashSet如何保持唯一性？

当我们将一个对象放入一个HashSet时，它使用该对象的hashcode值来确定一个元素是否已经在该集合中。

每个散列码值对应于某个块位置，该块位置可以包含计算出的散列值相同的各种元素。但是具有相同hashCode的两个对象可能不相等。

因此，将使用equals（）方法比较同一存储桶中的对象。

hashCode（）与equals（）的相关规定：

  1. 如果两个对象相等，则hashcode一定也是相同的
  2. 两个对象相等,对两个equals方法返回true
  3. 两个对象有相同的hashcode值，它们也不一定是相等的
  4. 综上，equals方法被覆盖过，则hashCode方法也必须被覆盖
  5. hashCode()的默认行为是对堆上的对象产生独特值。如果没有重写hashCode()，则该class的两个对象无论如何都不会相等（即使这两个对象指向相同的数据）。

性能

HashSet的性能主要受两个参数影响 - 初始容量和负载因子。

  • 较低的初始容量降低了空间复杂性，但增加了重新散布的频率，这是一个昂贵的过程。

  • 另一方面，高初始容量增加了迭代成本和初始内存消耗。

HashMap 和 HashSet区别

TreeMap

TreeMap是基于红黑树（Red-Black Tree）

TreeMap实现SortedMap接口，能够把它保存的记录根据键排序，默认是按键值的升序排序，也可以指定排序的比较器，当用Iterator遍历TreeMap时，得到的记录是排过序的。如果使用排序的映射，建议使用TreeMap。在使用TreeMap时，key必须实现Comparable接口或者在构造TreeMap传入自定义的Comparator，否则会在运行时抛出java.lang.ClassCastException类型的异常。

img

属性

1
2
3
4
5
6
7
8
// 比较器
private final Comparator<? super K> comparator;
// 根节点
private transient Entry<K,V> root;
// 树中键值对个数
private transient int size = 0;
// 树结构的修改次数
private transient int modCount = 0;

构造

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public TreeMap() {
    // 比较器为null，使用key的自然顺序来维持TreeMap的顺序，Key要求实现Comparable接口
    comparator = null; 
}
public TreeMap(Comparator<? super K> comparator) {
    this.comparator = comparator; // 设置比较器
}
public TreeMap(Map<? extends K, ? extends V> m) {
    comparator = null; // 比较器为null
    putAll(m); // 放置所有元素
}
public TreeMap(SortedMap<K, ? extends V> m) {
    comparator = m.comparator(); // 根据SortedMap的比较器维持TreeMap的顺序
    try {
        buildFromSorted(m.size(), m.entrySet().iterator(), null, null);
    } catch (java.io.IOException cannotHappen) {
    } catch (ClassNotFoundException cannotHappen) {
    }
}

方法

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
V put(K key, V value) // 添加键值对
void putAll(Map<? extends K,? extends V> map) // 添加map中所有

V remove(Object key) // 根据key移除
void clear() // 移除所有键值对
Map.Entry<K,V> pollFirstEntry() // 移除并返回最小key的键值对
Map.Entry<K,V> pollLastEntry() // 移除并返回最大key的键值对

V replace(K key, V value) // 替换某key的value
boolean replace(K key, V oldValue, V newValue) // 替换某键值对的value

int size() // 键值对个数
Comparator<? super K> comparator() // 返回比较器，根据key的自然排序则返回null

V get(Object key) // 指定key的value

Set<K> keySet() // key集合
NavigableSet<K> navigableKeySet() // 和keySet()一样
Collection<V> values() // 值集合
Set<Map.Entry<K,V>> entrySet() // 映射的键值对集合

boolean containsKey(Object key) // 是否包含某键
boolean containsValue(Object value) // 是否包含某值

NavigableSet<K> descendingKeySet() // key的降序集合
NavigableMap<K,V> descendingMap() // 键值对的降序映射

Map.Entry<K,V> ceilingEntry(K key) // key的上限（>=）键值对
Map.Entry<K,V> floorEntry(K key) // key的下限（<=）键值对
K ceilingKey(K key) // key的上限（>=）键
K floorKey(K key) // key的下限（<=）键

Map.Entry<K,V> firstEntry() // 最小的键值对
Map.Entry<K,V> lastEntry() // 最大的键值对
K firstKey() // 最小的key
K lastKey() // 最大的key

Map.Entry<K,V> higherEntry(K key) // 大于key的第一个键值对
K higherKey(K key) // 大于key的第一个键
Map.Entry<K,V> lowerEntry(K key) // 小于key的第一个键值对
K lowerKey(K key) // 小于key的第一个键

SortedMap<K,V> headMap(K toKey) // portion < tokey 的部分
NavigableMap<K,V> headMap(K toKey, boolean inclusive) // portion < tokey 的部分（inclusive是否包含边界）
SortedMap<K,V> subMap(K fromKey, K toKey) // fromKey <= portion < toKey 的部分
NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive) // fromKey < portion < toKey 的部分（inclusive是否包含边界）
SortedMap<K,V> tailMap(K fromKey) // portion >= tokey 的部分
NavigableMap<K,V> tailMap(K fromKey, boolean inclusive) // portion > tokey 的部分（inclusive是否包含边界）

void forEach(BiConsumer<? super K,? super V> action) // 对每个键值对执行相同操作，异常中断
void replaceAll(BiFunction<? super K,? super V,? extends V> function) // 对每个键值对执行相同的替换操作，异常中断

Object clone() // 浅复制TreeMap实例

使用示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 遍历treeMap
treeMap.forEach(new BiConsumer<Integer, String>() {
    @Override
    public void accept(Integer integer, String s) {
        System.out.println(integer+"->"+s);
    }
});
// 替换treeMap所有元素
treeMap.replaceAll(new BiFunction<Integer, String, String>() {
    @Override
    public String apply(Integer integer, String s) {
        return s+"....";
    }
});

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
55
56
57
58
59
60
61
62
63
public V put(K key, V value) {
    Entry<K,V> t = root;
    // 根节点为null，直接创建一个节点返回
    if (t == null) {
        compare(key, key); // 类型校验，是否为null
        root = new Entry<>(key, value, null);
        size = 1;
        modCount++;
        return null;
    }
    int cmp;
    Entry<K,V> parent;
    Comparator<? super K> cpr = comparator;
    // 比较器不为null，使用比较器维持TreeMap的元素顺序
    if (cpr != null) {
        // 循环，获取插入后的父节点
        do {
            // 记录父节点
            parent = t;
            cmp = cpr.compare(key, t.key);
            // key<t.key，插入到节点的左边
            if (cmp < 0)
                t = t.left;
            // key>t.key，插入到节点的右边
            else if (cmp > 0)
                t = t.right;
            // key==t.key，覆盖原值即可，并返回原值
            else
                return t.setValue(value);
        } while (t != null);
    }
    // 比较器为null，使用key作为比较器进行比较，key需实现Comparable接口
    else {
        if (key == null)
            throw new NullPointerException();
        @SuppressWarnings("unchecked")
            Comparable<? super K> k = (Comparable<? super K>) key;
        // 同上面一样，获取插入后的父节点
        do {
            parent = t;
            cmp = k.compareTo(t.key);
            if (cmp < 0)
                t = t.left;
            else if (cmp > 0)
                t = t.right;
            else
                return t.setValue(value);
        } while (t != null);
    }
    // 创建新节点
    Entry<K,V> e = new Entry<>(key, value, parent);
    if (cmp < 0)
        // key小于父节点，插入到左侧
        parent.left = e;
    else
        // key大于父节点，插入到右侧
        parent.right = e;
    // 插入后，保持红黑树平衡进行调整
    fixAfterInsertion(e);
    size++;
    modCount++;
    return null;
}

rotateLeft

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
// 左旋
// 重置三个父子节点
// 1. p 和 r.left
// 2. p.parent 和 r
// 3. r 和 p
private void rotateLeft(Entry<K,V> p) {
    if (p != null) {
        Entry<K,V> r = p.right;
        // 1. p 和 r.left 建立父子节点关系
        p.right = r.left;
        if (r.left != null)
            r.left.parent = p;
        // 2. p.parent 和 r 建立父子节点关系
        r.parent = p.parent;
        if (p.parent == null)
            root = r;
        else if (p.parent.left == p)
            p.parent.left = r;
        else
            p.parent.right = r;
        // 3. r 和 p 建立父子节点关系
        r.left = p;
        p.parent = r;
    }
}

rotateRight

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// 右旋
// 重置三个父子节点
// 1. p 和 l.right
// 2. p.parent 和 l
// 3. l 和 p
private void rotateRight(Entry<K,V> p) {
    if (p != null) {
        Entry<K,V> l = p.left;
        // 1. p 和 l.right 建立父子节点关系
        p.left = l.right;
        if (l.right != null)
            l.right.parent = p;
        // 2. p.parent 和 l 建立父子节点关系
        l.parent = p.parent;
        if (p.parent == null)
            root = l;
        else if (p.parent.right == p)
            p.parent.right = l;
        else p.parent.left = l;
        // 3. l 和 p 建立父子节点关系
        l.right = p;
        p.parent = l;
    }
}

remove

1
2
3
4
5
6
7
8
9
10
11
12
public V remove(Object key) {
    // 根据key查找键值对
    Entry<K,V> p = getEntry(key);
    if (p == null)
        return null;
    // 保存原值
    V oldValue = p.value;
    // 删除键值对
    deleteEntry(p);
    // 返回原值
    return oldValue;
}

对equal的几点补充

集合中大量使用equals方法，实际上，该方法如果没有被重写，则就比较两个对象是否完全相等。

java对equals()的要求

1
2
3
4
5
1. 对称性：如果x.equals(y)返回是"true"，那么y.equals(x)也应该返回是"true"。
2. 反射性：x.equals(x)必须返回是"true"。
3. 类推性：如果x.equals(y)返回是"true"，而且y.equals(z)返回是"true"，那么z.equals(x)也应该返回是"true"。
4. 一致性：如果x.equals(y)返回是"true"，只要x和y内容一直不变，不管你重复x.equals(y)多少次，返回都是"true"。
5. 非空性，x.equals(null)，永远返回是"false"；x.equals(和x不同类型的对象)永远返回是"false"。

equals() 与 == 的区别是什么？

没有被复写的时候等价

hashCode() 的作用

本质作用是确定该对象在哈希表中的索引位置

在散列表中可以判断对象的大小关系

hashCode() 和 equals() 的关系

在会创建“类对应的散列表”的情况下

1)、如果两个对象相等，那么它们的hashCode()值一定相同。
这里的相等是指，通过equals()比较两个对象时返回true。
2)、如果两个对象hashCode()相等，它们并不一定相等。
因为在散列表中，hashCode()相等，即两个键值对的哈希值相等。然而哈希值相等，并不一定能得出键值对相等。补充说一句：“两个不同的键值对，哈希值相等”，这就是哈希冲突。

对conparable和comparator的几点补充

Java 中 Comparable 和 Comparator 比较

Comparable

Comparable 是排序接口。

若一个类实现了Comparable接口，就意味着“该类支持排序”。 即然实现Comparable接口的类支持排序，假设现在存在“实现Comparable接口的类的对象的List列表(或数组)”，则该List列表(或数组)可以通过 Collections.sort（或 Arrays.sort）进行排序。

1
2
3
4
5
6
package java.lang;
import java.util.*;

public interface Comparable<T> {
    public int compareTo(T o);
}

说明：
假设我们通过 x.compareTo(y) 来“比较x和y的大小”。若返回“负数”，意味着“x比y小”；返回“零”，意味着“x等于y”；返回“正数”，意味着“x大于y”。

Comparator

Comparator 是比较器接口。

我们若需要控制某个类的次序，而该类本身不支持排序(即没有实现Comparable接口)；那么，我们可以建立一个“该类的比较器”来进行排序。这个“比较器”只需要实现Comparator接口即可。

也就是说，我们可以通过“实现Comparator类来新建一个比较器”，然后通过该比较器对类进行排序。

1
2
3
4
5
6
7
8
package java.util;

public interface Comparator<T> {

    int compare(T o1, T o2);

    boolean equals(Object obj);
}

说明：

  1. 若一个类要实现Comparator接口：它一定要实现compareTo(T o1, T o2) 函数，但可以不实现 equals(Object obj) 函数。

    为什么可以不实现 equals(Object obj) 函数呢？ 因为任何类，默认都是已经实现了equals(Object obj)的。 Java中的一切类都是继承于java.lang.Object，在Object.java中实现了equals(Object obj)函数；所以，其它所有的类也相当于都实现了该函数。

  2. int compare(T o1, T o2)是“比较o1和o2的大小”。返回“负数”，意味着“o1比o2小”；返回“零”，意味着“o1等于o2”；返回“正数”，意味着“o1大于o2”。

比较

Comparable是排序接口；若一个类实现了Comparable接口，就意味着“该类支持排序”。
而Comparator是比较器；我们若需要控制某个类的次序，可以建立一个“该类的比较器”来进行排序。

我们不难发现：Comparable相当于“内部比较器”，而Comparator相当于“外部比较器”。

1
一个类本身实现了Comparable比较器，就意味着它本身支持排序；若它本身没实现Comparable，也可以通过外部比较器Comparator进行排序。

ConcurrentHashMap(jdk1.7)

属性

1
2
3
4
5
6
7
8
9
10
11
 final Segment<K,V>[] segments;

 transient volatile HashEntry<K,V>[] table;

static final class HashEntry<K,V> {
        final int hash;
        final K key;
        volatile V value;
        volatile HashEntry<K,V> next;
        //其他省略
}

Segment继承了ReentrantLock，所以它就是一种可重入锁（ReentrantLock)。在ConcurrentHashMap，一个Segment就是一个子哈希表，Segment里维护了一个HashEntry数组，并发环境下，对于不同Segment的数据进行操作是不用考虑锁竞争的。（就按默认的ConcurrentLevel为16来讲，理论上就允许16个线程并发执行）

构造

segment构造方法

1
2
3
4
5
Segment(float lf, int threshold, HashEntry<K,V>[] tab) {
            this.loadFactor = lf;//负载因子
            this.threshold = threshold;//阈值
            this.table = tab;//主干数组即HashEntry数组
        }

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
37
38
39
//初始化方法有三个参数，如果用户不指定则会使用默认值，initialCapacity为16，loadFactor为0.75（负载因子，扩容时需要参考），concurrentLevel为16。
public ConcurrentHashMap(int initialCapacity,
                         float loadFactor,
                         int concurrencyLevel) {
          if (!(loadFactor > 0) || initialCapacity < 0 || concurrencyLevel <= 0)
              throw new IllegalArgumentException();
          //MAX_SEGMENTS 为1<<16=65536，也就是最大并发数为65536
          if (concurrencyLevel > MAX_SEGMENTS)
              concurrencyLevel = MAX_SEGMENTS;
          //2的sshif次方等于ssize，例:ssize=16,sshift=4;ssize=32,sshif=5
         int sshift = 0;
         //ssize 为segments数组长度，根据concurrentLevel计算得出
         int ssize = 1;
         while (ssize < concurrencyLevel) {
             ++sshift;
             ssize <<= 1;
         }
         //segmentShift和segmentMask这两个变量在定位segment时会用到
         this.segmentShift = 32 - sshift;
         this.segmentMask = ssize - 1;
         if (initialCapacity > MAXIMUM_CAPACITY)
             initialCapacity = MAXIMUM_CAPACITY;
         //计算cap的大小，即Segment中HashEntry的数组长度，cap也一定为2的n次方.
         int c = initialCapacity / ssize;
         if (c * ssize < initialCapacity)
             ++c;
        // 默认 MIN_SEGMENT_TABLE_CAPACITY 是 2，这个值也是有讲究的，因为这样的话，对于具体的槽上，
    // 插入一个元素不至于扩容，插入第二个的时候才会扩容
         int cap = MIN_SEGMENT_TABLE_CAPACITY;
         while (cap < c)
             cap <<= 1;
         //创建segments数组并初始化第一个Segment，其余的Segment延迟初始化
         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); 
         this.segments = ss;
     }

初始化完成，我们得到了一个 Segment 数组。我们就当是用 new ConcurrentHashMap() 无参构造函数进行初始化的，那么初始化完成后：

  • Segment数组长度为 16，不可以扩容.Segment数组的大小ssize是由concurrentLevel来决定的，但是却不一定等于concurrentLevel，ssize一定是大于或等于concurrentLevel的最小的2的次幂
  • Segment[i] 的默认大小为 2，负载因子是 0.75，得出初始阈值为 1.5，也就是以后插入第一个元素不会触发扩容，插入第二个会进行第一次扩容
  • 这里初始化了 segment[0]，其他位置还是 null，至于为什么要初始化 segment[0]，后面的代码会介绍
  • 当前 segmentShift的值为 32 - 4 = 28，segmentMask 为 16 - 1 = 15，姑且把它们简单翻译为移位数和掩码，这两个值马上就会用到

方法

put

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public V put(K key, V value) {
       Segment<K,V> s;
       //concurrentHashMap不允许key/value为空
       if (value == null)
           throw new NullPointerException();
  // 1. 计算 key 的 hash 值
       //hash函数对key的hashCode重新散列，避免差劲的不合理的hashcode，保证散列均匀
       int hash = hash(key);
   // 2. 根据 hash 值找到 Segment 数组中的位置 j
       //返回的hash值无符号右移segmentShift位与段掩码进行位运算，定位segment
       int j = (hash >>> segmentShift) & segmentMask;
       if ((s = (Segment<K,V>)UNSAFE.getObject          // nonvolatile; recheck
            (segments, (j << SSHIFT) + SBASE)) == null) //  in ensureSegment
           s = ensureSegment(j);
   // 3. 插入新值到槽 s 中 
    //调用代理到segment上的put方法
       return s.put(key, hash, value, false);
   }

从源码看出，put的主要逻辑也就两步：

1. 定位segment并确保定位的Segment已初始化

2. 调用Segment的put方法

关于segmentShift和segmentMask·

segmentShift和segmentMask这两个全局变量的主要作用是用来定位Segment，int j =(hash >>> segmentShift) & segmentMask。

segmentMask：段掩码，假如segments数组长度为16，则段掩码为16-1=15；segments长度为32，段掩码为32-1=31。这样得到的所有bit位都为1，可以更好地保证散列的均匀性

segmentShift：2的sshift次方等于ssize，segmentShift=32-sshift。若segments长度为16，segmentShift=32-4=28;若segments长度为32，segmentShift=32-5=27。而计算得出的hash值最大为32位，无符号右移segmentShift，则意味着只保留高几位（其余位是没用的），然后与段掩码segmentMask位运算来定位Segment。

*concurrentHashMap代理到Segment上的put方法，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
final V put(K key, int hash, V value, boolean onlyIfAbsent) {
            HashEntry<K,V> node = tryLock() ? null :
                scanAndLockForPut(key, hash, value);//tryLock不成功时会遍历定位到的HashEnry位置的链表（遍历主要是为了使CPU缓存链表），若找不到，则创建HashEntry。tryLock一定次数后（MAX_SCAN_RETRIES变量决定），则lock。若遍历过程中，由于其他线程的操作导致链表头结点变化，则需要重新遍历。
            V oldValue;
            try {
                HashEntry<K,V>[] tab = table;
                int index = (tab.length - 1) & hash;//定位HashEntry，可以看到，这个hash值在定位Segment时和在Segment中定位HashEntry都会用到，只不过定位Segment时只用到高几位。
                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，这个要看获取锁的过程，不过和这里都没有关系。
// 如果不为 null，那就直接将它设置为链表表头；如果是null，初始化并设置为链表表头。
                        if (node != null)
                            node.setNext(first);
                        else
                            node = new HashEntry<K,V>(hash, key, value, first);
                        int c = count + 1;　　　　　　　　　　　　　　//若c超出阈值threshold，需要扩容并rehash。扩容后的容量是当前容量的2倍。这样可以最大程度避免之前散列好的entry重新散列，具体在另一篇文章中有详细分析，不赘述。扩容并rehash的这个过程是比较消耗资源的。
                        if (c > threshold && tab.length < MAXIMUM_CAPACITY)
                            rehash(node);
                        else
                            setEntryAt(tab, index, node);
                        ++modCount;
                        count = c;
                        oldValue = null;
                        break;
                    }
                }
            } finally {
                unlock();
            }
            return oldValue;
        }

初始化槽: ensureSegment

ConcurrentHashMap 初始化的时候会初始化第一个槽 segment[0]，对于其他槽来说，在插入第一个值的时候进行初始化。这里需要考虑并发，因为很可能会有多个线程同时进来初始化同一个槽 segment[k]，不过只要有一个成功了就可以。

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
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[0] 了，
        // 使用当前 segment[0] 处的数组长度和负载因子来初始化 segment[k]
        // 为什么要用“当前”，因为 segment[0] 可能早就扩容过了
        Segment<K,V> proto = ss[0];
        int cap = proto.table.length;
        float lf = proto.loadFactor;
        int threshold = (int)(cap * lf);

        // 初始化 segment[k] 内部的数组
        HashEntry<K,V>[] tab = (HashEntry<K,V>[])new HashEntry[cap];
        if ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u))
            == null) { // 再次检查一遍该槽是否被其他线程初始化了。

            Segment<K,V> s = new Segment<K,V>(lf, threshold, tab);
            // 使用 while 循环，内部用 CAS，当前线程成功设值或其他线程成功设值后，退出
            while ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u))
                   == null) {
                if (UNSAFE.compareAndSwapObject(ss, u, null, seg = s))
                    break;
            }
        }
    }
    return seg;
}

总的来说，ensureSegment(int k)比较简单，对于并发操作使用 CAS 进行控制。如果当前线程 CAS 失败，这里的 while 循环是为了将 seg 赋值返回。

获取写入锁: scanAndLockForPut

往某个 segment 中 put 的时候，首先会调用 node = tryLock() ? null : scanAndLockForPut(key, hash, value)，也就是说先进行一次 tryLock() 快速获取该 segment 的独占锁，如果失败，那么进入到 scanAndLockForPut 这个方法来获取锁。

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
private HashEntry<K,V> scanAndLockForPut(K key, int hash, V value) {
    HashEntry<K,V> first = entryForHash(this, hash);
    HashEntry<K,V> e = first;
    HashEntry<K,V> node = null;
    int retries = -1; // negative while locating node

    // 循环获取锁
    while (!tryLock()) {
        HashEntry<K,V> f; // to recheck first below
        if (retries < 0) {
            if (e == null) {
                if (node == null) // speculatively create node
                    // 进到这里说明数组该位置的链表是空的，没有任何元素
                    // 当然，进到这里的另一个原因是 tryLock() 失败，所以该槽存在并发，不一定是该位置
                    node = new HashEntry<K,V>(hash, key, value, null);
                retries = 0;
            }
            else if (key.equals(e.key))
                retries = 0;
            else
                // 顺着链表往下走
                e = e.next;
        }
        // 重试次数如果超过 MAX_SCAN_RETRIES（单核1多核64），那么不抢了，进入到阻塞队列等待锁
        //    lock() 是阻塞方法，直到获取锁后返回
        else if (++retries > MAX_SCAN_RETRIES) {
            lock();
            break;
        }
        else if ((retries & 1) == 0 &&
                 // 这个时候是有大问题了，那就是有新的元素进到了链表，成为了新的表头
                 //     所以这边的策略是，相当于重新走一遍这个 scanAndLockForPut 方法
                 (f = entryForHash(this, hash)) != first) {
            e = first = f; // re-traverse if entry changed
            retries = -1;
        }
    }
    return node;
}

这个方法有两个出口，一个是 tryLock() 成功了，循环终止，另一个就是重试次数超过了 MAX_SCAN_RETRIES，进到 lock() 方法，此方法会阻塞等待，直到成功拿到独占锁。
这个方法就是看似复杂，但是其实就是做了一件事，那就是获取该segment的独占锁，如果需要的话顺便实例化了一下 node。

rehash

segment 数组不能扩容，扩容是 segment 数组某个位置内部的数组 HashEntry[] 进行扩容，扩容后，容量为原来的 2 倍。

首先，我们要回顾一下触发扩容的地方，put 的时候，如果判断该值的插入会导致该 segment 的元素个数超过阈值，那么先进行扩容，再插值

该方法不需要考虑并发，因为到这里的时候，是持有该 segment 的独占锁的。

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
// 方法参数上的 node 是这次扩容后，需要添加到新的数组中的数据。
private void rehash(HashEntry<K,V> node) {
    HashEntry<K,V>[] oldTable = table;
    int oldCapacity = oldTable.length;
    // 2 倍
    int newCapacity = oldCapacity << 1;
    threshold = (int)(newCapacity * loadFactor);
    // 创建新数组
    HashEntry<K,V>[] newTable =
        (HashEntry<K,V>[]) new HashEntry[newCapacity];
    // 新的掩码，如从 16 扩容到 32，那么 sizeMask 为 31，对应二进制 ‘000...00011111’
    int sizeMask = newCapacity - 1;

    // 遍历原数组，老套路，将原数组位置 i 处的链表拆分到 新数组位置 i 和 i+oldCap 两个位置
    for (int i = 0; i < oldCapacity ; i++) {
        // e 是链表的第一个元素
        HashEntry<K,V> e = oldTable[i];
        if (e != null) {
            HashEntry<K,V> next = e.next;
            // 计算应该放置在新数组中的位置，
            // 假设原数组长度为 16，e 在 oldTable[3] 处，那么 idx 只可能是 3 或者是 3 + 16 = 19
            int idx = e.hash & sizeMask;
            if (next == null)   // 该位置处只有一个元素，那比较好办
                newTable[idx] = e;
            else { // Reuse consecutive sequence at same slot
                // e 是链表表头
                HashEntry<K,V> lastRun = e;
                // idx 是当前链表的头结点 e 的新位置
                int lastIdx = idx;

                // 下面这个 for 循环会找到一个 lastRun 节点，这个节点之后的所有元素是将要放到一起的
                for (HashEntry<K,V> last = next;
                     last != null;
                     last = last.next) {
                    int k = last.hash & sizeMask;
                    if (k != lastIdx) {
                        lastIdx = k;
                        lastRun = last;
                    }
                }
                // 将 lastRun 及其之后的所有节点组成的这个链表放到 lastIdx 这个位置
                newTable[lastIdx] = lastRun;
                // 下面的操作是处理 lastRun 之前的节点，
                //    这些节点可能分配在另一个链表中，也可能分配到上面的那个链表中
                for (HashEntry<K,V> p = e; p != lastRun; p = p.next) {
                    V v = p.value;
                    int h = p.hash;
                    int k = h & sizeMask;
                    HashEntry<K,V> n = newTable[k];
                    newTable[k] = new HashEntry<K,V>(h, p.key, v, n);
                }
            }
        }
    }
    // 将新来的 node 放到新数组中刚刚的 两个链表之一 的 头部
    int nodeIndex = node.hash & sizeMask; // add the new node
    node.setNext(newTable[nodeIndex]);
    newTable[nodeIndex] = node;
    table = newTable;
}

这里的扩容比之前的 HashMap 要复杂一些，代码难懂一点。上面有两个挨着的 for 循环，第一个 for 有什么用呢？如果没有第一个 for 循环，也是可以工作的，但是，这个 for 循环下来，如果 lastRun 的后面还有比较多的节点，那么这次就是值得的。因为我们只需要克隆 lastRun 前面的节点，后面的一串节点跟着 lastRun 走就是了，不需要做任何操作。我觉得 Doug Lea 的这个想法也是挺有意思的，不过比较坏的情况就是每次 lastRun 都是链表的最后一个元素或者很靠后的元素，那么这次遍历就有点浪费了。不过 Doug Lea 也说了，根据统计，如果使用默认的阈值，大约只有 1/6 的节点需要克隆。

get

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public V get(Object key) {
        Segment<K,V> s; 
        HashEntry<K,V>[] tab;
        int h = hash(key);
        long u = (((h >>> segmentShift) & segmentMask) << SSHIFT) + SBASE;        //先定位Segment，再定位HashEntry
        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方法无需加锁，由于其中涉及到的共享变量都使用volatile修饰，volatile可以保证内存可见性，所以不会读取到过期数据。

  1. 计算 hash 值，找到 segment 数组中的具体位置，或我们前面用的“槽”
  2. 槽中也是一个数组，根据 hash 找到数组中具体的位置
  3. 到这里是链表了，顺着链表进行查找即可

并发分析

put 操作的线程安全性

  1. 初始化槽，这个我们之前就说过了，使用了 CAS 来初始化 Segment 中的数组。
  2. 添加节点到链表的操作是插入到表头的，所以，如果这个时候 get 操作在链表遍历的过程已经到了中间，是不会影响的。当然，另一个并发问题就是 get 操作在 put 之后，需要保证刚刚插入表头的节点被读取，这个依赖于 setEntryAt 方法中使用的 UNSAFE.putOrderedObject。
  3. 扩容。扩容是新创建了数组，然后进行迁移数据，最后面将 newTable 设置给属性 table。所以，如果 get 操作此时也在进行，那么也没关系，如果 get 先行，那么就是在旧的 table 上做查询操作；而 put 先行，那么 put 操作的可见性保证就是 table 使用了 volatile 关键字。

remove 操作的线程安全性
get 操作需要遍历链表，但是 remove 操作会”破坏”链表。如果 remove 破坏的节点 get 操作已经过去了，那么这里不存在任何问题。如果 remove 先破坏了一个节点，分两种情况考虑。 1、如果此节点是头结点，那么需要将头结点的 next 设置为数组该位置的元素，table 虽然使用了 volatile 修饰，但是 volatile 并不能提供数组内部操作的可见性保证，所以源码中使用了 UNSAFE 来操作数组，请看方法 setEntryAt。2、如果要删除的节点不是头结点，它会将要删除节点的后继节点接到前驱节点中，这里的并发保证就是 next 属性是 volatile 的。

ConcurrentHashMap(1.8)

构造

1
2
3
4
5
6
7
8
9
10
11
// 这构造函数里，什么都不干
public ConcurrentHashMap() {
}
public ConcurrentHashMap(int initialCapacity) {
    if (initialCapacity < 0)
        throw new IllegalArgumentException();
    int cap = ((initialCapacity >= (MAXIMUM_CAPACITY >>> 1)) ?
               MAXIMUM_CAPACITY :
               tableSizeFor(initialCapacity + (initialCapacity >>> 1) + 1));
    this.sizeCtl = cap;
}

方法

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
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
86
87
88
89
90
91
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();
    // 得到 hash 值
    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();

        // 找该 hash 值对应的数组下标，得到第一个节点 f
        else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
            // 如果数组该位置为空，
            //    用一次 CAS 操作将这个新值放入其中即可，这个 put 操作差不多就结束了，可以拉到最后面了
            //          如果 CAS 失败，那就是有并发操作，进到下一个循环就好了
            if (casTabAt(tab, i, null,
                         new Node<K,V>(hash, key, value, null)))
                break;                   // no lock when adding to empty bin
        }
        // hash 居然可以等于 MOVED，这个需要到后面才能看明白，不过从名字上也能猜到，肯定是因为在扩容
        else if ((fh = f.hash) == MOVED)
            // 帮助数据迁移，这个等到看完数据迁移部分的介绍后，再理解这个就很简单了
            tab = helpTransfer(tab, f);

        else { // 到这里就是说，f 是该位置的头结点，而且不为空

            V oldVal = null;
            // 获取数组该位置的头结点的监视器锁
            synchronized (f) {
                if (tabAt(tab, i) == f) {
                    if (fh >= 0) { // 头结点的 hash 值大于 0，说明是链表
                        // 用于累加，记录链表的长度
                        binCount = 1;
                        // 遍历链表
                        for (Node<K,V> e = f;; ++binCount) {
                            K ek;
                            // 如果发现了"相等"的 key，判断是否要进行值覆盖，然后也就可以 break 了
                            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;
                        }
                    }
                }
            }
            // binCount != 0 说明上面在做链表操作
            if (binCount != 0) {
                // 判断是否要将链表转换为红黑树，临界值和 HashMap 一样，也是 8
                if (binCount >= TREEIFY_THRESHOLD)
                    // 这个方法和 HashMap 中稍微有一点点不同，那就是它不是一定会进行红黑树转换，
                    // 如果当前数组的长度小于 64，那么会选择进行数组扩容，而不是转换为红黑树
                    //    具体源码我们就不看了，扩容部分后面说
                    treeifyBin(tab, i);
                if (oldVal != null)
                    return oldVal;
                break;
            }
        }
    }
    // 
    addCount(1L, binCount);
    return null;
}

初始化数组 initTable()

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
private final Node<K,V>[] initTable() {
    Node<K,V>[] tab; int sc;
    while ((tab = table) == null || tab.length == 0) {
        // 初始化的"功劳"被其他线程"抢去"了
        if ((sc = sizeCtl) < 0)
            Thread.yield(); // lost initialization race; just spin
        // CAS 一下，将 sizeCtl 设置为 -1，代表抢到了锁
        else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
            try {
                if ((tab = table) == null || tab.length == 0) {
                    // DEFAULT_CAPACITY 默认初始容量是 16
                    int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
                    // 初始化数组，长度为 16 或初始化时提供的长度
                    Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
                    // 将这个数组赋值给 table，table 是 volatile 的
                    table = tab = nt;
                    // 如果 n 为 16 的话，那么这里 sc = 12
                    // 其实就是 0.75 * n
                    sc = n - (n >>> 2);
                }
            } finally {
                // 设置 sizeCtl 为 sc，我们就当是 12 吧
                sizeCtl = sc;
            }
            break;
        }
    }
    return tab;
}

链表转红黑树: treeifyBin

前面我们在 put 源码分析也说过，treeifyBin 不一定就会进行红黑树转换，也可能是仅仅做数组扩容。我们还是进行源码分析吧。

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
private final void treeifyBin(Node<K,V>[] tab, int index) {
    Node<K,V> b; int n, sc;
    if (tab != null) {
        // MIN_TREEIFY_CAPACITY 为 64
        // 所以，如果数组长度小于 64 的时候，其实也就是 32 或者 16 或者更小的时候，会进行数组扩容
        if ((n = tab.length) < MIN_TREEIFY_CAPACITY)
            // 后面我们再详细分析这个方法
            tryPresize(n << 1);
        // b 是头结点
        else if ((b = tabAt(tab, index)) != null && b.hash >= 0) {
            // 加锁
            synchronized (b) {

                if (tabAt(tab, index) == b) {
                    // 下面就是遍历链表，建立一颗红黑树
                    TreeNode<K,V> hd = null, tl = null;
                    for (Node<K,V> e = b; e != null; e = e.next) {
                        TreeNode<K,V> p =
                            new TreeNode<K,V>(e.hash, e.key, e.val,
                                              null, null);
                        if ((p.prev = tl) == null)
                            hd = p;
                        else
                            tl.next = p;
                        tl = p;
                    }
                    // 将红黑树设置到数组相应位置中
                    setTabAt(tab, index, new TreeBin<K,V>(hd));
                }
            }
        }
    }
}

扩容：tryPresize

如果说 Java8 ConcurrentHashMap 的源码不简单，那么说的就是扩容操作和迁移操作。这个方法要完完全全看懂还需要看之后的 transfer 方法，读者应该提前知道这点。这里的扩容也是做翻倍扩容的，扩容后数组容量为原来的 2 倍。

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
// 首先要说明的是，方法参数 size 传进来的时候就已经翻了倍了
private final void tryPresize(int size) {
    // c：size 的 1.5 倍，再加 1，再往上取最近的 2 的 n 次方。
    int c = (size >= (MAXIMUM_CAPACITY >>> 1)) ? MAXIMUM_CAPACITY :
        tableSizeFor(size + (size >>> 1) + 1);
    int sc;
    while ((sc = sizeCtl) >= 0) {
        Node<K,V>[] tab = table; int n;

        // 这个 if 分支和之前说的初始化数组的代码基本上是一样的，在这里，我们可以不用管这块代码
        if (tab == null || (n = tab.length) == 0) {
            n = (sc > c) ? sc : c;
            if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
                try {
                    if (table == tab) {
                        @SuppressWarnings("unchecked")
                        Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
                        table = nt;
                        sc = n - (n >>> 2); // 0.75 * n
                    }
                } finally {
                    sizeCtl = sc;
                }
            }
        }
        else if (c <= sc || n >= MAXIMUM_CAPACITY)
            break;
        else if (tab == table) {
            // 我没看懂 rs 的真正含义是什么，不过也关系不大
            int rs = resizeStamp(n);

            if (sc < 0) {
                Node<K,V>[] nt;
                if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
                    sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
                    transferIndex <= 0)
                    break;
                // 2. 用 CAS 将 sizeCtl 加 1，然后执行 transfer 方法
                //    此时 nextTab 不为 null
                if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
                    transfer(tab, nt);
            }
            // 1. 将 sizeCtl 设置为 (rs << RESIZE_STAMP_SHIFT) + 2)
            //     我是没看懂这个值真正的意义是什么？不过可以计算出来的是，结果是一个比较大的负数
            //  调用 transfer 方法，此时 nextTab 参数为 null
            else if (U.compareAndSwapInt(this, SIZECTL, sc,
                                         (rs << RESIZE_STAMP_SHIFT) + 2))
                transfer(tab, null);
        }
    }
}

个方法的核心在于 sizeCtl 值的操作，首先将其设置为一个负数，然后执行 transfer(tab, null)，再下一个循环将 sizeCtl 加 1，并执行 transfer(tab, nt)，之后可能是继续 sizeCtl 加 1，并执行 transfer(tab, nt)。所以，可能的操作就是执行 1 次 transfer(tab, null) + 多次 transfer(tab, nt)，这里怎么结束循环的需要看完 transfer 源码才清楚

HashMap和ConcurrentHashMap源码jkd7~8全解析

分享到：