一切福田，不離方寸，從心而覓，感無不通。

JDK7 和 JDK8 的 HashMap

一、HashMap 的存储结构键值均可为 null

JDK7 的 HashMap

JDK7 的 HashMap 的存储结构其实就是哈希表的存储结构(由数组与链表结合组成，称为链表的数组)。如下图：

HashMap的存储结构-JDK7

HashMap 的主干是一个 Entry 数组。Entry 是 HashMap 的基本组成单元，每一个 Entry 包含一个 key-value 键值对。当发生 hash 冲突时，数组节点则会变成一个链表，用于存储 hash 冲突的数据。

如上图，HashMap 中元素存储的形式是 key-value 键值对，即 Entry 对。一个长度为 16 的数组中，每个元素存储的是一个链表的头结点。这些元素是按照什么样的规则存储到数组中呢？一般是通过 hash(key.hashCode())%len 获得，也就是元素的 key 的哈希值对数组长度取模得到。上述哈希表中，12%16=12；28%16=12；108%16=12；140%16=12。所以 12、28、108 以及 140 都存储在数组下标为 12 的位置。

JDK8 的 HashMap

当链表长度超过阈值(TREEIFY_THRESHOLD) 8，table 的长度大于 64如果小于 64，就通过扩容的方式来解决，避免红黑树结构化链表转换为红黑树。

HashMap的存储结构-JDK8

区别：

1️⃣JDK7：new HashMap() 时，底层创建 size 为 16 的数组Entry[]。

2️⃣JDK8：首次调用 put() 时，底层创建 size 为 16 的数组Node[]。

3️⃣JDK7 底层：数组+链表。JDK8 底层：数组+链表+红黑树。
当数组某个索引位置的元素以链表形式存在的数据个数 >8 且当前数组的长度 >64 时，该索引位置上的所有数据改为使用红黑树存储。

4️⃣新节点插入到链表的顺序不同：JDK7—头插法因为插入头部效率高，不需要遍历整个链表，JDK8—尾插法。

1
2
3
4
5
6
//JDK7 的头插法：addEntry 的 createEntry 方法：
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++;
}

 

道理很简单，就是创建一个 Entry，该 Entry 的 next 是 e(参照new Entry<>(hash,key,value,e)的实现)，这个 e 就是之前的头结点，然后把当前 table 的位置放上新建的 Entry，也就是插入在链表的头部了。

1
2
3
4
5
6
7
8
//JDK8  的尾插法，putVal 的一段代码：
if ((e = p.next) == null) {
  p.next = newNode(hash, key, value, null);
  if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
    treeifyBin(tab, hash);
    break;
  }
...

 

JDK8 链表大于 8 的时候要树化，需要遍历算该链表的长度，直接把数据放到后面，这样方便，减少了把数据移动到头数组位置这一步，效率也提高了。而且，JDK7 中出现的 HashMap 死循环 bug 不会有了，因为这里是只是平移，没有调换顺序。

5️⃣JDK8 的 hash 算法有所简化
JDK7 默认初始化大小 16，加载因子 0.75。如果传入了 size，会变为大于等于当前值的 2 的 n 次方的最小的数。

1
2
// Find a power of 2 >= toSize
int capacity = roundUpToPowerOf2(toSize);

 

为什么是 2 的幂次方？

因为确定下标位置的 indexFor 方法，h&(length-1)。length 是 2 的次方，那么 length-1 总是 0001 1111 等后面都是 1 的数，h& 它之后，其实就相当于取余，与的效率比取余高，所以用了这种方式达到高效率。下面是 JDK7 的 indexfor 的实现：

1
2
3
4
5
6
7
/**
* Returns index for hash code h.
*/
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);
}

 

二、JDK7 的 HashMap 底层实现原理

put方法实现原理

HashMap map = new HashMap();
在实例化后，底层创建了 size 为 16 的一维数组 Entry[] table。
map.put(key1,value1);
首先，调用 key1 所在类的 hashcode() 计算 key1 的哈希值，此哈希值经过某种算法以后，得到在 Entry 数组中的存放位置。
1️⃣如果此位置上的数据为空，此时的 key1-value1 添加成功。【情况一】
2️⃣如果此位置上的数据不为空，(意味着此位置上存在一个或多个数据以链表形式存在)，比较 key1 和已经存在的一个或多个数据的哈希值：
①如果 key1 的哈希值与已经存在的数据的哈希值都不相同，此时 key1-value1 添加成功。【情况二】
②如果 key1 的哈希值和已经存在的某一个数据(key2-value2)的哈希值相同，然后调用 key1 所在类的 equals(key2) 继续比较。如果返回 false：此时 key1-value1 添加成功。【情况三】
如果返回 true：使用 value1 替换 value2。【情况四】
说明：【情况二】和【情况三】此时 key1-value1 和原来的数据以链表的方式存储。在不断的添加过程中，当超出临界值(map 中元素总数超过 Entry 数组的 75%)，且要存放的位置非空时，为了减少链表长度，元素分配更均匀，触发扩容操作。默认的扩容方式：扩容为原来容量 size 的 2 倍，并将原有的数据复制过来，size 一定为 2 的 n 次幂。扩容针对整个 Map。每次扩容时，原来数组中的元素依次重新计算存放位置，并重新插入。插入元素后才判断该不该扩容，有可能无效扩容(插入后如果扩容，如果没有再次插入，就会产生无效扩容)。

hashCode 是定位，确定存储位置；equals 是定性，比较两者是否相等。

get方法实现原理

与 put 类似，会首先调用 Key 值中的 hashCode()，用于获取对应的 bucket 的下标值，找到 bucket 的位置后，再通过 key.equals() 找到对应的键值对，从而获得对应的 value 值。

三、JDK7 的 HashMap 源码分析

属性信息

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
/**
* The default initial capacity - MUST be a power of two.
*/
//Hashmap的初始化大小，默认容量为 16，也可以构造时指定
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
 
/**
* The maximum capacity, used if a higher value is implicitly specified
* by either of the constructors with arguments.
* MUST be a power of two <= 1<<30.
*/
//HashMap是动态扩容的，最大支持容量为 2^30
static final int MAXIMUM_CAPACITY = 1 << 30;
 
/**
* The load factor used when none specified in constructor.
*/
//默认的扩容因子，这个值可以通过构造修改
static final float DEFAULT_LOAD_FACTOR = 0.75f;
 
/**
* An empty table instance to share when the table is not inflated.
*/
//空数据，默认构造的时候赋值为空的Entry数组，在添加元素的时候
//会判断table=EMPTY_TABLE ，然后就扩容
static final Entry<?,?>[] EMPTY_TABLE = {};
 
/**
* The table, resized as necessary. Length MUST Always be a power of two.
*/
//表示一个空的Hashmap
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
 
/**
* The number of key-value mappings contained in this map.
*/
//Hashmap的大小
transient int size;
 
/**
* The next size value at which to resize (capacity * load factor).
* @serial
*/
// If table == EMPTY_TABLE then this is the initial capacity at which the
// table will be created when inflated.
//初始容量，如果构造传入的值是12，那么这个值就是12，如果没有传入就是默认的容量
//DEFAULT_INITIAL_CAPACITY=16
//扩容的阈值
int threshold;
 
/**
* The load factor for the hash table.
*
* @serial
*/
//扩容因子，没有传入就使用默认的DEFAULT_LOAD_FACTOR = 0.75f
final float loadFactor;
 
/**
* The number of times this HashMap has been structurally modified
* Structural modifications are those that change the number of mappings in
* the HashMap or otherwise modify its internal structure (e.g.,
* rehash).  This field is used to make iterators on Collection-views of
* the HashMap fail-fast.  (See ConcurrentModificationException).
*/
//数据操作次数，用于迭代检查修改异常
transient int modCount;
 
/**
* The default threshold of map capacity above which alternative hashing is
* used for String keys. Alternative hashing reduces the incidence of
* collisions due to weak hash code calculation for String keys.
* <p/>
* This value may be overridden by defining the system property
* {@code jdk.map.althashing.threshold}. A property value of {@code 1}
* forces alternative hashing to be used at all times whereas
* {@code -1} value ensures that alternative hashing is never used.
*/
static final int ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE;

 

构造方法

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
//这个构造方法是传入初始容量和扩容因子
//当需要扩容的时候，根据扩容因子计算进行扩容
public HashMap(int initialCapacity, float loadFactor) {
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " +
                                           initialCapacity);
                                          
      //当初始容量太大，大于了允许的最大值时，使用最大值                                    
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
        //判断加载因子必须是大于0,而且必须是数字
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " +
                                           loadFactor);
 
    this.loadFactor = loadFactor;
    threshold = initialCapacity;
    init();
}
public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public HashMap() {
    this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
//初始化时将一个Map集合放入新创建的HashMap
public HashMap(Map<? extends K, ? extends V> m) {
    this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
                  DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
    inflateTable(threshold);
 
    putAllForCreate(m);
}

 

put方法

JDK 的底层源码很多都用到了位运算，先回顾下：

左移<<：高位舍掉，低位补0
右移>>：低位舍掉，高位补0；

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
public V put(K key, V value) {
    //在实例化HashMap的时候，只是将初始化容量值赋值了。
    //但是没有初始化数组，所以第一次进来的话，
    //table==EMPTY_TABLE 肯定是成立的。而且会初始化数组
    if (table == EMPTY_TABLE) {
        inflateTable(threshold);
    }
    if (key == null)
        return putForNullKey(value);
   //这里是得到通过key计算出来的hash值，这个hash值通过
   //位移运算和hashseed进行位运算得到    
    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;
}
private void inflateTable(int toSize) {
    // Find a power of 2 >= toSize
    //官方的解释：找到一个大于等于toSize的2的幂次方
    int capacity = roundUpToPowerOf2(toSize);
 
    //记录下一次扩容的阈值大小，
    //这边计算是通过本次初始的容量* 扩容因子
    //得到的值作为下一次扩容的阈值大小
    //当添加元素的数组大小大于等于阈值了，就需要进行扩容
    threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
    table = new Entry[capacity];
    initHashSeedAsNeeded(capacity);
}
private static int roundUpToPowerOf2(int number) {
    // assert number >= 0 : "number must be non-negative";
    return number >= MAXIMUM_CAPACITY
            ? MAXIMUM_CAPACITY
            : (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;
}

 

int capacity = roundUpToPowerOf2(toSize)
官方的解释：找到一个 2 的幂次方数，要求大于等于toSize(初始化的容量大小)。比如传入的容量是 12，那么最终初始化的容量就是 16；如果是 15，也是 16；如果是 17，则就是 32，反正就是大于等于该数的 2 的幂次方的最小值。

return number >= MAXIMUM_CAPACITY ? MAXIMUM_CAPACITY : (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;
这行代码的使用了两个三目运算符。第一个运算符比较简单，就是要设置的数组大小是否大于了允许的最大容量，如果大于则使用最大的容量，否则又一个三目运算符。这个是重点，假如传入的是 11：

(num -1) << 1等价于“10 << 1”也就是 10 左移一位，表示为

1
2
10 的二进制：0000 1010
    10 << 1：0001 0100 也就是 20

 

然后看Integer.highestOneBit：

1
2
3
4
5
6
7
8
9
public static int highestOneBit(int i) {
    // HD, Figure 3-1
    i |= (i >>  1);
    i |= (i >>  2);
    i |= (i >>  4);
    i |= (i >>  8);
    i |= (i >> 16);
    return i - (i >>> 1);
}

 

传入的是 20，二进制是：0001 0100。执行i |= (i >> 1);

1
2
3
i：     0001 0100
i >> 1：0000 1010
|：     0001 1110

 

得到结果：0001 1110。执行i |= (i >> 2);

1
2
3
i：     0001 1110
i >> 2：0000 0111
|：     0001 1111

 

得到的结果：0001 1111。执行i |= (i >> 4);

1
2
3
i：     0001 1111
i >> 4：0000 0001
|：     0001 1111

 

得到的结果：0001 1111。执行i |= (i >> 8);

1
2
3
i：     0001 1111
i >> 8：0000 0000
|：     0001 1111

 

得到的结果： 0001 1111。执行i |= (i >> 16);

1
2
3
i：      0001 1111
i >> 16：0000 0000
|：      0001 1111

 

得到的结果： 0001 1111。执行return i - (i >>> 1);

1
2
3
i：          0001 1111
i>>>1：      0000 1111
i-(i >>> 1)：0001 0000

 

最终的结果：0001 0000，十进制就是 16 。传入的初始容量是 11，实际初始化的容量是 16，也就验证了Find a power of 2 >= toSize，找到一个 2 的幂次方数并且大于等于 toSize，toSize 就是传入的 11。

这个操作的规律就是最终的结果不是 4 个 0 就是 4 个 1，它将低位的 1 尽量的移动到高位去，不管移动多少位，反正取 ”与“ 后的结果肯定还是 ”与“ 之前的结果。

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

 

这个方法就是 hashmap 计算 key 的 hash 值方法，比较复杂，大体意思就是将 key 的 hash 值计算出来然后做位运算，为什么要右移这么多，核心思想就是避免出现太多了 hash 冲突。因为取余都是操作低位，hash 碰撞的概率会提高，为了减少 hash 碰撞，右移就可以将高位也参与运算，减少了 hash 碰撞。

1
2
3
4
5
6
7
8
9
10
11
12
13
private V putForNullKey(V value) {
    for (Entry<K,V> e = table[0]; e != null; e = e.next) {
        if (e.key == null) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }
    modCount++;
    addEntry(0, null, value, 0);
    return null;
}

 

上面方法当 key==null 的时候调用，HashMap 允许传入一个 null 作为 key。如果是 null 的 key，默认放在第一位，也就是数组为 0 的位置，当放置 null key 的时候，第 0 个位置已经被占用了，这个时候就会存在第 0 个位置的链表上。
上面代码可以看出 for 循环中是从数组的第一个位置开始循环的，也就是说 key = null 的数据是放在数组为 0 的位置上或者数组为 0 的链表上。上面方法是要返回一个值的，如果添加 key = null 的数据的时候，这个 null key 已经有了，那么会替换这个新的值，然后返回之前的值。

1
2
3
4
5
6
7
8
9
10
11
void addEntry(int hash, K key, V value, int bucketIndex) {
    if ((size >= threshold) && (null != table[bucketIndex])) {
        //扩容的大小为原来数组长度的2倍，比如当前长度16，扩容
        //后就是32(注意是 table 长度，而不是 threshold)
        resize(2 * table.length);
        hash = (null != key) ? hash(key) : 0;
        bucketIndex = indexFor(hash, table.length);
    }
//创建一个Entry存放添加的元素
    createEntry(hash, key, value, bucketIndex);
}

 

上面方法就是添加元素，也就是 put 方法的核心逻辑处理，首先判断当前的 map 的 size 是否大于了这个阈值，这个阈值初始化长度为 16(构造 hashmap 为空的情况下)，当第一次 put 的时候会计算数组的初始长度然后这个阈值(=16 * 扩容因子)；所以当 size 大于等于阈值过后，并且要添加的这个鼠标下标位置已经有值了就开始扩容;

扩容

数据量很大的情况下，扩容将会带来性能的损失。在性能要求很高的地方，这种损失很可能很致命。

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
//这个newCapacity默认是扩容前的2倍，
void resize(int newCapacity) {
    //首先声明一个Entry数组用来存放原来的数组信息
    Entry[] oldTable = table;
    //得到原来的数组长度，然后判断扩容的大小是否已经达到了最大的长度，
    //如果大于了数组的最大长度，那么就设置阈值为最大数组的长度，则下次无法再扩容了
    int oldCapacity = oldTable.length;
    if (oldCapacity == MAXIMUM_CAPACITY) {
        threshold = Integer.MAX_VALUE;
        return;
    }
    //声明新的数组信息
    Entry[] newTable = new Entry[newCapacity];
    //数据的元素转移，就是讲oldTable转移到newTable中
    transfer(newTable, initHashSeedAsNeeded(newCapacity));
    table = newTable;
    threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
//这个方法是干什么的呢？
//简单来说就是currentAltHashing 和useAltHashing异或如果为true
//那么hashSeed就会重新赋值，那么什么时候为true呢?
//比如说第一次初始化的时候hashSeed肯定是0，所以currentAltHashing  false
//而useAltHashing 主要是由Holder.ALTERNATIVE_HASHING_THRESHOLD来控制的
//根据下图来看，主要由jdk.map.althashing.threshold这个参数控制
//这个参数可以在运行参数中设置 -Djdk.map.althashing.threshold=3，比如为3
//那么useAltHashing 就很有可能为true，那么switching就会ture，那么
//hashseed就会重新计算值，就不是0了，那么这个值到底有什么用呢？
//这个值的用途在transfer方法中，其实它的用法其实就是为了使hash算法
//变得更复杂一些，也就是更散列一些，其实就是这个作用，更散列一些，计算出来
//的下标也就更好一些
final boolean initHashSeedAsNeeded(int capacity) {
    boolean currentAltHashing = hashSeed != 0;
    boolean useAltHashing = sun.misc.VM.isBooted() &&
            (capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
    boolean switching = currentAltHashing ^ useAltHashing;
    if (switching) {
        hashSeed = useAltHashing
            ? sun.misc.Hashing.randomHashSeed(this)
            : 0;
    }
    return switching;
}
//扩容的核心方法，就是讲原来的数组复制到新的数组中
void transfer(Entry[] newTable, boolean rehash) {
    int newCapacity = newTable.length;
    //这里使用了2层循环来进行数组的复制，为什么要使用2层循环呢？
    //因为hashmap是一般的数组结构，在数组元素上的单向链表结构，所以如果发生了数组
    //的扩容，需要两层循环来操作
    for (Entry<K,V> e : table) {
        while(null != e) {
            Entry<K,V> next = e.next;
            //hashSedd的判断
            if (rehash) {
                //使hash更散列一些
                e.hash = null == e.key ? 0 : hash(e.key);
            }
            int i = indexFor(e.hash, newCapacity);
            //通过hash计算出来的下标，
            //在新的数组中赋值给原来数组的next
            //其实就是新的数组下标引用了原来的下标数据的引用地址            
            e.next = newTable[i];
            //将本次元素与原来解除关系过后，将引用变成原有的地址
            //具体看图
            newTable[i] = e;
            e = next;
        }
    }
}

 

扩容数组移动图

上图就是transfer方法的2层循环执行的过程

CreateEntry

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

 

如果有需要扩容，扩容完成过后就进行最后一步添加Entry元素，看第二行代码，第二行代码是
Entry<K,V> e = table[bucketIndex]，这个e可能为空，也可能不为空，当e为空的时候，那么证明这个下标上还没有元素被添加，那么bucketIndex位置上直接存放添加的元素即可；如果不为空，则证明bucketIndex上已经存在元素了，那么这个时候就要添加到bucketIndex的链表上，因为hashmap的链表默认是单向链表，Hashmap的单向链表默认是头插法，根据扩容的流程图就可以知道，所以当e不为空的时候，那么这个元素默认在头部，其他元素往下移，也就有了 table[bucketIndex] = new Entry<>(hash, key, value, e)这句代码的含义。

Entry的基本结构

就根据createEntry方法来了解下Entry的数据结构，大概了解一下即可

1
2
3
4
5
6
Entry(int h, K k, V v, Entry<K,V> n) {
    value = v;
    next = n;
    key = k;
    hash = h;
}

 

这是HashMap在put的时候最后调用createEntry的方法，这个方法有4个参数
int h:可以对应的hash值；
K k：key的明文值；
V v：put的值；

Entry<k,v> n:这个值可空，可不为空，如果put的时候，n不为空，那么n就是这个位置上的（包括链表上）的所有节点元素，如果为空，则也就为空，什么意思呢？就是这个位置有添加的一个当前put的元素，它的下一个是null，比如添加的元素是abc，如图：

get获取元素

get获取元素比较简单，就算没有看过源码，也大概能够猜出来，不就是根据key循环HashMap的Entry数组嘛，找到key相等的就返回，这是我初探HashMap源码时，带着这种思维去看的，所以看源码先要理解它的原理，带着原理快速过一遍源码，刚开始不要纠结细节，否则你看源码的兴趣可能在半小时左右，你专到一个方法细节里面出不来，半小时过后可能就失去兴趣了，所以要根据自己所猜的原理去快速过一遍，然后后面再慢慢理细节。

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
public V get(Object key) {
    //如果Key为空，那么就找到Entry数组中key==null的一个元素Entry
    //在HashMap中是允许Null key和Null value的
    if (key == null)
        return getForNullKey();
        //循环Entry数组，根据找到对应的value
    Entry<K,V> entry = getEntry(key);
 
    return null == entry ? null : entry.getValue();
}
//这个方法比较简单，就是在table中找到一个null key的Entry，然后返回
private V getForNullKey() {
    if (size == 0) {
        return null;
    }
    for (Entry<K,V> e = table[0]; e != null; e = e.next) {
        if (e.key == null)
            return e.value;
    }
    return null;
}
final Entry<K,V> getEntry(Object key) {
    if (size == 0) {
        return null;
    }
 
    int hash = (key == null) ? 0 : hash(key);
    //根据key找到Entry，这里的循环很简单，就是根据传进来的的key
    //计算出来一个hash，然后通过IndexFor找到指定的位置
    //然后在这个位置上循环单向链表，找到对应的key，然后返回这个
    //key对应的Entry对象
    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;
}

 

删除元素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
public V remove(Object key) {
    Entry<K,V> e = removeEntryForKey(key);
    return (e == null ? null : e.value);
}
//根据key删除元素和get差不不大，都是新通过key计算hash
//然后再通过indexFor得到要删除的元素所在的位置
//然后循环，找到要删除元素的key，这里删除使用的是链表出队的方式
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) {
        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
                prev.next = next;
            e.recordRemoval(this);
            return e;
        }
        prev = e;
        e = next;
    }
 
    return e;
}

 

在remove或者put的时候都有代码，modCount++和size++ / size–
size其实很好理解，就是Hashmap的真实元素个数，而不是数组长度，这个元素个数在一定程度上可能大于数组长度，因为有链表结构；
而这个modCount是什么呢？这个涉及到一个异常，修改异常ConcurrentModificationException，也就是fast-fail（快速失败）是HashMap的一种自我保护模式，就是说在迭代的时候是不循环对map进行添加或者删除的，所以个modCount表示的是对map的操作次数，只是改变数组元素时候会记录这个modCount，所以在迭代的时候声明一个期望值=modCount，然后每次迭代判断这个期望值是否还是等于modCout，如果不等于，则抛出异常，是一种快速失败的模式。
Hashmap的其他的api就不做记录了，其实都差不多，都是围绕Entry这个来展开进行操作的，没有什么太多太难的地方，理解原理和思想即可。

四、JDK8 的 HashMap 源码分析

1️⃣HashMap的默认容量 16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
2️⃣HashMap的最大支持容量 2^30
static final int MAXIMUM_CAPACITY = 1 << 30;
3️⃣HashMap的默认加载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
4️⃣Bucket中链表长度大于该默认值，转化为红黑树
static final int TREEIFY_THRESHOLD = 8;
5️⃣Bucket中红黑树存储的Node小于该默认值，转化为链表
static final int UNTREEIFY_THRESHOLD = 6;
6️⃣桶中的Node被树化时最小的hash表容量。(当桶中Node的数量大到需要变红黑树时，若hash表容量小于MIN_TREEIFY_CAPACITY时，此时应执行resize扩容操作，这个MIN_TREEIFY_CAPACITY的值至少是 TREEIFY_THRESHOLD的4倍)
static final int MIN_TREEIFY_CAPACITY = 64;
7️⃣table：存储元素的数组，总是 2 的 n 次幂。
8️⃣entrySet：存储具体元素的集
9️⃣size：HashMap中存储的键值对的数量
🔟modCount：HashMap扩容和结构改变的次数。
1️⃣1️⃣threshold：扩容的临界值，=容量*填充因子
1️⃣2️⃣loadFactor：填充因子

静态成员常量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class HashMap {
    //默认数组的初始值是16，必须为2的倍数
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
    //数组的最大值。2^30
    static final int MAXIMUM_CAPACITY = 1 << 30;
    //默认加载因子，0.75，和数组大小一起使用
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    //默认转换为红黑树的阈值
    static final int TREEIFY_THRESHOLD = 8;
    //默认从红黑树转为链表的阈值
    static final int UNTREEIFY_THRESHOLD = 6;
    //默认转换为红黑树后最小的红黑树容量
    static final int MIN_TREEIFY_CAPACITY = 64;
}

 

成员变量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class HashMap<K, V> {
//一开分析的 `储存数据的数组`
transient java.util.HashMap.Node<K,V>[] table;
 
//用于entrySet()和values()，返回一个迭代器遍历Map结构
transient Set<Map.Entry<K,V>> entrySet;
 
//整个hashmap 所包含的节点数
transient int size;
 
//hashmap 的结构修改次数，比如 Put，remove的次数,
//和上面的 迭代器配合使用，在迭代过程中，如果其它线程更改了这个值，
//则会抛出 `ConcurrentModificationException`异常
transient int modCount;
 
//hashmap扩容的阈值，值为 loadFactor*table.length e.g: 0.75 * 16 = 12
//也就是说默认是当数组大小超过 12时就会进行数组扩容
int threshold;
 
//加载因子，默认值上图已经说明
final float loadFactor;
}

 

Node类的成员变量

1
2
3
4
5
6
static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;
}

 

key、key 的 hash 值、key 对应的 value 和下一个节点的引用，其中链表的形成就是 next 这个引用的作用。

put()

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

 

很清楚，通过 hash(key) 获取到了 key 的 hash 值，然后调用了 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
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);
                        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;
}

 

这是 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
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
92
93
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
//声明本地变量 tab，p，n，i(提高性能，effective java)
Node<K, V>[] tab;
Node<K, V> p;
int n, i;
//将成员变量 table 赋值给本地变量 tab，并且将tab的长度赋值给本地变量 n
tab = table;
if (tab != null) {
n = tab.length;
}
/* 如果tab为空或者 数组长度为0，进行初始化，调用 resize()方法，并且获取赋值后的数组长度 */
if (tab == null || n = 0) {
tab = resize();
n = tab.length;
}
/* 根据key的hash值得到当前key在数组中的 位置，赋值给 i */
i = (n - 1) & hash;
/* 将i在数组中对应的key值去除赋值给p，所以p代表当前的key */
p = tab[i];
/* 判断当前数组中取出来的key是否为空（数组中没有），就new一个新的节点，并且放在这个索引 i的位置 */
if (p == null) {
tab[i] = newNode(hash, key, value, null);
/* 如果不为空，那就表示已经有这样的hash 值已经存在了，可能存在hash冲突 或者 直接替换原来的value */
} else {
/* 声明本地变量 e, k */
Node<K, V> e;
K k;
/* 如果取出来的节点 hash值相等，key也和原来的一样（ == 或者 equals方法为true），直接将 这个节点
* p 赋值给刚刚声明的本地变量 e （这个操作很重要，在心中记住）
* 另外这里还将 节点 p的key 赋值给了本地变量 k
* */
if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) {
e = p;
 
/* 如果 hash值一样，但不是同一个 key，则表示hash冲突，接着判断这个节点是不是 红黑树的节点
* 如果是，则生成一个红黑树的节点然后赋值给本地变量 e */
} else if (p instanceof TreeNode) {
e = ((TreeNode<K, V>) p).putTreeVal(this, tab, hash, key, value);
/* 不是红黑树，hash冲突了，这个时候开始扩展链表 */
} else {
/* 声明一个本地变量 binCount，开始遍历 p节点后面的链表 */
for (int binCount = 0; ; ++binCount) {
/* 首先将p节点的 next（链表的下一个）赋值给 本地变量e */
e = p.next;
 
/* 如果e为空，表示p指向的下一个节点不存在，这个时候直接将 新的 key，value放在链表的最末端 */
if (e == null) {
p.next = newNode(hash, key, value, null);
/* 放入后，还要判断下 这个链表的长度是否已经大于等于红黑树的阈值 （前面分析静态成员变量已经说明），
* 一旦大于，就可以变形，调用 treeifyBin方法将原来的链表转化为红黑树 ！
* */
if (binCount >= TREEIFY_THRESHOLD - 1) { // -1 for 1st
treeifyBin(tab, hash);
}
break;
}
/* 如果不为空，表示还没有到链表的末端，
将 e 赋值给 p（p的下一个节点赋值给p），开启下一次循环 */
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) {
break;
}
p = e;
}
}
 
/* e不等于null，则表示 key值相等，替换原来的value即可，
* 这里需要注意，这里不是表示 hash冲突（再观察下前面的分析），
* hash冲突链表的扩展已经在最后一个 else完成了！
* */
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null) {
e.value = value;
}
/* 替换新值后，回调该方法（子类可扩展） */
afterNodeAccess(e);
/* 返回原来的 key对应的旧值 */
return oldValue;
}
}
/* 完成一次 put方法后，加一次 modCount，看前面成员变量分析 */
++modCount;
/* 加入了新节点，把 size 自加，并且 判断是否已经大于要扩容的阈值（观察前面成员变量分析），开始扩容 */
if (++size > threshold)
resize();
 
/* 插入新节点后，回调方法（子类可扩展） */
afterNodeInsertion(evict);
 
/* 插入的新节点，直接返回 null即可 */
return null;
}

 

其中所有代码均已经加上详细注释，这里值得注意的是，由于这个方法没有任何 线程同步手段，所以不论是在查找对应的key，还是扩容，插入节点，增加size，modCount等，肯定会出现问题（这里先预留一篇文章，ConCurrentHashMap源码分析），所以多线程环境下，绝对不能使用HashMap，

而应该使用ConCurrentHashMap。

当然到了现在，那个面试题的答案也已经能够较为完整的回答出来了！

  1. 上面较为详细的分析了put方法后，注意到 resize() 在这个方法中起到了关键作用，初始化，以及扩容。那接着来观察下 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
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;
}

 

这个方法看起来也较为复杂，同样作下简单分析：

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
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;
/* 将原来的数组长度 * 2 判断是否小于最大值，并且原来的数组长度大于 默认初始长度（16）
* 直接双倍扩容， 阈值，长度都 * 2
* */
} 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
/* 第一次调用 resize方法，初始化数组长度，阈值，这里就对应前面成员变量的分析了：
* 阈值 = 加载因子 * 数组长度
* */
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) {
/* 原数组的值先置换为null，帮助gc */
oldTab[j] = null;
/* 如果节点的next不为空（没有形成链表），直接复制到新数组 */
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;
}

 

注释已经简要说明流程，这里可以看出有数组复制以及重新计算hash的操作，所以在实际开发中使用 HashMap 的时候，最好设置一个初始容量，防止经常扩容操作耗费性能！

  1. 好了，HashMap 两个关键方法都分析完毕了，接下来分析 get(key)：
1
2
3
4
public V get(Object key) {
Node<K, V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}

 

get 方法首先通过 hash(key) 获取到了 hash 值，接着通过 getNode(hash) 获取节点，所以重点看下 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
32
33
34
35
36
final Node<K, V> getNode(int hash, Object key) {
/* 声明本地变量，提高性能 */
Node<K, V>[] tab;
Node<K, V> first, e;
int n;
K k;
/* 本地变量赋值，n为数组长度 */
tab = table;
if (tab != null) {
n = tab.length;
}
/* 通过 hash值算出key在数组中的 位置，取出该节点 */
first = tab[n - 1] & hash;
/* 不为空，表示key在数组中存在，接下来开始遍历链表获取红黑树，找出具体位置 */
if (tab != null && n > 0 && first != null) {
/* 如果链表或者红黑树的第一个节点 hash值，key相等，这个节点就是要找的，直接返回 */
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
 
return first;
/* 开始遍历链表 */
if ((e = first.next) != null) {
/* 如果是红黑树，直接按树规则 查找然后返回 */
if (first instanceof TreeNode)
return ((TreeNode<K, V>) first).getTreeNode(hash, key);
do {
/* 遍历链表找到了，返回 */
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
/* 最后没有找到，直接返回null */
return null;
}

 

值得注意的是， 在链表中查找节点采用的是遍历的方式，所以一旦链表过长，查找性能就较慢，这也是为什么 jdk1.8 会在链表长度超过阈值的时候将链表转换为红黑树的原因！链表时间复杂度为O(n)，红黑树为 O(logn)。

五、JDK8 中 HashMap 底层链表转红黑树的阈值为什么是 8？红黑树转链表为什么是 6？

和 hashcode 碰撞次数的泊松分布有关，主要是为了寻找一种时间和空间的平衡。

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

 

1️⃣链表转换为红黑树

红黑树中的 TreeNode 是链表中的 Node 所占空间的 2 倍，虽然红黑树的查找效率为 O(logN)，要优于链表的 O(N)，但是当链表长度比较小的时候，即使全部遍历，时间复杂度也不会太高。所以要寻找一种时间和空间的平衡，即在链表长度达到一个阈值之后再转换为红黑树。链表转换为红黑树的最终目的，是为了解决在 map 中元素过多，hash 冲突较大，而导致的读写效率降低的问题。在源码的 putVal 方法中，有关红黑树结构化的分支为：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//此处遍历链表
for (int binCount = 0; ; ++binCount) {
    //遍历到链表最后一个节点
    if ((e = p.next) == null) {
        p.next = newNode(hash, key, value, null);
        //如果链表元素个数大于等于TREEIFY_THRESHOLD
        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;
}

 

即当链表元素个数大于 8 的时候，就会转换为红黑树。之所以是 8，是因为 Java 的源码贡献者在进行大量实验发现，hash 碰撞发生 8 次的概率非常低，几乎为不可能事件。如果真的发生了 8 次碰撞，说明由于元素本身和 hash 函数的原因，此时的链表性能已经很差了，操作的 hash 碰撞的可能性非常大，后序可能还会继续发生碰撞。所以，在这种极端的情况下才会把链表转换为红黑树，链表转换为红黑树也是需要消耗性能的，大部分情况下 hashMap 还是使用链表。treeifyBin() 源码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    //首先tab的长度是否小于64,
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
    //小于64则进行扩容
        resize();
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        //否则才将列表转换为红黑树
        TreeNode<K,V> hd = null, tl = null;
        do {
            TreeNode<K,V> p = replacementTreeNode(e, null);
            if (tl == null)
                hd = p;
            else {
                p.prev = tl;
                tl.next = p;
            }
            tl = p;
        } while ((e = e.next) != null);
        if ((tab[index] = hd) != null)
            hd.treeify(tab);
    }
}

 

可以看到在 treeifyBin 中并不是简单地将链表转换为红黑树，而是先判断 table 的长度是否大于 64。如果小于 64，就通过扩容的方式来解决，避免红黑树结构化。链表长度大于 8 有两种情况：

  • table 长度足够，hash 冲突过多
  • hash 没有冲突，但是在计算 table 下标的时候，由于 table 长度太小，导致很多 hash 不一致的

第二种情况是可以用扩容的方式来避免的，扩容后链表长度变短，读写效率自然提高。另外，扩容相对于转换为红黑树的好处在于可以保证数据结构更简单。由此可见并不是链表长度超过 8 就一定会转换成红黑树，而是先尝试扩容。

2️⃣红黑树转换为链表

基本思想是当红黑树中的元素减少并小于一定数量时，会切换回链表。而元素减少有两种情况：

  1. 调用 map 的 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
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
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
final Node<K,V> removeNode(int hash, Object key, Object value,
                               boolean matchValue, boolean movable) {
        Node<K,V>[] tab; Node<K,V> p; int n, index;
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (p = tab[index = (n - 1) & hash]) != null) {
            Node<K,V> node = null, e; K k; V v;
            //根据hash值以及key判断当前的是否相等,如果相等直接返回
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                node = p;
            else if ((e = p.next) != null) {
                //判断是否为红黑树结构
                if (p instanceof TreeNode)
                    node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
                else {
                    //如果不是则为链表结构
                    do {
                        if (e.hash == hash &&
                            ((k = e.key) == key ||
                             (key != null && key.equals(k)))) {
                            node = e;
                            break;
                        }
                        p = e;
                    } while ((e = e.next) != null);
                }
            }
            if (node != null && (!matchValue || (v = node.value) == value ||
                                 (value != null && value.equals(v)))) {
                //判断当前桶是否是红黑树结构,如果是的话
                if (node instanceof TreeNode)
                    ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
                else if (node == p)
                    tab[index] = node.next;
                else
                    p.next = node.next;
                ++modCount;
                --size;
                afterNodeRemoval(node);
                return node;
            }
        }
        return null;
    }
 
   final void removeTreeNode(HashMap<K,V> map, Node<K,V>[] tab,
                                  boolean movable) {
            int n;
            if (tab == null || (n = tab.length) == 0)
                return;
            int index = (n - 1) & hash;
            TreeNode<K,V> first = (TreeNode<K,V>)tab[index], root = first, rl;
            TreeNode<K,V> succ = (TreeNode<K,V>)next, pred = prev;
            if (pred == null)
                tab[index] = first = succ;
            else
                pred.next = succ;
            if (succ != null)
                succ.prev = pred;
            if (first == null)
                return;
            if (root.parent != null)
                root = root.root();
            //判断是否解除红黑树结构
            if (root == null || root.right == null ||
                (rl = root.left) == null || rl.left == null) {
                tab[index] = first.untreeify(map);  // too small
                return;
            }
            TreeNode<K,V> p = this, pl = left, pr = right, replacement;
            if (pl != null && pr != null) {
                TreeNode<K,V> s = pr, sl;
                while ((sl = s.left) != null) // find successor
                    s = sl;
                boolean c = s.red; s.red = p.red; p.red = c; // swap colors
                TreeNode<K,V> sr = s.right;
                TreeNode<K,V> pp = p.parent;
                if (s == pr) { // p was s's direct parent
                    p.parent = s;
                    s.right = p;
                }
                else {
                    TreeNode<K,V> sp = s.parent;
                    if ((p.parent = sp) != null) {
                        if (s == sp.left)
                            sp.left = p;
                        else
                            sp.right = p;
                    }
                    if ((s.right = pr) != null)
                        pr.parent = s;
                }
                p.left = null;
                if ((p.right = sr) != null)
                    sr.parent = p;
                if ((s.left = pl) != null)
                    pl.parent = s;
                if ((s.parent = pp) == null)
                    root = s;
                else if (p == pp.left)
                    pp.left = s;
                else
                    pp.right = s;
                if (sr != null)
                    replacement = sr;
                else
                    replacement = p;
            }
            else if (pl != null)
                replacement = pl;
            else if (pr != null)
                replacement = pr;
            else
                replacement = p;
            if (replacement != p) {
                TreeNode<K,V> pp = replacement.parent = p.parent;
                if (pp == null)
                    root = replacement;
                else if (p == pp.left)
                    pp.left = replacement;
                else
                    pp.right = replacement;
                p.left = p.right = p.parent = null;
            }
 
            TreeNode<K,V> r = p.red ? root : balanceDeletion(root, replacement);
 
            if (replacement == p) {  // detach
                TreeNode<K,V> pp = p.parent;
                p.parent = null;
                if (pp != null) {
                    if (p == pp.left)
                        pp.left = null;
                    else if (p == pp.right)
                        pp.right = null;
                }
            }
            if (movable)
                moveRootToFront(tab, r);
        }

 

可以看到，此处并非当节点数小于 UNTREEIFY_THRESHOLD 时才转换，而是通过红黑树根节点及其子节点是否为空来判断。

  1. resize 的时候，对红黑树进行了拆分

resize 的时候，判断节点类型，如果是链表，则将链表拆分，如果是 TreeNode，则执行 TreeNode 的 split 方法分割红黑树，而 split 方法中将红黑树转换为链表的分支如下：

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
final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
            TreeNode<K,V> b = this;
            // Relink into lo and hi lists, preserving order
            TreeNode<K,V> loHead = null, loTail = null;
            TreeNode<K,V> hiHead = null, hiTail = null;
            int lc = 0, hc = 0;
            for (TreeNode<K,V> e = b, next; e != null; e = next) {
                next = (TreeNode<K,V>)e.next;
                e.next = null;
                if ((e.hash & bit) == 0) {
                    if ((e.prev = loTail) == null)
                        loHead = e;
                    else
                        loTail.next = e;
                    loTail = e;
                    ++lc;
                }
                else {
                    if ((e.prev = hiTail) == null)
                        hiHead = e;
                    else
                        hiTail.next = e;
                    hiTail = e;
                    ++hc;
                }
            }
            //在这之前的逻辑是将红黑树每个节点的hash和一个bit进行&运算，
            //根据运算结果将树划分为两棵红黑树，lc表示其中一棵树的节点数
            if (loHead != null) {
                if (lc <= UNTREEIFY_THRESHOLD)
                    tab[index] = loHead.untreeify(map);
                else {
                    tab[index] = loHead;
                    if (hiHead != null) // (else is already treeified)
                        loHead.treeify(tab);
                }
            }
            if (hiHead != null) {
                if (hc <= UNTREEIFY_THRESHOLD)
                    tab[index + bit] = hiHead.untreeify(map);
                else {
                    tab[index + bit] = hiHead;
                    if (loHead != null)
                        hiHead.treeify(tab);
                }
            }
        }

 

这里才用到了 UNTREEIFY_THRESHOLD 的判断，当红黑树节点元素小于等于 6 时，才调用 untreeify 方法转换回链表。红黑树转链表的阈值为 6，主要是因为，如果也将该阈值设置为 8，那么当 hash 碰撞在 8 时，会发生链表和红黑树的不停相互激荡转换，白白浪费资源。中间有个差值 7 可以防止链表和树之间的频繁转换。

3️⃣总结

如果设计成链表个数超过 8 则链表转换成树结构，链表个数小于 8 则树结构转换成链表，HashMap 不停的插入/删除元素，链表个数在 8 左右徘徊，就会频繁的发生红黑树转链表，链表转红黑树，效率会很低下。

  1. hashMap 并不是在链表元素个数大于 8 就一定会转换为红黑树，而是先考虑扩容，扩容达到默认限制后才转换。
  2. hashMap 的红黑树不一定小于 6 的时候才会转换为链表，而是只有在 resize 的时候才会根据 UNTREEIFY_THRESHOLD 进行转换。

六、HashMap 和 HashTable 的区别

  1. HashMap 是线程不安全的，HashTable 是线程安全的。
  2. 由于线程安全，所以 HashTable 的效率比不上 HashMap。
  3. HashMap 最多只允许一条记录的键为 null，允许多条记录的值为 null，而 HashTable不允许。
  4. HashMap 默认初始化数组的大小为 16，扩容时扩大两倍。HashTable 为 11，扩容时扩大两倍 +1。
  5. HashMap 需要重新计算 hash 值，而 HashTable 直接使用对象的 hashCode。

七、HashMap & TreeMap & LinkedHashMap 使用场景？

一般情况下，使用最多的是 HashMap。

  1. HashMap：在 Map 中插入、删除和定位元素时；
  2. TreeMap：在需要按自然顺序或自定义顺序遍历键的情况下；
  3. LinkedHashMap：在需要输出的顺序和输入的顺序相同的情况下。

八、只有 HashMap 可操作 null

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import java.util.HashMap;
import java.util.Hashtable;
import java.util.Map;
import java.util.concurrent.ConcurrentHashMap;
 
public class mapDemo {
    public static void main(String[] args) {
        HashMap map = new HashMap();
        map.put(null, null);
        map.get(null);
        map.remove(null);
        Map table = new Hashtable();
//        table.put(null, "value");//NPE
//        table.put("key",null);//NPE
//        table.get(null);//NPE
//        table.remove(null);//NPE
        ConcurrentHashMap cm = new ConcurrentHashMap();
//        cm.put(null, "value");//NPE
//        cm.put("key", null);//NPE
//        cm.get(null);//NPE
//        cm.remove(null);//NPE
    }
}

 

作者：日常更新
链接：https://www.jianshu.com/p/78989cd553b4
来源：简书
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

Copyright © 2024 Longsheng All rights reserved.