笔记簿 - ᴄᴏᴅɪɴɢ ɪs ᴀʀᴛ

HashMap - 核心方法的实现细节

HashMap 是 Java 中基于哈希表实现的键值对存储结构，其核心方法 `put()`、`get()` 和 `resize()` 的实现细节如下：

---

### **一、`put()` 方法的实现**
`put()` 方法用于插入键值对，其核心步骤如下：

#### 1. **计算哈希值**
   - 对键的 `hashCode()` 进行扰动，减少哈希冲突：
     ```java
     static final int hash(Object key) {
         int h;
         return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
     }
     ```
   - **目的**：将高 16 位与低 16 位异或，使哈希分布更均匀。

#### 2. **定位桶（Bucket）**
   - 通过哈希值与数组长度取模，确定键值对的位置：
     ```java
     index = (n - 1) & hash; // n 是数组长度（2 的幂）
     ```

#### 3. **处理哈希冲突**
   - **情况 1：桶为空**  
     直接创建新节点 `Node` 并插入。
   - **情况 2：桶为链表**  
     遍历链表：
     - 若找到相同键，更新值；
     - 若未找到，在链表尾部插入新节点；
     - 若链表长度 ≥ 8，且数组长度 ≥ 64，链表转为红黑树。
   - **情况 3：桶为红黑树**  
     调用 `TreeNode.putTreeVal()` 插入节点。

#### 4. **触发扩容**
   - 若元素总数超过 `容量 × 负载因子`（默认 0.75），调用 `resize()` 扩容。

---

### **二、`get()` 方法的实现**
`get()` 方法用于根据键查找值，核心步骤如下：

#### 1. **计算哈希值**
   - 与 `put()` 相同的方式计算哈希值。

#### 2. **定位桶**
   - 使用 `(n - 1) & hash` 找到桶的位置。

#### 3. **遍历链表或树**
   - **链表**：遍历链表，通过 `equals()` 比较键是否相等。
   - **红黑树**：调用 `TreeNode.getTreeNode()` 查找节点。

#### 4. **返回结果**
   - 找到匹配键则返回值，否则返回 `null`。

---

### **三、`resize()` 方法的实现**
`resize()` 用于扩容哈希表，核心步骤如下：

#### 1. **计算新容量和阈值**
   - 新容量为旧容量的 2 倍（保证始终为 2 的幂）。
   - 新阈值为新容量 × 负载因子。

#### 2. **创建新数组**
   ```java
   Node<K,V>[] newTab = (Node<K,V>[])new Node[newCapacity];
   ```

#### 3. **重新分配元素**
   遍历旧数组中的每个桶：
   - **单个节点**：直接重新计算索引（`newIndex = hash & (newCap - 1)`）。
   - **链表**：将链表拆分为高位链和低位链：**高位运算拆分链表**：在 `resize()` 中避免重新计算哈希值，提升效率。
     - 低位链：`newIndex = oldIndex`；
     - 高位链：`newIndex = oldIndex + oldCap`。
     ```java
     // 通过 (e.hash & oldCap) 判断高位是否为 1
     if ((e.hash & oldCap) == 0) {
         // 低位链
     } else {
         // 高位链
     }
     ```
   - **红黑树**：调用 `TreeNode.split()` 拆分树，若拆分后节点数 ≤ 6，转回链表。

#### 4. **更新哈希表**
   - 将新数组赋值给 HashMap 的 `table` 属性。

---

### **四、关键细节总结**
| **操作**   | **核心逻辑**                                                                 |
|------------|-----------------------------------------------------------------------------|
| `put()`    | 哈希计算 → 定位桶 → 处理冲突（链表/树） → 触发扩容。                             |
| `get()`    | 哈希计算 → 定位桶 → 遍历链表/树 → 返回结果。                                     |
| `resize()` | 创建新数组 → 拆分链表/树 → 重新分配元素 → 更新容量和阈值。                         |

---

### **五、示例代码片段**
#### 1. **`put()` 简化逻辑**
```java
public V put(K key, V value) {
    int hash = hash(key);
    int index = (n - 1) & hash;
    Node<K,V> node = table[index];
    
    if (node == null) {
        table[index] = newNode(hash, key, value, null);
    } else {
        // 遍历链表或树插入
    }
    
    if (++size > threshold) resize();
    return null;
}
```

#### 2. **`resize()` 链表拆分逻辑**
```java
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; // j = oldIndex
}
if (hiTail != null) {
    hiTail.next = null;
    newTab[j + oldCap] = hiHead; // j + oldCap = newIndex
}
```

---

### **六、性能优化点**
1. **哈希扰动**：减少哈希冲突，提升分布均匀性。
2. **红黑树优化**：链表长度 ≥ 8 时转为树，避免最坏情况 O(n) 的查询。
3. **高位运算拆分链表**：在 `resize()` 中避免重新计算哈希值，提升效率。

通过理解这些核心实现，可以更好地掌握 HashMap 的高效设计及其适用场景。