Java 集合学习笔记：HashMap

UML

简介

基于Hash table的Map接口实现。实现了 Map 定义的所有方法，并允许 key 和 value 为 null。(除了非线程安全和允许 null 之外，HashMap 与 Hashtable 大致相同)这个类不保证 map 的顺序；尤其是，它不能保证顺序随时间的推移保持不变。

这个实现为基本操作(get和put)提供了恒定时间的性能，假设 hash 函数将元素适当地分散到桶中。在集合视图上迭代所需的时间与HashMap实例的容量(桶的数量)加上它的大小(键-值映射的数量)成正比。因此，如果迭代性能很重要，就不要将初始容量设置得太高(或负载因子设置得太低)。

HashMap 的实例有两个参数影响其性能：初始容量 和 负载因子。容量是哈希表中桶的数量，初始容量只是哈希表在创建时的容量。负载因子是哈希表在其容量自动增加之前可以达到多满的一种尺度。当哈希表中的条目数超出了负载因子与当前容量的乘积时，则要对该哈希表进行rehash操作（即重建内部数据结构），从而哈希表将具有大约两倍的桶数。

通常，默认负载因子 (0.75) 在时间和空间成本上寻求一种折衷。负载因子过高虽然减少了空间开销，但同时也增加了查询成本（在大多数 HashMap 类的操作中，包括 get 和 put 操作，都反映了这一点）。在设置初始容量时应该考虑到映射中所需的条目数及其负载因子，以便最大限度地减少 rehash 操作次数。如果初始容量大于最大条目数除以负载因子，则不会发生 rehash 操作。

如果很多映射关系要存储在 HashMap 实例中，则相对于按需执行自动的 rehash 操作以增大表的容量来说，使用足够大的初始容量创建它将使得映射关系能更有效地存储。

注意，此实现不是同步的。如果多个线程同时访问一个哈希映射，而其中至少一个线程从结构上修改了该映射，则它必须 保持外部同步。（结构上的修改是指添加或删除一个或多个映射关系的任何操作；仅改变与实例已经包含的键关联的值不是结构上的修改。）这一般通过对自然封装该映射的对象进行同步操作来完成。如果不存在这样的对象，则应该使用 Collections.synchronizedMap 方法来“包装”该映射。最好在创建时完成这一操作，以防止对映射进行意外的非同步访问，如下所示：

Map m = Collections.synchronizedMap(new HashMap(...));
1

由所有此类的“collection 视图方法”所返回的迭代器都是快速失败 的：在迭代器创建之后，如果从结构上对映射进行修改，除非通过迭代器本身的 remove 方法，其他任何时间任何方式的修改，迭代器都将抛出 ConcurrentModificationException。因此，面对并发的修改，迭代器很快就会完全失败，而不冒在将来不确定的时间发生任意不确定行为的风险。

注意，迭代器的快速失败行为不能得到保证，一般来说，存在非同步的并发修改时，不可能作出任何坚决的保证。快速失败迭代器尽最大努力抛出 ConcurrentModificationException 。因此，编写依赖于此异常的程序的做法是错误的，正确做法是：迭代器的快速失败行为应该仅用于检测程序错误。

此类是 Java Collections Framework 的成员。

阅读源码

属性字段

1. 静态属性

2. 成员属性

• 默认都是：null
• transient ：被此关键字修饰的字段不会序列化

HashMap 结构

静态工具方法

hash

计算 key 的 hash 值。为了尽量避免碰撞，使用 异或 和 位移。是出于性能考虑。

• test

@Test
public void hashCodeTest(){
    int h = 0b11111111111111110000000000000000;     // 0b开头表示二进制数
    int i = h >>> 16;                               // 无符号右移16位（包括符号位一起移）
    log.info("{}", Integer.toBinaryString( i ));    // 00000000000000001111111111111111 原本高位的16个1都移到了左边，左边空出的位置补0
    int hash = h ^ i;                               // 异或运算
    log.info("{}", Integer.toBinaryString( hash )); // 11111111111111111111111111111111 i高16位没东西，直接照搬 h，低16位，不同为1，相同为 0
}
1
2
3
4
5
6
7
8

• hash(Object key)

1. 如果 key 为 null 返回 0
2. 否则调用对象的 hashCode() 获取 hash值。
3. ^ + >>>，把 hash 值搅拌一下，尽可能的减少不同 key 出现 hash 相同的情况。

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
1
2
3
4

• public native int hashCode(); Object 的原生方法：返回此对象的 hash 值。

【算法学习】 ^ 加 >>> 减少碰撞

为何要使用异或和位移来减少碰撞？

comparableClassFor(Object x)

如果x的形式是Class C implements Comparable 返回其类的类型。否则为空。

• test
  例如：当 x 的类型 C 和比较器的参数类型 Comparable<C> 一样时就返回 C）

// 形式为 Class C implements Comparable
Class C implements Comparable<C>;
C c = new C;
Class<?> clazz = comparableClassFor(c);
System.out.println(clazz.getName()); // C
// Class C implements Comparable<如果这里不是C> 返回 null
1
2
3
4
5
6

• comparableClassFor(Object x)

1. 检测：给定参数必需实现了 Comparable 否则直接返回 null
2. 如果给定参数是String，直接返回 String.class，因为我们知道String实现了 Comparable
3. 否则：遍历对象实现的所有接口，逐个判断：
   3.1. 如果实现了Comparable 并且泛型参数不为空，则返回此参数类型。

static Class<?> comparableClassFor(Object x) {
	// 如果 x 是 Comparable 的实例。如果是继续，否则返回 null;
    if (x instanceof Comparable) {
    
        Class<?> c; Type[] ts, as; Type t; ParameterizedType p;
        // 如果 x 是个 String 直接返回类型。
        if ((c = x.getClass()) == String.class) // bypass checks
            return c;
        // 获取 c 所实现的接口们（可能有多个所以放数组里）。如果不为 null 继续，否则返回 null;
        if ((ts = c.getGenericInterfaces()) != null) {
        	// 逐个遍历接口类型
            for (int i = 0; i < ts.length; ++i) {
                if (
                	// 1. 如果此接口 t 是某种 ParameterizedType（参数化类型，如 Collection）
                	((t = ts[i]) instanceof ParameterizedType)
                	// 2. 并且，接口 t 的类型正好是 Comparable（为了调用 getRawType() 获取类型，做了强转）
                    && ((p = (ParameterizedType)t).getRawType() == Comparable.class)
                    // 3. 并且，获取 p 的参数类型数组。不为 null。（Comparable就是这里替换 T 的实参）
                    && (as = p.getActualTypeArguments()) != null
                    // 4. 并且，只有 1 个
                    && as.length == 1 
                    // 5. 并且，Comparable<参数> 中的 ‘参数’ == 给定的 x 的类型。
                    && as[0] == c
                 ) 
                 return c;
            }
        }
    }
    return 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

compareComparables(Class kc, Object k, Object x)

如果 x的类型是 kc 就返回 k.compareTo(x) 的结果，否则返回 0。
此方法是要配合上面的 comparableClassFor(Object x) 一起用的。

• test

@Test
public void compareComparablesTest(){
    String k = "jerry1";
    String x = "jerry2";
    Class<?> kc = comparableClassFor(k);
    int i = compareComparables(kc, k, x);
    log.info("{}", i); // -1
}
1
2
3
4
5
6
7
8

• compareComparables(Class kc, Object k, Object x)

k：就是 key，比如类型是我们最见的“字符串”。String 就实现了 Comparable。
kc ： 通过 comparableClassFor(k) 获取 k 实现的 Comparable 中的实参。在 HashMap 的源码 find 、treeify、putTreeVal 这些方法中能看到它的身影。kc 都有先判断 非null 然后才使用。

以下情况中假设 k、x 的类型都是 String

1. x 为 null 直接返回 0 （表示比个毛）
2. kc 是从 k 上获取的比较器 Comparable 的参数的类型 String.class。
   如果 k 没有实现 Comparable 则 kc 为 null，否则 kc 为 String.class
3. x.getClass() != kc 表达的意思是：如果 k 没有实现 Comparable 比较器，就没法比，直接返回 0
   换句话说只有 k 实现了 Comparable 才会执行到 ((Comparable)k).compareTo(x) 这里。

@SuppressWarnings({"rawtypes","unchecked"}) // 压制强转警告
static int compareComparables(Class<?> kc, Object k, Object x) {
    return (x == null 
    		|| x.getClass() != kc ? 0 : ((Comparable)k).compareTo(x));
}
1
2
3
4
5

tableSizeFor(int cap)

返回大于 cap 的最近的一个 2 的倍数。

• test
  以 cap = 50 为例：

@Test
public void tableSizeForTest(){
    int cap = 50;
    int n = cap - 1;	// n: 49。
    int MAXIMUM_CAPACITY = 1 << 30; // 1_073_741_824
    //int x,y;
    //log.info("原值={}; {} = {} | {}; Binary: {} = {} | {} ", x=y=n, x |= x >>> 1, y, y>>>1,Integer.toBinaryString(x), Integer.toBinaryString(y), toBinary(y>>>1, 6));
    n |= n >>> 1;       // 原值=49; 57 = 49 | 24; Binary: 111001 = 110001 | 011000
    n |= n >>> 2;       // 原值=57; 61 = 57 | 28; Binary: 111101 = 111001 | 011100
    n |= n >>> 4;       // 原值=63; 63 = 63 | 31; Binary: 111111 = 111111 | 011111
    n |= n >>> 8;       // 原值=63; 63 = 63 | 31; Binary: 111111 = 111111 | 011111
    n |= n >>> 16;      // 原值=63; 63 = 63 | 31; Binary: 111111 = 111111 | 011111
    n = (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    System.out.println(n); // 64
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

cap：目标容量传进来前已确保 >= 0

static final int tableSizeFor(int cap) { // cap = 50
	// 因为末尾需要 + 1 达到 0111 + 1 = 1000 效果。所以此处配合先 -1
	// 最终效果：确保当 cap 正好是 2的n次方时，最终结果是 cap 本身。
    int n = cap - 1;	
    // 这一通 >>> 与 | 配合下来，使得最高位的 1 不变，右边所有的 0 都变成 1
    // （ 也就是找到最高位并将其右侧所有位都设置成 1 ）
    // 如： 1000 0000 变成 1111 1111; 
    //      0010 1010 变成 0011 1111;
    n |= n >>> 1;		
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    // 小于 0 直接返回 1 ( 2 的 0 次方 )
    // 如果大于最大值直接返回最大值，否则当前值 +1 返回。
    // +1 能保存是 2的二次幂。因为最高位后所有都是 1 时，再+1，肯定是一个 2 的幂。
    // 例：0000 1111 + 1 = 0001 0000 = 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

【算法学习】32 位全置 1

10000000 00000000 00000000 00000000 
01000000 00000000 00000000 00000000 // >>> 1
————————————————————————————————————// 或
11000000 00000000 00000000 00000000 
00110000 00000000 00000000 00000000	// >>> 2
————————————————————————————————————// 或
11110000 00000000 00000000 00000000 
00001111 00000000 00000000 00000000	// >>> 4
————————————————————————————————————// 或
11111111 00000000 00000000 00000000	
00000000 11111111 00000000 00000000	// >>> 8
————————————————————————————————————// 或
11111111 11111111 00000000 00000000
00000000 00000000 11111111 11111111	// >>> 16
————————————————————————————————————// 或
11111111 11111111 11111111 11111111 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

构造方法

HashMap(int initialCapacity, float loadFactor)

指定初始容量和负载因子，构造一个空的 HashMap。

/**
 * @param  initialCapacity 初始容量
 * @param  loadFactor      负载因子
 * @throws 如果【初始容量 < 0】，或【负载因子 <= 0】，抛 IllegalArgumentException
 */
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;
    // 返回大于 initialCapacity 的最小 2 次幂数。
    this.threshold = tableSizeFor(initialCapacity);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

HashMap(int initialCapacity)

指定 初始容量，构造一个空的 HashMap。负载因子 默认 0.75。

/**
 * @param  initialCapacity 初始容量
 * @throws 如果【初始容量 < 0】抛 IllegalArgumentException 
 */
public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR); // DEFAULT_LOAD_FACTOR =  0.75f;
}
1
2
3
4
5
6
7

HashMap()

构造一个空的 HashMap 容量默认16 、负载因子默认0.75

public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // DEFAULT_LOAD_FACTOR =  0.75f; 其它都是默认值。
}
1
2
3

HashMap(Map m)

用指定的 Map，构造一个新的 HashMap。负载因子使用默认的0.75，容量等于给定的 Map 大小。

/**
 * @param   m 用来创建 HashMap 的给定 map
 * @throws  如果给定 map 为空，抛 NullPointerException 
 */
public HashMap(Map<? extends K, ? extends V> m) {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    putMapEntries(m, false);
}
1
2
3
4
5
6
7
8

非 public 方法

putMapEntries 填充当前对象

用给定的 map 填充当前 HashMap。主要是实现 Map.putAll 和 Map 构造 的底层逻辑，供它们调用 .

• putMapEntries(Map m, boolean evict)

1. 如果给定的 map 不为空，继续处理，否则结束。
2. 如果 哈希表表为 null 则先初始化，否则直接检测并按需扩容。
3. 然后遍历给定的 map 填充当前 HashMap

/**
 * @param m 	用来创建 HashMap 的 map
 * @param evict 在最初构造这个 Map 时为 false，否则为true(最终会传给 afternodeinsert 方法 )。                                                                                                                                        
 */
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
	// 取出给定 map 的大小，好用来创建新的 HashMap
    int s = m.size();
    // 没有内容直接跳过
    if (s > 0) {
    	// 为 null 表示尚未初始化
        if (table == null) { // pre-size
        	// 计算所需的初始容量（向上取整尽量避免频繁扩容）
            float ft = ((float)s / loadFactor) + 1.0F;
            // 如果没超最大值，直接使用。否则用最大值。
            int t = ((ft < (float)MAXIMUM_CAPACITY) ? (int)ft : MAXIMUM_CAPACITY);
            // 如果大于扩容阈值，则计算出新的扩容阈值（大于 t 的最小 2 次幂）。
            if (t > threshold) // 初始化时  threshold = 0 必触发
                threshold = tableSizeFor(t);
        // 给定的 map 比当前 HashMap 大。进行扩容。
        } else if (s > threshold)
            resize();
        // 遍历给定的 m 填充当前 HashMap
        for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
            K key = e.getKey();
            V value = e.getValue();
            // 被构造函数调用时 evict = false 
            putVal(hash(key), key, value, false, evict); 
        }
    }
}
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

【算法学习】 尽量避免新 Map 很快触发扩容

分析1：
((float)s / loadFactor) + 1.0F 通过+1.0F 努力避免刚出生没扑腾 put几下就触发扩容的尴尬。
1. (int)( float + 1 ) 的含义是向上取整。常用于小数部分不应舍弃的场景，比如1.5瓶饮料，需要2个瓶子装。
2. 以 s = 12 为例：如不 +1.0F 那么 threshold = (12 / 0.75) = 16 离下一次扩容近在咫尺。构造出来的新 map 几乎一抬脚就要触发一次扩容。
但如果有了 +1.0F 那么 (12 / 0.75) + 1 = 17 经过 tableSizeFor(17) 结果是 32。新 map 可以开心的扑腾put 不用尴尬了。

分析2：
在网上搜了一下，看到有一种说法，如果不+1，舍弃小数，会导致放不下（触发扩容浪费）。但是 size + 1 > size / 0.75 不可能成立，size > size / 0.75 更不可能。
更何况有tableSizeFor(t)的存在，size 要正好是 2的n次方，然后再满足上面的条件。
无论如何，实际PUT的个数永远不可能放不下啊？？？？这个疑惑困扰了我几天5555

分析3：
看了 anlian523-JDK8 HashMap源码 putMapEntries解析 发现：我把程序员们想得太好了，我认为他们会遵守基本的编码规范（如果你不知道为何 loadFactor 是 0.75 请别动它），但是如果有人不用 0.75 非要传一个奇怪的小数，就可能满足 16 + 1 > 16 / 0.95 == true ，所以我是不是可以理解为，这个 +1 不是用来防止容量不够，而是用来防刁民的

getNode 获取结点

按给定的 hash 和 key 获取结点。找到就返回结点，否则返回 null。
注意： 返回 null 不一定是没找到。因为 HashMap 的 Value 也是允许为 null 的。

1. 先判断：当哈希表不为空且目标哈希桶不为空。继续处理，否则返回 null
2. 单独判断桶中的第一个结点，如果 hash、key 都相等，返回此结点。
3. 第一个结点不是要找的目标，就遍历后续所有结点，找到目标就直接返回。
   3.1. 遍历前先判断，如果结点类型是TreeNode 调用树专用的get方法 getTreeNode

    final Node<K,V> getNode(int hash, Object key) {
    	// tab		临时变量缓存哈希表（数组）
    	// first	桶中的第一个结点（可能是链表的头结点，也可能是树的根结点）
    	// n		哈希表的长度
    	// k		临时变量缓存 key
        Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
        // 如果hash桶不为 null 且 长度 > 0，并且桶中第一个结点不为 null 则处理。
        // 否则返回 null
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (first = tab[(n - 1) & hash]) != null) {
            
			// 总是检查第一个结点，如果 hash 和 key 都相等，说明找到目标，直接返回
            if (first.hash == hash &&
                ((k = first.key) == key || (key != null && key.equals(k))))
                return first;

			// 如果头结点不是要找的目标，则继续看下一个是否为空，不为空就继续找。
            if ((e = first.next) != null) {
            	// 判断头结点的类型，是否 TreeNode
            	// 1. 如果是则调用树专用的get方法 getTreeNode
            	// 2. 否则遍历链表逐个查找。找到 hash 和 key 都相等的结点就返回
                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
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

putVal 设置值

• putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict)

1. 检测 哈希表为null，则执行初始化。
2. 如果：按 hash 值算出索引，找到对应的哈希桶，桶为空，直接创建结点填充。
3. 否则：获取桶中第一个结点，然后按 hash 和 key查找目标。
   3.1. 如果是红黑桶会调专用的 putTreeVal 方法。否则遍历链表。
4. 如果找到，修改 value。
5. 如果没找到，说明是新的，追加到末尾。
6. 最后执行一些扫尾工作：更新修改计数、检测是否需要扩容、调回调函数。

/**
 * 用于实现 Map.put 和相关方法。（供它用调用）
 *
 * @param hash 			用 key 算出的 hash 值
 * @param key 			the key
 * @param value 		the value to put
 * @param onlyIfAbsent	如果为 true，则不更改现有值 (只有 putIfAbsent方法调用时会传 true)
 * @param evict			如果为false，则表处于创建模式。
 * @return 				返回原先的值。如果原来没有返回 null
 */
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;
    
    // 用 hash 算出索引，获取对应哈希桶上的第一个结点。
    // 1. 如果：哈希桶为空，则创建新结点并填充。
    // 2. 否则：向链表or树中追加。（当前桶中不为空，则按索引拿到的就是第一个结点）
    // 2.1. 如果：hash相同，key也相同，先选定此结点。（如果头结点不是。接下去需要遍历后续结点）
    // 2.2. 再如果：当前结点是红黑树结点。调用树专用的 putTreeVal 方法处理。
    // 2.3. 否则：遍历链表，找到目标修改 value，找到最后都没有，就追加在尾结点之后。
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
    	// 临时变量：e 用来缓存迭代过程中的当前结点
    	// 临时变量：k 用来缓存迭代过程中当前结点的键
        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) {
            	// 从当前结点 p 中取出下一结点 e
            	// 如果是 null 表示当前就是尾结点，用给定值 new 新结点，追加。
            	//     再判断如果：满足树化条件，传入【数组、hash值】执行树化操作。
            	//     完成后跳出循环。
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                
                // hash 和 key 都一样，这就是我们要找的结点。跳出循环，进行后续操作。
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;

                // 这不是要找的结点，更新 p 指向下一个结点，继续迭代。
                p = e;
            }
        }
        
        // 如果最终找到 hash 和 key 都与给定参数一样的结点。
        if (e != null) { // existing mapping for key
            V oldValue = e.value; // 取出原值
            
            // 有值存在 || 值为null 就更新 value
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
                
            // 调用给 LinkedHashMap 预留的回调函数，处理后续。此方法在HashMap中是空的。
            afterNodeAccess(e);
            return oldValue; // 返回原值
        }
    }
    
    // ========= 末尾追加新结点，会来到这里，需要做一些扫尾工作 =========
    // 更新修改计数。（检测并发冲突用的）
    ++modCount;
    // 所拥有的元素个数 +1，如果大于【扩容阈值】就触发扩容。
    if (++size > threshold)
        resize();
    // 调用给 LinkedHashMap 预留的回调函数，处理后续。此方法在HashMap中是空的。
    afterNodeInsertion(evict);
    return 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
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

【算法学习】 除以 2ⁿ 取余

tab[i = (n - 1) & hash] 用 hash 与 数组长度取模，算出哈希桶位置。

• 2的幂可利用 & 实现取模。
• 公式：(hash % 2^n) == (hash & (2^n)-1)
• 正好 table 长度就必须是2的幂。（早有预谋）。
  2^n 二进制数的特点：高位1其它全是0。比如1 0000
-1 实现去掉最高位，后面全变成 1。比如1 0000 - 1 = 1111
  例： table 长 16，hash 后 4 位是0101。（前面的 28 位 &0 后肯定都是 0 了，可以忽略）

???????? ???????? ???????? ????0101	= 5  // hash
00000000 00000000 00000000 00001111	= 15 // table.length: 16-1 得 15
--------------------
  0 1 0 1	= 5  // 5 % 16 == 5
1
2
3
4

• 公式 (hash % 2^n) == (hash & (2^n)-1) 推导：
  在二进制的位运算中，一个数 x2 就是左移1位，÷2就是右移1位。
  移出的部分直接丢弃，空出的位置补0。

// 首先已知：9527 % 16 = 7
// 工具方法便于直接 F12 验算
var toBinary = n=>n.toString(2).padStart(32, 0).match(/.{8}/g).join(' ');
00000000 00000000 00100101 00110111 // toBinary(9527); 
// 除以16等于 9527 ÷2, ÷2, ÷2, ÷2 也就是右移 4 位。商 595 就拿到了。
00000000 00000000 00000010 01010011 // toBinary(9527>>4); 
// 但是余数呢？ 经过观察发现，余数正好就是移出右侧边界被丢弃的部分 7。其实，我们直接取后 4 位就行了。
    0000 00000000 00000010 01010011 0111 
// 16 - 1 = 15 正好后 4 位 1 得到一个完美的掩码。
  00000000 00000000 00000000 00001111 // toBinary(16-1)
& 00000000 00000000 00100101 00110111 // toBinary(9527)
—————————————————————————————————————
                                 0111 // 通过 & 前 28 位都被消除，得到了末尾 4 位。也就是余数了。
1
2
3
4
5
6
7
8
9
10
11
12
13

resize 初始化或扩容 table

• resize()

初始化或将数组 table 扩容到原来的 2 倍。
如果为 table 为 null，则按照扩容阈值 threshold 分配初始容量。
另外，因为我们使用的是2的幂展开，所以每个bin中的元素要么必须保持相同的索引，要么在新表中以2的幂偏移量移动。
返回完成初始化或扩容后的 table

1. 准备工作：先声明一堆临时变量，用来缓存哈希表，扩容阈值，新容量、阈值
2. 计算新的【容量、扩容阈值】
   2.1. 扩容：如果 oldCap > 0 表示当前 HashMap 已经初始化过，需要执行的是扩容操作。
   2.2. 否则：如果有【扩容阀值】oldThr，则使用它初始化【容量】
   2.3. 否则：全都用默认值。
   2.4. 如果以上几步完成后，尚未算出新的 threshold，就单独把它算出来。
3. 创建新哈希表，并填充数据
   3.1. 至此用上面算出来的新容积 newCap 创建哈希表。
   3.2. 如果原来这个 HashMap 就是空的，直接返回新哈希表，否则遍历旧哈希表向新数组填充。
   3.2.1. 填充新数组时，将旧数组中的元素置null，以便垃圾回收。
   3.2.2. 如果只有一个结点的情况，会单独处理。
   3.2.3. 如果需要遍历所有结点，会判断是否红黑树，如果是树调用专用的方法处理。
   3.2.4. 向新数组填充的同时就会将符合条件的元素，移动到新扩充区域。

final Node<K,V>[] resize() {
	// ================= 一、准备工作：先声明一堆临时变量 =================
	// 临时变量 oldTab、newTab 缓存 【数组 table】：扩容前的原值/扩容后的新值。
	// 临时变量 oldThr、newThr 缓存 【扩容阀值 threshold】：扩容前的原值/扩容后的新值。
 	// 临时变量 oldCap、newCap 缓存 【数组table的长度】：扩容前的原值/扩容后的新值。
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    
    // ================= 二、计算新的【容量、扩容阈值】=================
    // 1. 扩容：oldCap > 0 表示当前 HashMap 已经初始化过，需要执行的是扩容操作。
    // 2. 否则：如果有【扩容阀值】threshold，则使用它初始化【容量】
    // 3. 否则：全都用默认值。
    if (oldCap > 0) {
    	// 如果当前容量 >= 上限。
    	// 将扩容阈值 threshold 设为 Integer.MAX_VALUE，因为永远不可能达到就再也不会触发扩容了。
    	// 未进行扩容操作，直接将【原数组】返回。 
        if (oldCap >= MAXIMUM_CAPACITY) {	// 01000000 00000000 00000000 00000000 2^30
            threshold = Integer.MAX_VALUE;  // 01111111 11111111 11111111 11111111 2^31-1
            return oldTab;
        }
        // 否则：如果(扩容前原容量x2 < 上限)并且(扩容前原容量 >= 默认的初始容量) 
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY 
        		&& oldCap >= DEFAULT_INITIAL_CAPACITY) // DEFAULT_INITIAL_CAPACITY = 16
        {
        	// 扩容阈值X2，得到新的扩容阈值
            newThr = oldThr << 1; 
        }
    }
    // 初始化：
    // 在初始化前，有调用其他操作，已经算出了扩容阈值。
    else if (oldThr > 0)
        newCap = oldThr; // 初始化容量 = 扩容阈值
    // 初始化：
    // 例如：new无参构造后，没调用过会初始化 threshold 的操作，直接调用 put 就会来到这里
    else {               
        newCap = DEFAULT_INITIAL_CAPACITY;	// 16
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); // 0.75 * 16 = 12
    }
    
    // 如果至此尚未算出新的 threshold，就算一下。（从上面第2个分支来的）
    if (newThr == 0) {
    	// 扩容阀值 = 新容量 * 负载因子
        float ft = (float)newCap * loadFactor;
        // (新容量 < 容量上限) && (扩容阀值 < 容量上限) 返回 ft 否则返回无法触及的 Integer.MAX_VALUE
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr; // 更新扩容阀值 
    
    // ================= 三、创建新数组，并填充数据 =================
    // 按前面算出来的容量，new 一个新 Node 数组。（ HashMap的根容器 ）
    @SuppressWarnings({"rawtypes","unchecked"})
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    // 如果原本 table 就有内容，则需要遍历它将内容填充到新数组中来。
    if (oldTab != null) {
    	  // --- 遍历原数组 --- 
          for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            // 取出索引 j 位置上的结点。（也是这个坑里的链表的头结点）
            if ((e = oldTab[j]) != null) {
                // 设置为 null 方便垃圾回收
                oldTab[j] = null; 
                // 1. 如果当前结点无后，表示已经是最后一个。直接按 hash 算出新的索引并填充到数组中。
                // 2. 否则如果是 TreeNode 结点，说明已经树化。调用调整 TreeNode 专用的方法。
                // 3. 否则（是链表结点）遍历链表，搬运结点到扩容后的新数组来。（部分结点要移到新的索引）
                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 {
                	// --- 遍历链表 ---
                	// 搬运结点到新数组。保持原链表顺序。
                	// 新数组分为高低两部分，低表示原有索引区域，高表示新扩展出来的索引区域。
                	// 当前类源码规范定义数组大小只能是 2^n                 	
                	Node<K,V> loHead = null, loTail = null; // 临时变量：低位的头结点、尾结点。
                    Node<K,V> hiHead = null, hiTail = null; // 临时变量：高位的头结点、尾结点。
                    Node<K,V> next;							// 临时变量：当前结点的下一结点
                    do {
                        next = e.next;
                        // 1. 如果 (e.hash & oldCap) == 0 索引不变，无需移动。
                        // 2. 否则表示结点要移到新扩展的高低区域。
                        if ((e.hash & oldCap) == 0) {
                        	// 如果尾结点为 null，表示链表是空的，先设置头结点。
                        	// 否则追加到末尾。
                        	/// 最后更新尾结点变量。
                            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);
                    // 扫尾工作
                    // 如果尾结点不为 null，将其 next 设置为 null (既然是末尾了，后没肯定是空的)
                    // 然后将链表的头结点，装进数组的当前索引位置。
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    // 向新扩展区域填充时，索引 + 偏移量。其他同上。
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab; // 最终返回初始化完成 or 扩容后的新数组。
}
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

【算法学习】计算结点是否需要移动

(e.hash & oldCap) == 0
假设：

e.hash = 9527
oldCap = 16
newCap = 32
1
2
3

原理：
扩容前取hash的后4位算索引，所以后4位相同的 hash 都蹲同一个坑。
扩容后取hash的后5位算索引，只有后5位都相同的 hash 才蹲同一个坑。
如果有两个hash 分别是 01000、11000 那么在容量为16时只取后4位计算索引，它们的值相同，都蹲一个坑里。
而扩容后，取后5位计算索引，它两就尿不到一壶了。
并且多出来的这一位肯定是 2^n（而且正好等于 oldCap 此例中是16），原索引加上它，可以完美的实现向新增区域偏移。

例子：

// 扩容前计算索引 (9527 & (16-1)) 
00000000 00000000 00100101 00110111 // toBinary(9527); 
00000000 00000000 00000000 00001111 // oldCap 后四位保留 
—————————————————————————————————————————————————————————
                               0111 // 得到索引 7
                               
// 扩容后计算索引 (9527 & (32-1)) 
00000000 00000000 00100101 00110111 // toBinary(9527); 
00000000 00000000 00000000 00011111 // newCap 后五位保留 
—————————————————————————————————————————————————————————
                              10111 // 得到索引 16 + 7 = 23
1
2
3
4
5
6
7
8
9
10
11

1. 可以看出 newCap 扩容1倍，也就是左边多出1位可用于计算。
   1.1. 如果多出的这一位，对应的 hash 是0，那计算出来的索引与扩容前完全一样。我们让此hash原位不会。
   1.2. 如果正好是1则算出来的索引 = oldCap + 7 = 16 + 7 落在了新扩容的区域。
   1.3. 所以只要判断此位上的值，即可得知是否需要移动。
2. 如何判断呢？只要把这个位置上的数 &1 看结果是0还是1就行了。
3. 正好 oldCap 正是此位上为 1 其他位都是 0的数 ，完美工具人。

treeifyBin 树化

将哈希桶中的链表转成红黑树。前提条件 ：MIN_TREEIFY_CAPACITY = 64

哈希表长度 < MIN_TREEIFY_CAPACITY 时，冲突的主要原因归咎于 哈希表 容量太小，扩大点自然能解决。（扩容后hash值多出来的那一位上为1 的元素，就会移到新扩的区域，自然链表的长度就下来了）
但是当数组长度达到 64 后再无脑扩容就不划算了，所以执行树化操作，将链表转为红黑树。

1. 首先判断，如果数组长度还没到64，直接扩容解决。
2. 如果数组长度已经 >= 64 并且按 hash 取到了头结点，则执行树化：
   2.1. 首先通过循环【原链表】创建一个新的【双向链表】：
   2.1.1. 循环的第一轮中，让【双向链表】的【头和尾结点】都指向【当前结点】，
   2.1.2. 后面每次循环中，将【当前结点】追加到【尾结点】后面，然后更新【尾结点】。
   2.2. 将新链表的头结点放进数组的相应索引中。
   2.2.1. 如果头结点非空，在头结点上调用 treeify 执行树化。

在遍历中可以看到有prev，next，说明在树化前，我们已经得到了一个双向链表。
并且转换完成后双向链表的信息并不会受影响，所以我们得到的结果既是一个红黑树也是一个双向链表。

/**
* @param tab	哈希表（HashMap底层的数组容器）
* @param hash	需要树化的结点的 hash 值
*/
final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    // 1. 如果数组为空或长度小于 MIN_TREEIFY_CAPACITY 则直接扩容 
	// 2. 否则按【hash】算出索引，找到目标桶，将其内容从【链表】转成【红黑树】
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize();
    else if ((e = tab[index = (n - 1) & hash]) != null) { // 取出头结点作为当前结点 e
    	// 声明新链表的：头结点、尾结点
        TreeNode<K,V> hd = null, tl = null;
        
        // 遍历结点逐个移到新声明的头结点后（直到整个链表都移完）
        // 1. 循环的第一轮中，让新链表的【头结点】和【尾结点】都指向【当前结点】，
		// 2. 后面每次循环中，将【当前结点】追加到【尾结点】后面，然后更新【尾结点】。
        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);
        
        // 把【头结点】hd 放进 tab[index]。如果 hd 非空，正式开始树化
        if ((tab[index] = hd) != null)
            hd.treeify(tab); // 在头结点上调用树化方法。
    }
}
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

removeNode 移除结点

按给定参数，移除结点。返回被移除的结点，如果没找到返回 null

1. 先检测哈希表非空且桶中第一个结点也非空，才继续，否则直接返回 null
2. 通过对比 hash、key 找目标结点。找到后用临时变量保存。
3. 然后移除结点。也就是把链表断开，再把爷孙相连，
4. 最后一通扫尾工作后，返回被移除的结点。

/**
 * @param hash			key 生成的 hash 值
 * @param key			键
 * @param value 		用于时行匹配的值，只在 matchValue = true 时有用。否则请忽略
 * @param matchValue	如果为 true 则只移除 value 匹配的结点。
 * @param movable		当结构是树时会用到。如果为 true 会将红黑树的根结点移动到最前面（桶中的第一个结点）
 * @return 
 */
final Node<K,V> removeNode(int hash, Object key, Object value, boolean matchValue, boolean movable) {
   	// tab		临时变量缓存哈希表（数组）
   	// p		临时变量缓存结点
   	// n		哈希表（数组）的长度
   	// index	用 hash 算出来的索引
    Node<K,V>[] tab; Node<K,V> p; int n, index;
    // 哈希表不为空且长度 > 0，并且头结点也不为 null 则继续处理，否则返回 null
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (p = tab[index = (n - 1) & hash]) != null) {

	   	// node		临时变量缓存结点（要移除的目标结点）
	   	// e		临时变量缓存结点（遍历链表时用到）
	   	// k		key
	   	// v		value
        Node<K,V> node = null, e; K k; V v;
        
		// ----- 找结点 -----
        // 1. 判断头结点，hash和key都相等就是目标，用临时变量 node 存好。
        // 2. 如果头结点不是目标，且下一结点不为null，则继续查找：
        // 2.1. 如果结点类型是 TreeNode 则调用树专用的查找方法 getTreeNode
        // 2.2. 否则遍历链表逐个对比hash和key都相等就是目标，赋给临时变量 node。
        //      一旦找到直接跳出循环，不浪费时间。
        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);
            }
        }
        // ----- 移除结点 -----
        // 1. 判断条件满足才继续处理移除逻辑。
        // 1.1. 目标结点 node 是否为 null，为null直接结束
        // 1.2. 并且：matchValue == true 时要判断 value 是否与给定值相等
        // 2. 判断结点类型：
        // 2.1. 如果结点类型是 TreeNode 则调用树专用的移除方法 removeTreeNode
        // 2.2. 否则如果：目标结点就是第一个结点，直接将 tab[index] 替换成它的 next
        // 2.3. 否则：p 是目标结点的父结点，断开链表，将 p.next 指向 自己的next。
        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;			// 结构修改计数+1
            --size;				// 大小-1
            afterNodeRemoval(node);	// 移除结点后回调
            return node;		// 返回被移除的结点
        }
    }
    return 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
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

loadFactor 返回负载因子

// 供 HashSets 的 writeObject 方法调用
final float loadFactor() { return loadFactor; }
1
2

capacity 返回容积

1. 如果哈希表非空，返回其长度。
2. 如果 threshold 扩容阈值 > 0，则返回扩容阈值。
3. 否则返回默认的初始容量 16

final int capacity() {
    return (table != null) ? table.length :
        (threshold > 0) ? threshold : DEFAULT_INITIAL_CAPACITY;
}
1
2
3
4

writeObject 序列化

将HashMap实例的状态保存到流中(即序列化它)。

会被序列化的内容：

• 所有：非静态non-static 字段。
• 所有：非瞬态 non-transient 字段。
• 所有：key、value

1. 将所有非静态、非瞬态字段写入库。
2. 容积，作为32位整型写入流。（读的这时候也按这个顺序读就知道它是哪个字段了）
3. size，作为32位整型写入流。（读的这时候也按这个顺序读就知道它是哪个字段了）
4. 遍历当前 hashMap 将所有 key、value 写到输出流。

private void writeObject(java.io.ObjectOutputStream s) throws IOException {
    int buckets = capacity();	// 获取容积
    // 将当前类的非静态non-static 和非瞬态 non-transient 字段写入此流。
    // 此字段只能从正在序列化的类的 writeObject 方法中调用。
    // 如果从其他地方调用该字段，则将抛出 NotActiveException。
    s.defaultWriteObject();		
    s.writeInt(buckets);		// 容积，作为32位整型写入流。
    s.writeInt(size);			// size，作为32位整型写入流。
    internalWriteEntries(s);	// 当前 hashMap的所有 key、value 写到输出流 s
}
1
2
3
4
5
6
7
8
9
10

readObject 反序列化

从流重新构造 HashMap 实例(即，反序列化它)。
从流读入数据前会先重置当前 HashMap。与序列化方法 writeObject 的操作相对应。

1. 先按序列化时的顺序，将流中的数据逐个读出来。
2. 然后重新初始化哈希表。
3. 最后循环从输入流中读取 key 和 value 填入当前 HashMap。

private void readObject(java.io.ObjectInputStream s) throws IOException, ClassNotFoundException {
    // 从此流读取当前类的非静态和非瞬态字段。
    // 此方法只能从正在反序列化的类的 readObject 方法中调用。
    // 如果从其他地方调用该字段，则将抛出 NotActiveException。
    s.defaultReadObject();
    // 重置到初始默认状态。
    reinitialize();
    // 负载因子 <= 0 或 不是浮点数 就抛锅
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new InvalidObjectException("Illegal load factor: " + loadFactor);
        
    s.readInt();                // 读取一个32位整型。这个值是：容积
    int mappings = s.readInt(); // 读取一个32位整型。这个值是：size

	// 如果 size < 0 直接抛锅
	// 否则如果 size > 0
	// 1. 先算：负载因子
	// 2. 再算：容积
	// 3. 按容积创建数组（哈希表）
	// 4. 遍历 i从输入流中逐个读取 key、value 填进 HashMap
    if (mappings < 0)
        throw new InvalidObjectException("Illegal mappings count: " + mappings);
    else if (mappings > 0) { // (if zero, use defaults)
    	// ----- 计算容积 -----
        // 计算负载因子。确保在 0.25 - 4.0 范围内
        float lf = Math.min(Math.max(0.25f, loadFactor), 4.0f);
        // 算出容积 fc = size / loadFactor + 1.0f
        // 如果：fc < 【默认的初始容量 16】 则使用【默认容量】
        // 否则如果： fc >= 【容量最大值】，则使用 【容量最大值】
        // 否则：返回大于 fc 的最小2的幂。
        float fc = (float)mappings / lf + 1.0f;
        int cap = ((fc < DEFAULT_INITIAL_CAPACITY) ? DEFAULT_INITIAL_CAPACITY :
                   (fc >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : tableSizeFor((int)fc));
        
        // ----- 更新扩容阈值 -----
        // 扩容阈值（临时变量） = 容量 * 负载因子
        float ft = (float)cap * lf;
        // 如果 容积cap < 容积最大值，并且 ft < 容积最大值，使用 ft
        // 否则：使用 Integer.MAX_VALUE
        threshold = ((cap < MAXIMUM_CAPACITY && ft < MAXIMUM_CAPACITY) ?
                     (int)ft : Integer.MAX_VALUE);
        
        // 按容量创建数组（哈希表）
        @SuppressWarnings({"rawtypes","unchecked"}) // 压制警告
        Node<K,V>[] tab = (Node<K,V>[])new Node[cap];
        table = tab;

        // 循环从输入流中读取 key 和 value 填入当前 HashMap
        for (int i = 0; i < mappings; i++) {
            @SuppressWarnings("unchecked") // 压制警告
                K key = (K) s.readObject();
            @SuppressWarnings("unchecked") // 压制警告
                V value = (V) s.readObject();
            putVal(hash(key), key, value, false, false);
        }
    }
}
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

LinkedHashMap support

以下受包保护的方法被设计成可以被LinkedHashMap覆盖，但不能被任何其他子类覆盖。几乎所有其他内部方法都是包保护的，但都声明为final，因此可以由LinkedHashMap、视图类和HashSet使用。

newNode 创建一个【链表结点】（非树结点）

    /**
     * @param hash	结点的 hash 值
     * @param key	结点的 key  值
     * @param value	结点的 value 值
     * @param next	指向的下一个结点对象
     */
    Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) {
        return new Node<>(hash, key, value, next);
    }
1
2
3
4
5
6
7
8
9

replacementNode 将【树结点】转换为【链表结点】

    /**
     * @param p		指向的下上个结点对象
     * @param next	指向的下一个结点对象
     */
    Node<K,V> replacementNode(Node<K,V> p, Node<K,V> next) {
        return new Node<>(p.hash, p.key, p.value, next);
    }
1
2
3
4
5
6
7

newTreeNode 创建一个树结点

    /**
     * @param hash	结点的 hash 值
     * @param key	结点的 key  值
     * @param value	结点的 value 值
     * @param next	指向的下一个结点对象
     */
    TreeNode<K,V> newTreeNode(int hash, K key, V value, Node<K,V> next) {
        return new TreeNode<>(hash, key, value, next);
    }
1
2
3
4
5
6
7
8
9

replacementTreeNode 将【链表结点】转换为【树结点】

    /**
     * @param p		指向的下上个结点对象
     * @param next	指向的下一个结点对象
     */
    TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) {
        return new TreeNode<>(p.hash, p.key, p.value, next);
    }
1
2
3
4
5
6
7

reinitialize 重置至初始默认状态

重置至初始默认状态. 供 clone 和 readObject 两个方法调用。

    void reinitialize() {
        table = null;
        entrySet = null;
        keySet = null;
        values = null;
        modCount = 0;
        threshold = 0;
        size = 0;
    }
1
2
3
4
5
6
7
8
9

afterNodeXXX 回调三人组

• afterNodeAccess 回调函数，允许 LinkedHashMap 在结点被【访问】后执行后置处理。
• afterNodeInsertion 回调函数，允许 LinkedHashMap 在结点被【插入】后执行后置处理。
• afterNodeRemoval 回调函数，允许 LinkedHashMap 在结点被【移除】后执行后置处理。

    void afterNodeAccess(Node<K,V> p) { }
    void afterNodeInsertion(boolean evict) { }
    void afterNodeRemoval(Node<K,V> p) { }
1
2
3

internalWriteEntries 写到输出流

仅供 writeObject 调用，以确保兼容的排序。

1. 遍历 HashMap 写到输出流

    void internalWriteEntries(java.io.ObjectOutputStream s) throws IOException {
        Node<K,V>[] tab;
        if (size > 0 && (tab = table) != null) {
        	// 遍历数组
            for (int i = 0; i < tab.length; ++i) {
            	// 遍历链表（此处红黑树的结点同时也是一个双向链表结点。treeifyBin干的）
                for (Node<K,V> e = tab[i]; e != null; e = e.next) {
                    s.writeObject(e.key);
                    s.writeObject(e.value);
                }
            }
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13

成员方法列表

增

删

改

查

总结

最佳实践

1. 初始化时制定容量，推荐值：(预期容量 / 0.75) + 1

参考资料

Class HashMap

笑虾：Java 学习笔记 HashMap 中的 hash 方法为何要进行异或和位移？
笑虾：Java 集合学习笔记：HashMap - 静态内部类 Node、TreeNode

CSDN-程序员的时光-详细理解HashMap数据结构，太齐全了！