hashmap java 实现-杰瑞科技汇

HashMap 简介
核心数据结构：数组 + 链表 / 红黑树
核心工作机制
- put() 方法：如何存入一个键值对？
- get() 方法：如何根据 Key 获取 Value？
- resize() 方法：扩容机制
重要属性
源码分析 (基于 JDK 8)
性能分析
与 Hashtable 和 ConcurrentHashMap 的区别

`HashMap` 简介

HashMap 是 Java 集合框架中非常重要的一部分，它实现了 Map 接口。Map 接口存储的是 key-value 键值对，并且不允许键重复。

HashMap 的主要特点：

基于哈希表：它通过哈希函数来计算键的存储位置，使得其增、删、改、查操作的平均时间复杂度接近 O(1)。
非线程安全：在多线程环境下，对 HashMap 的并发操作可能会导致数据不一致或死循环等问题，如果需要线程安全的 Map，应使用 Hashtable 或 ConcurrentHashMap。
允许 null 键和 null 值：HashMap 是 Map 接口中唯一允许 key 或 value 为 null 的实现。
不保证顺序：HashMap 的迭代顺序不固定，也不与插入顺序相同，如果需要保持插入顺序，应使用 LinkedHashMap。

核心数据结构：数组 + 链表 / 红黑树

HashMap 的底层实现是一个“数组”，数组的每个元素被称为一个“桶”（Bucket），每个桶可能存储多个键值对，这是通过“链表”或“红黑树”来实现的。

在 JDK 7 及之前，HashMap 的结构是纯粹的“数组 + 链表”，这种结构在哈希冲突严重时（即一个桶里有很多元素），链表会变得很长，导致 get() 等操作的时间复杂度退化为 O(n)。

为了解决这个问题,JDK 8 对 HashMap 进行了优化，引入了“红黑树”。

现在的结构是：

Node<K,V>[] table：一个 Node 类型的数组，这就是哈希表的主干。
Node<K,V>：HashMap 的内部类，代表链表中的一个节点。
TreeNode<K,V>：HashMap 的内部类，Node 的子类，代表红黑树的一个节点。

结构图示：

+-------------------+   +-------------------+   +-------------------+
|    Node[0]        |   |    Node[1]        |   |    Node[2]        |  <-- 数组
|   (null)          |   |   head -> (key1, val1) |   |   head -> (key3, val3) |
+-------------------+   |         |         |   |         |         |
                       |      next -> (key2, val2) |      next -> (key4, val4) |
                       +-------------------+   +-------------------+
                               |                         |
                               | (链表长度 > 8)          | (链表长度 > 8)
                               |                         |
                               V                         V
                         +-------------------+   +-------------------+
                         |   TreeNode       |   |   TreeNode       |  <-- 红黑树
                         |   (root of tree) |   |   (root of tree) |
                         +-------------------+   +-------------------+

转换规则 (JDK 8):

当链表长度超过 8 (TREEIFY_THRESHOLD)，并且数组的长度大于等于 64 时，链表会转换为红黑树。
当红黑树的节点数减少到 6 (UNTREEIFY_THRESHOLD) 时，红黑树会退化为链表。

为什么是 8 和 6？

8 (Treeify Threshold)：这是一个经验值，在泊松分布下，哈希冲突的概率极低，链表长度达到 8 的情况非常罕见，选择 8 是为了平衡链表和红黑树的转换开销，链表短时，遍历的开销很小；链表过长时，转换为红黑树能显著提升查询效率。
6 (Untreeify Threshold)：选择比 8 小的值，可以避免在 resize() 过程中频繁地在链表和红黑树之间来回转换（即“乒乓效应”），提高性能。

核心工作机制

1 `put()` 方法：如何存入一个键值对？

put(key, value) 的流程可以分解为以下几步：

计算哈希值：
- 首先调用 key.hashCode() 方法获取 key 的原始哈希码（这是一个 32 位的整数）。
- 然后调用 HashMap 内部的 hash() 方法进行二次哈希处理，这个方法会进行位运算，目的是为了减少哈希冲突。
```
static final int hash(Object key) {
    int h;
    // (h = key.hashCode()) ^ (h >>> 16) 是核心操作
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
```
  h >>> 16 是将高 16 位移动到低 16 位，然后与原哈希码进行异或（^），这样做的好处是，当数组长度较小时（比如只有 16 个桶），只取哈希码的低 4 位来定位桶，冲突概率很高，通过混合高 16 位，可以让哈希值的分布更均匀。
定位桶的位置：
- 使用 (n - 1) & hash 来计算元素在数组中的索引 i。n 是数组的长度。
- 为什么是 n - 1？ 因为 HashMap 要求数组的长度 n 必须是 2 的幂次方，这样 n - 1 的二进制形式就是全 1（length=16, n-1=15 -> ..1111），与 hash 进行与运算，就等价于取 hash 的低 log₂(n) 位作为索引，这比取模运算（）效率更高。
处理桶中的元素：
- 桶为空：table[i] 为 null，直接创建一个新的 Node 对象，放入该桶中。
- 桶不为空（发生哈希冲突）：
  - 链表情况：遍历链表，比较桶中每个节点的 key 与待插入的 key 的 hash 值和 equals() 结果。
    - 如果找到一个节点的 key 与待插入的 key 相等（hash 相同且 equals 为 true），则用新的 value 覆盖旧的 value，并返回旧的 value。
    - 如果遍历完整个链表都没有找到,就在链表的末尾添加一个新的 Node。
  - 红黑树情况：调用 putTreeVal() 方法，在红黑树中查找 key，如果找到则覆盖，否则在树中插入一个新的节点，并保持红黑树的平衡。
检查是否需要转换结构：
- 在添加新节点后,检查当前桶中链表的长度，如果长度超过 8，并且数组总长度大于等于 64，则调用 treeifyBin() 方法将链表转换为红黑树。
检查是否需要扩容：
- 每次添加元素后,都会检查 size 是否超过了 threshold（扩容阈值）。threshold = loadFactor * capacity。
- size > threshold，则触发 resize() 方法进行扩容。

2 `get()` 方法：如何根据 Key 获取 Value？

get(key) 的流程与 put() 类似：

计算哈希值：和 put() 一样，先计算 key 的 hash 值。
定位桶的位置：使用 (n - 1) & hash 找到对应的桶 table[i]。
在桶中查找元素：
- 桶为空：直接返回 null。
- 桶不为空：
  - 链表情况：遍历链表，逐个比较节点的 key 的 hash 值和 equals() 结果，如果找到，返回对应的 value；如果没找到，返回 null。
  - 红黑树情况：调用 getTreeNode() 方法在红黑树中查找节点，找到则返回 value，否则返回 null。

3 `resize()` 方法：扩容机制

当 HashMap 中的元素数量 size 超过 threshold 时，就需要进行扩容。

扩容的步骤：

创建新数组：创建一个新的数组，其容量是旧数组的 2 倍。
重新计算索引（元素迁移）：遍历旧数组中的每一个桶，将桶中的每一个元素（无论是链表还是红黑树）重新计算在新数组中的位置，并迁移过去。
索引计算优化：这是 JDK 8 的一个巨大优化，因为新数组的长度是旧数组的 2 倍，newCapacity - 1 的二进制表示只是在旧 capacity - 1 的基础上前面多了一个 1。
- 旧 capacity=16 (10000), capacity-1=15 (01111)，新 capacity=32 (100000), newCapacity-1=31 (011111)。
- 重新计算索引 (newCap - 1) & hash，等价于 (oldCap - 1 & hash) | (oldCap & hash)。
- 这意味着,一个元素要么还在原来的位置 i，要么就在 i + oldCap 的位置。
- 判断条件：if ((e.hash & oldCap) == 0)，则留在原位；否则，移动到 i + oldCap。
- 这个优化避免了重新计算每个元素的哈希值,只需要一次位运算即可确定新位置，极大地提升了扩容效率。

重要属性

// 默认初始容量，必须是2的幂次方
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
// 最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;
// 默认加载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 当桶中链表长度达到此值时，转换为红黑树
static final int TREEIFY_THRESHOLD = 8;
// 当桶中红黑树节点减少到此时，转换为链表
static final int UNTREEIFY_THRESHOLD = 6;
// 当桶中元素数量达到此值，并且总容量大于等于64时，才进行树化，否则优先扩容
static final int MIN_TREEIFY_CAPACITY = 64;
// 存储元素的数组， transient 表示序列化时忽略此字段
transient Node<K,V>[] table;
// Map中存储的键值对数量
transient int size;
// 扩容阈值，当 size > threshold 时进行扩容
int threshold;
// 加载因子
final float loadFactor;

源码分析 (基于 JDK 8)

这里我们只看最核心的 putVal() 方法（put() 方法会调用它）：

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    // 1. table 为空或长度为 0，则进行初始化（resize）
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // 2. 计算索引 (n - 1) & hash，如果该位置为空，直接创建新节点放入
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        // 3. 如果桶的第一个节点的 hash 和 key 都相等，则找到该节点
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        // 4. 如果是红黑树结构，则调用树的方法插入
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        // 5. 如果是链表结构
        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;
                }
                // 如果在链表中找到了 key 相同的节点，则退出循环
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        // 6. e 不为 null，说明找到了 key 相同的节点，进行覆盖操作
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e); // 可用于 LinkedHashMap
            return oldValue;
        }
    }
    // 7. size 超过阈值，进行扩容
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict); // 可用于 LinkedHashMap
    return null;
}

性能分析

操作	平均时间复杂度	最坏情况时间复杂度	说明
`put(key, value)`	O(1)	O(n)	哈希冲突严重，且所有元素都在同一个桶中（如所有 `key` 的 `hash` 值都相同）。
`get(key)`	O(1)	O(n)	同上。
`remove(key)`	O(1)	O(n)	同上。
`containsKey(key)`	O(1)	O(n)	同上。

影响性能的关键因素：

哈希函数：一个好的哈希函数能让 key 的哈希值分布均匀，减少哈希冲突。
加载因子：
- 高加载因子（如 0.75）：数组可以更满，空间利用率高，但哈希冲突的概率增加，查询效率降低。
- 低加载因子（如 0.5）：哈希冲突概率低，查询效率高，但空间浪费严重。
- HashMap 默认的 75 是在时间和空间成本之间的一个良好折衷。
初始容量：如果预估了大概要存储多少数据，设置一个合适的初始容量可以避免在后续操作中频繁地 resize()，因为 resize() 是一个比较耗时的操作。

容量和负载因子的关系： threshold = capacity * loadFactor

与 `Hashtable` 和 `ConcurrentHashMap` 的区别

特性	`HashMap`	`Hashtable`	`ConcurrentHashMap`
线程安全	否	是	是
锁机制	无锁	整个表加一把锁（对象锁）	分段锁 / CAS + synchronized (JDK 8)
性能	高（单线程）	低（多线程下，锁竞争严重）	高（多线程下，锁粒度细）
Null 键/值	允许 1 个 null 键，多个 null 值	不允许	不允许
继承/实现	`AbstractMap`	`Dictionary` (已过时)	`AbstractMap`
迭代器	快速失败	快速失败	弱一致性

快速失败：如果在迭代过程中，有其他线程修改了 Map 的结构（不是通过迭代器的 remove() 方法），会立即抛出 ConcurrentModificationException。
弱一致性：迭代器不一定能反映出最新的修改，但它不会抛出异常，可以安全地遍历。

HashMap 是 Java 中使用最广泛的 Map 实现之一，其强大的性能得益于其精巧的内部设计：

核心结构：基于 数组 + 链表/红黑树，结合了数组的快速定位和链表/红黑树的冲突处理能力。
高效操作：通过位运算 (n-1) & hash 快速定位桶，使得 get 和 put 操作的平均时间复杂度为 O(1)。
冲突优化：JDK 8 引入的红黑树解决了哈希冲突严重时性能退化为 O(n) 的问题。
扩容优化：JDK 8 的 resize() 方法通过巧妙的位运算，极大地提升了扩容时的元素迁移效率。

理解 HashMap 的工作原理，不仅能帮助我们在日常开发中更高效地使用它，也能让我们在面试中脱颖而出，并写出更高质量的代码。

hashmap java 实现

目录

`HashMap` 简介

核心数据结构：数组 + 链表 / 红黑树

核心工作机制

1 `put()` 方法：如何存入一个键值对？

2 `get()` 方法：如何根据 Key 获取 Value？

3 `resize()` 方法：扩容机制

重要属性

源码分析 (基于 JDK 8)

性能分析

与 `Hashtable` 和 `ConcurrentHashMap` 的区别

99ANYc3cd6

add binary python

Centos系统安装教程步骤详解？

Java字符串用法有哪些核心要点？

foreach 数组 java

java调用sqlserver

Java Socket编程实例具体怎么实现？

零基础学会计，视频教程怎么学才有效？

Java如何高效获取Map的value值？

Python Matplotlib如何执行绘图？

Python中import机制底层是如何实现的？

Java int如何转为二进制比特？

文泰雕刻2002初学教程

Oracle 11g如何与Java高效集成？

java date获取当前时间

Python如何高效实现数据结构与算法？

游戏键盘6.1汉化版怎么用？

hashmap java 实现

目录

HashMap 简介

核心数据结构：数组 + 链表 / 红黑树

核心工作机制

1 put() 方法：如何存入一个键值对？

2 get() 方法：如何根据 Key 获取 Value？

3 resize() 方法：扩容机制

重要属性

源码分析 (基于 JDK 8)

性能分析

与 Hashtable 和 ConcurrentHashMap 的区别

相关推荐

Java Socket编程实例具体怎么实现？

`HashMap` 简介

1 `put()` 方法：如何存入一个键值对？

2 `get()` 方法：如何根据 Key 获取 Value？

3 `resize()` 方法：扩容机制

与 `Hashtable` 和 `ConcurrentHashMap` 的区别