回顾：Map 集合

• 常用方法
• 存储机制
  • 结构
  • 确定存储位置
  • 扩容机制
  • 解决哈希冲突
• JDK 8 的改动

1、常用方法

HashMap 继承自 Map 接口

• put()：添加元素，key 重复则覆盖原值。
• keySet()：返回一个包含所有 key 值的 Set 集合。
• entrySet()：返回一个包含所有记录的 Set 集合。

2、存储机制（❗）

2.1、特点

• 存储形式：K-V 键值对，Key 具有唯一性。
  • JDK 7：称为 Entry（记录），头插入
  • JDK 8：称为 Node（结点），尾插入
• 存储结构：数组 + 链表 （+ 红黑树）
  1. 先根据 Key 的 hashCode() 计算对应的存放位置。
  2. 若产生哈希冲突，在当前位置形成链表。
  3. 根据 equals() 判断元素是否相等，若相等则覆盖原值。
• 无序性：Key 是哈希到数组中的，且可能因为扩容而改变存储位置。
• 线程不安全：
  1. 在多线程下使用 Collections.synchronizedMap(Map)
  2. 使用 ConcurrentHashMap

2.2、存储结构

2.2.1、数据结构

解决哈希冲突：拉链法

• JDK 7：数组 + 链表（拉链法）
• JDK 8：数组 + 链表 + 红黑树（拉链法 + 红黑树）
  • 若哈希冲突严重，链表长度越长，遍历链表的时间复杂度 O(n)
  • 树化条件：链表长度达到树化阈值（默认 8），链表容量达到最小树化容量（默认 64）
  • 访问红黑树结点的时间复杂度 O(log_n)

2.2.2、重要参数

• Node<K,V>[] table：存放元素的数组。

• entrySet：包含所有元素的 Set 集合。

• size：哈希表中的元素个数。

• threshold：扩容阈值。

• loadFactor：加载因子。

  	含义	默认值
  桶（bucket）	数组中的每个地址位置
  初始容量	桶的初始数量	DEFAULT_INITIAL_CAPACITY = 1 << 4（16）
  最大容量		MAXIMUM_CAPACITY = 1 << 30
  加载因子	用于计算扩容阈值	DEFAULT_LOAD_FACTOR = 0.75f
  扩容阈值	元素个数达到阈值时扩容	扩容阈值 = 哈希表容量 * 加载因子
  树化阈值	桶的结点个数达到阈值时树化	TREEIFY_THRESHOLD = 8
  最小树化容量	树化的另一个前提条件	MIN_TREEFY_CAPACITY = 64
  非树化阈值	桶的结点个数达到阈值时退化为链表	UNTREEIFY_THRESHOLD = 6

2.3、API

2.3.1、结点类 Node<K,V>

JDK 7：Entry。

JDK 8：引入红黑树，改为 Node。

• Node 即 Bucket，表示一张单链表。

• 属性：元素哈希值、键、值、后继指针。

  static class Node<K,V> implements Map.Entry<K,V> {
      final int hash;
      final K key;
      V value;
      Node<K,V> next;
      
      // 构造方法、getter、setValue()、hashCode()、equals()
  }
  

2.3.2、构造方法

1. 空参：默认加载因子。

2. 初始容量：指定初始容量，默认加载因子

3. 初始容量、加载因子：指定初始容量和加载因子

4. Map：深拷贝

   public HashMap() {
       this.loadFactor = DEFAULT_LOAD_FACTOR;
   }
   
   public HashMap(int initialCapacity) {
       this(initialCapacity, DEFAULT_LOAD_FACTOR);
   }
   
   public HashMap(int initialCapacity, float loadFactor) {
       if (initialCapacity < 0)
           throw new IllegalArgumentException("Illegal initial capacity: " +
                                              initialCapacity);
       if (initialCapacity > MAXIMUM_CAPACITY)
           initialCapacity = MAXIMUM_CAPACITY;
       if (loadFactor <= 0 || Float.isNaN(loadFactor))
           throw new IllegalArgumentException("Illegal load factor: " +
                                              loadFactor);
       this.loadFactor = loadFactor;
       this.threshold = tableSizeFor(initialCapacity);
   }
   
   public HashMap(Map<? extends K, ? extends V> m) {
       this.loadFactor = DEFAULT_LOAD_FACTOR;
       putMapEntries(m, false);
   }
   

2.3.3、存储位置

hash()

Key 的哈希值通常不满足哈希表的长度要求。

• JDK7：扰动函数，即 4 次位运算 + 5 次异或运算。

  static final int hash(Object k) {
     int h = 0;
     h ^= k.hashCode(); 
     h ^= (h >>> 20) ^ (h >>> 12);
     return h ^ (h >>> 7) ^ (h >>> 4);
  }
  

• JDK8：优化的扰动函数，即 1 次位运算 + 1 次异或运算（减小开销）

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

indexfor()

JDK7 单独作为方法，JDK8 合并到 put() 中。

高效率：二进制与运算，取代十进制的取模运算。

• HashMap 底层数组长度总是 2^n，转为二进制后低位有多个 0。

• 将某个数与 2 ^ n 取模，相当于 2 ^ n - 1。

  static int indexFor(int h, int length) {
       return h & (length-1);
  }
  

2.4、添加元素（❗）

添加元素

注：调用 HashMap 的无参构造时尚未初始化，在首次添加元素时才完成初始化操作。

方法参数

• hash()：计算 key 的哈希值。

• key、value

• false：对应 onlyIfAbsent 参数，true 表示位桶中没有元素才添加。

• true：对应 evict 参数。

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

2.4.1、putVal()

源码中将很多代码合为一句，可读性差，可以拆分为多行代码来理解。

• tab：当前元素数组。

• p：下标为 i 所对应的数组元素。

• n：tab 长度。

• i：由哈希值计算出的存储位置（数组下标）。

  

① 判空：table

第一个 if：判断 table 是否为空

是：调用 resize() 进行扩容

② 添加元素（❗）

第二个 if：由哈希值计算的存储位置 i，判断 i 位桶的元素 p 是否为空。

是：将元素存储在当前位桶 i

否（else）：在当前位桶形成链表（拉链法）

• if：判断待添加元素与当前位置元素的哈希值和 key 是否相等，是则将当前位置元素 p 赋给临时变量 e

  

• else-if：判断 p 是否为 TreeNode，是则调用另一个方法（即判断当前是否已树化）

• else：遍历当前位桶的链表
  （临时变量 e 代表链表中当前位置元素，k 是 e 的 Key）

  • 若待添加元素与 e 哈希值和 key 相等，则跳出循环，跳出 else 语句。
  • 若遍历直到最后一个结点，未出现重复元素，将元素尾插入；
    • 若达到桶中元素个数达到树化阈值 - 1，则树化。
    • 假设 binCount == 5 时访问到最后一个结点，此时桶中有 6 个数据，添加新元素后有 7 个元素。

• if：待添加元素的 Key 已在 HashMap 中存在，覆盖旧值，并将旧值返回。

③ 扩容

第三个 if

1. size 自增。
2. 判断是否达到扩容阈值，是则调用 resize() 扩容。

2.4.2、resize()

初始化容量或扩容（加倍），并将表返回

• oldTab：原表，即当前的表。

• oldCap：原容量，即当前容量。

• newCap、newThr：新容量和新扩容阈值。

• newTab：新表。

  

① 初始化/扩容

第一个 if：判断 oldCap 是否大于 0

负责扩容、初始化。

是：说明数组已初始化过，进行扩容。

• if：oldCap 超过最大容量（1 << 30），不成立
• else if：扩容，新容量为原来的 2 倍
  • 判断是否小于最大容量：必成立
  • 判断 oldCap 是否不小于默认初始化容量：若已初始化过，必成立

否：数组未初始化，进行初始化。

• else if：判断扩容容量是否已赋值，是则作为新容量
• else：新容量 == 默认初始容量，新阈值 == 默认初始阈值
  （无参构造，首次 put() 会到这里）

② 更新扩容阈值

第二个 if：判断新扩容阈值是否已赋值

新扩容阈值 == 新容量 * 加载因子

③ 扩容：复制元素

第三个 if：判断旧表是否为空

null 说明是在初始化，非空说明是在扩容

（遍历数组，临时变量 e 代表当前访问的元素。）

判断当前数组元素是否为空，null 则无需操作，不为 null 进入以下操作。

• if：e 的后继为空，说明当前位置未形成链表，直接将其添加到新表的相应位置。
• else-if：e 是树节点，说明当前位桶的链表已树化，调用 split() 进行操作。
• else：当前位桶已形成链表，且未树化。逐个复制到新表中。

最后，返回新表。