企业官网建设流程全解析

刚开始接触数据结构与算法的时候，哈希表（Hash Table）对我来说就是一个“能在 O(1) 时间内完成查找”的神奇容器。那时候只会用 HashMap，put 进去 get 出来，根本不知道它底层到底怎么做到这么快，也不知道为什么有时候重写 equals 就必须重写 hashCode。直到后来去看源码、手写简易版本、再被线上问题毒打几次之后，才慢慢把这块彻底吃透。这篇博文就以 Java 为背景，把哈希表这个东西从头到尾拆开揉碎讲清楚，既是给自己做一个沉淀，也希望能帮正在啃算法和集合源码的同学少走一点弯路。

这篇文章适合这几类人看：准备 Java 面试、正在刷算法题、或者工作中想排查 HashMap 相关的线上问题。内容不会只停留在“HashMap 是数组加链表”这种表面结论，而是会讲清楚哈希表为什么设计成这样、JDK 里到底是怎么实现的、哈希冲突怎么处理、容量和负载因子该怎么选、以及手写一个极简哈希表的完整过程。看完之后你不仅能应付面试八股文，还能在真正写代码的时候明白自己在用什么、为什么这么用。

1. 哈希表的核心思路与设计动机

1.1 为什么需要哈希表：从数组和链表说起

在讲哈希表之前，先回想一下我们最基础的两个数据结构：数组和链表。

数组的特点是内存连续，通过下标访问元素的时间复杂度为 O(1)，但缺点也很明显：查找一个不按下标走的元素时，最坏需要遍历整个数组，时间复杂度 O(n)。而且数组的插入和删除，尤其是中间位置的操作，需要移动大量元素，成本很高。

链表解决了插入删除的问题，因为只需要修改指针指向，时间复杂度为 O(1)。但链表查找某个值时也必须从头遍历，同样逃不过 O(n) 的命运。

那有没有一种结构，既能享受数组的随机访问速度，又能灵活处理动态数据？哈希表就是为这个诉求而生的。它通过一个“哈希函数”把元素的键（Key）映射成数组下标，这样一来，插入和查找都能直接定位到目标位置，理想情况下时间复杂度就是 O(1)。

你可以把哈希函数理解成一个“计算器”：输入一个键，输出一个整数，这个整数再经过处理就变成数组下标。整个过程就像你去图书馆找书，不需要一本一本翻，而是根据索书号直接定位到对应的书架层。

1.2 哈希表的基本结构：数组加哈希函数

一个标准的哈希表由两个核心部分组成：

• 一块连续的内存空间（通常就是数组），用来存储数据
• 一个哈希函数，用来把键映射为数组下标

插入元素时，先计算 key 的哈希值，再通过取模等方式转换成数组下标，然后把 value 存入数组的该位置。查询元素时也走同样的流程：计算哈希值、定位下标、取出数据。

这里最关键的设计点是哈希函数的质量。如果哈希函数设计得不好，不同 key 算出来的下标很容易相同，这就会导致“哈希冲突”。哈希冲突一多，查找速度就会从 O(1) 退化到 O(n)，哈希表的性能优势就荡然无存了。

用生活化的例子来类比：哈希函数就好比把一堆快递分到不同货架上的规则。规则越合理，每个货架上的快递越少，你找快递越快。规则不合理，所有快递都堆在同一个货架上，找起来就和在一堆杂物里翻东西没区别。

2. Java 中 HashMap 的底层实现解析

2.1 JDK 1.8 之后的数组加链表加红黑树结构

说到 Java 里的哈希表，绝大多数人第一个想到的就是 HashMap。JDK 1.8 之后，HashMap 的底层结构变成了“数组 + 链表 + 红黑树”的复合结构。

数组是主体，用来存储数据。每个数组位置称为一个“桶”（Bucket）。当多个元素的哈希值映射到同一个桶时，它们就以链表的形式串联起来。但当链表长度超过阈值（默认是 8）时，链表会转换成红黑树，目的是把最坏情况下的查找时间复杂度从 O(n) 降到 O(log n)。

这个设计解决了一个很实际的问题：如果哈希函数的质量不够好，或者恶意攻击者故意构造大量哈希值相同的 key（典型的哈希碰撞攻击），链表会变得很长，HashMap 的查询性能会急剧下降。引入红黑树之后，即使最坏情况发生了，查询性能依然保持在可接受的范围。

2.2 put 操作完整流程

HashMap 的 put 操作是整个结构的核心入口，流程如下：

1. 对 key 计算哈希值，这里 JDK 不是直接使用 key.hashCode() 的原始值，而是做了一次扰动处理：h = key.hashCode() ^ (h >>> 16)。高位和低位做异或，目的是让高位的信息也参与到后续的下标计算中，减少冲突概率。
2. 根据哈希值计算数组下标：(n - 1) & hash，其中 n 是数组长度。因为 n 是 2 的幂次方，所以n - 1的二进制全是低位 1，这个位运算等价于取模运算，但效率更高。
3. 如果数组还没有初始化（首次 put），会先触发 resize 初始化数组。
4. 如果目标位置为空，直接 new 一个 Node 放进去。
5. 如果目标位置不为空，说明有冲突，分两种情况：
   • 如果当前桶是普通链表节点，就遍历链表。如果找到相同的 key（先比较 hash 再比较 equals），就替换旧值并返回旧值。如果没找到，就在链表尾部插入新节点。插完之后检查链表长度，如果超过阈值 8，调用 treeifyBin 尝试转换成红黑树。
   • 如果当前桶已经是红黑树节点，就按照红黑树的插入逻辑处理。
6. 插入完成后，size加 1。如果size超过阈值threshold（容量乘以负载因子），执行扩容。

2.3 get 操作完整流程

get 操作的逻辑相对简单：

1. 对 key 计算哈希值，同样经过扰动处理。
2. 计算数组下标，取出该位置的节点。
3. 如果节点为空，直接返回 null。
4. 如果节点的 hash 和 key 都与目标匹配，直接返回 value。
5. 如果不匹配，判断节点是链表还是红黑树：
   • 链表：遍历链表逐个比较 hash 和 equals。
   • 红黑树：调用红黑树的查找方法。

这里要注意一个问题：hash相同不代表key一定相同，因为哈希函数有不确定性。所以判断 key 相等必须走equals方法。这也解释了为什么重写 equals 必须重写 hashCode——如果两个对象 equals 相等但 hashCode 不相等，那么它们会映射到不同的桶里，HashMap 就找不到了。

我试过踩这个坑，场景是拿自定义对象做 key，只重写了 equals 没重写 hashCode。结果就是同一个逻辑上相等的 key，第一次 put 存进去，第二次 get 永远取不到。排查了半天才发现是 hashCode 的问题。这个点值得单独拿出来强调：equals 相等的两个对象，hashCode 必须相等；hashCode 相等的两个对象，equals 不一定相等。这是 Java 集合框架的黄金法则。

3. 哈希冲突的几种解决策略对比

3.1 链地址法（拉链法）

链地址法是目前最常用的解决哈希冲突的方法，也是 HashMap 采用的方式。思路很简单：每个桶不直接存数据，而是存一个链表头。冲突的元素依次挂到链表后面。

优点是实现简单，对哈希函数的要求相对宽松，链表只需要在头部或尾部插入即可。缺点是极端情况下链表过长，性能下降。

JDK 1.8 中 HashMap 对链地址法做了一点改进：链表长度超过 8 且数组容量大于等于 64 时，链表会转换成红黑树。如果数组容量小于 64，会优先扩容而不是转红黑树。这个细节经常出现在面试题里，值得注意。

3.2 开放地址法

开放地址法解决冲突的思路和链地址法截然不同。它不引入额外数据结构，而是当发生冲突时，在数组内部寻找下一个空闲位置存储。

常见探测方式有三种：

• 线性探测：冲突时依次往后找，直到找到空位。缺点是容易产生“堆积”现象，即冲突的元素聚集在一起。
• 二次探测：探测步长是 1²、2²、3²……这样间隔越来越大，避免堆积。
• 双重散列：冲突时用另一个哈希函数计算步长，也就是走两步，一步定位，一步探测。

Java 中的 ThreadLocalMap 使用的就是开放地址法中的线性探测。它的适用场景是数据量小、哈希表负载因子不高的情况。如果负载因子太高，探测次数会急剧上升，性能下降很严重。

3.3 再哈希法

再哈希法的思路更“简单粗暴”：准备多个哈希函数，第一个冲突了就用第二个，第二个冲突了就用第三个。这种方法对哈希函数的分布性要求很高，实际应用中不如链地址法和开放地址法普及。Redis 的 rehash 思想和它有些类似，但实现上更复杂，还涉及渐进式搬迁。

三种方式各有优劣，简单整理成下面的表格：

4. 手写一个极简哈希表：从零到可运行

4.1 设计目标与关键参数

纸上谈兵讲再多原理，都不如自己动手写一个来得深刻。这一节带大家手写一个极简的哈希表，包含 put、get、remove、扩容这些核心功能。

不追求和生产级 HashMap 完全对标，重点是把“哈希函数 + 数组 + 链表 + 扩容”这条主链路走通。在动手之前，先确定几个关键参数：

• 初始容量：16
• 负载因子：0.75
• 底层结构：数组加链表

数组中的每个元素是一个 Node 节点，Node 里面存哈希值、键、值，以及指向下一个节点的引用。

4.2 核心代码实现

先定义节点类：

static class Node<K, V> { final int hash; final K key; V value; Node<K, V> next; Node(int hash, K key, V value, Node<K, V> next) { this.hash = hash; this.key = key; this.value = value; this.next = next; } }

然后是极简哈希表的主体：

public class SimpleHashMap<K, V> { static final int DEFAULT_INITIAL_CAPACITY = 16; static final float DEFAULT_LOAD_FACTOR = 0.75f; private Node<K, V>[] table; private int size; private int threshold; private final float loadFactor; public SimpleHashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; this.threshold = DEFAULT_INITIAL_CAPACITY; this.table = (Node<K, V>[]) new Node[DEFAULT_INITIAL_CAPACITY]; } static int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); } private int indexOf(int hash, int length) { return (length - 1) & hash; } public V put(K key, V value) { int hash = hash(key); int index = indexOf(hash, table.length); Node<K, V> first = table[index]; if (first == null) { table[index] = new Node<>(hash, key, value, null); size++; if (size > threshold) { resize(); } return null; } for (Node<K, V> n = first; n != null; n = n.next) { if (n.hash == hash && (n.key == key || (key != null && key.equals(n.key)))) { V oldValue = n.value; n.value = value; return oldValue; } } // 头插法插入新节点 table[index] = new Node<>(hash, key, value, first); size++; if (size > threshold) { resize(); } return null; } public V get(Object key) { int hash = hash(key); int index = indexOf(hash, table.length); Node<K, V> n = table[index]; while (n != null) { if (n.hash == hash && (n.key == key || (key != null && key.equals(n.key)))) { return n.value; } n = n.next; } return null; } public V remove(Object key) { int hash = hash(key); int index = indexOf(hash, table.length); Node<K, V> prev = table[index]; if (prev == null) { return null; } if (prev.hash == hash && (prev.key == key || (key != null && key.equals(prev.key)))) { table[index] = prev.next; size--; return prev.value; } Node<K, V> current = prev.next; while (current != null) { if (current.hash == hash && (current.key == key || (key != null && key.equals(current.key)))) { prev.next = current.next; size--; return current.value; } prev = current; current = current.next; } return null; } private void resize() { Node<K, V>[] oldTable = table; int oldCapacity = oldTable.length; int newCapacity = oldCapacity << 1; Node<K, V>[] newTable = (Node<K, V>[]) new Node[newCapacity]; for (int i = 0; i < oldCapacity; i++) { Node<K, V> n = oldTable[i]; if (n == null) { continue; } oldTable[i] = null; while (n != null) { Node<K, V> next = n.next; int newIndex = indexOf(n.hash, newCapacity); n.next = newTable[newIndex]; newTable[newIndex] = n; n = next; } } table = newTable; threshold = (int) (newCapacity * loadFactor); } public int size() { return size; } public boolean isEmpty() { return size == 0; } }

4.3 手写过程中的几个关键决策

写这个简易版哈希表的时候，有几个点值得展开讲：

首先是扰动函数。JDK 的 HashMap 把 hashCode 的高 16 位和低 16 位做异或，这样即使两个 key 的 hashCode 低位相同、高位不同，经过扰动后也能在取模运算中体现差异。我写的版本保持一致，因为这是性价比很高的优化。

其次是计算下标采用位运算而不是取模。(length - 1) & hash只有当 length 是 2 的幂次方时才等价于hash % length。这也是为什么 HashMap 在扩容时总是把容量翻倍，而不是随便扩大。这个设计看似简单，但一不小心就会踩坑。

最后是扩容逻辑。遍历每个桶，把桶里的每个节点重新计算新数组的下标并迁移。我这里用的是头插法，存在一个隐患：在并发环境下可能会形成环。JDK 1.8 改成了尾插法就是为了规避这个问题。但在多线程环境下，HashMap 依然不是安全的，这个后面会细讲。自己练习的时候，头插法足够理解核心逻辑了。

写完之后，我建议做一轮简单的功能验证：

public static void main(String[] args) { SimpleHashMap<String, Integer> map = new SimpleHashMap<>(); map.put("apple", 1); map.put("banana", 2); map.put("cherry", 3); System.out.println(map.get("apple")); System.out.println(map.get("banana")); System.out.println(map.get("cherry")); map.put("apple", 100); System.out.println(map.get("apple")); map.remove("banana"); System.out.println(map.get("banana")); for (int i = 0; i < 100; i++) { map.put("key" + i, i); } System.out.println(map.size()); System.out.println(map.get("key99")); }

这段代码覆盖了插入、更新、删除、扩容几个核心场景。如果你看到控制台输出符合预期，说明这个简易哈希表基本跑通了。建议多试一些自定义对象做 key 的场景，亲身感受一下 hashCode 和 equals 对结果的影响。

5. 容量、负载因子与扩容机制深度解读

5.1 为什么默认负载因子是 0.75

HashMap 的默认负载因子是 0.75f，这个数字不是随便拍的，而是 JDK 作者在时间和空间成本之间权衡的结果。

负载因子越大，意味着数组可以容纳更多的元素才扩容，空间利用率更高，但冲突也会更多，查询效率下降。负载因子越小，冲突更少，查询更快，但空间浪费严重，频繁扩容也会带来性能开销。

0.75 是时空权衡之后的选择，在大多数场景下表现均衡。如果业务场景对内存敏感，可以适当调大到 0.8 或 0.9；如果对查询性能敏感，可以调小到 0.5 或 0.6。但注意：这个值一旦设置，不要频繁变化，因为扩容计算依赖它。

5.2 为什么容量必须是 2 的幂次方

HashMap 要求初始容量为 2 的幂次方，即使你传入的初始容量不是，它也会计算出大于等于该数的最小 2 的幂次方。原因有两个：

第一，保证(n - 1) & hash能正确替代取模运算。当 n 为 2 的幂次方时，n - 1的二进制全部为 1，低位信息被完整保留。如果 n 不是 2 的幂次方，n - 1的二进制会存在 0，某些下标永远不可能被映射到，造成空间浪费和冲突加剧。

第二，扩容时可以利用位运算优化元素迁移。扩容后容量变为原来的两倍，元素的新位置只可能是“原位置”或者“原位置加旧容量”，取决于 hash 的新增那一位是 0 还是 1。这个特性让 JDK 1.8 的扩容实现非常高效，不需要重新计算每个元素的 hash。

5.3 扩容触发的时机与过程

扩容的触发条件是size > threshold，其中threshold = capacity * loadFactor。举个例子：初始容量 16，负载因子 0.75，threshold 就是 12。当元素数量超过 12 时，触发扩容，数组变成 32，threshold 变成 24。

扩容的核心操作是创建一个新数组，把旧数组中的元素重新分配到新数组。JDK 1.8 使用尾插法，按原链表的顺序分割成两条链：一条留在原下标，一条移动到原下标加旧容量的位置。这样既避免了并发下的死循环问题，又比逐个重新哈希效率更高。

5.4 预先设置容量避免频繁扩容

在实际开发中，如果我们能够预估元素数量，就应该在创建 HashMap 时指定初始容量，避免频繁扩容。这里有个很容易算错的地方：指定的初始容量要大于“元素数量除以负载因子”，才能保证不提前扩容。

举个例子，预估要存 1000 个元素，如果直接传入 1000，那么 threshold 会是1000 * 0.75 = 750。当存到第 751 个元素时就会扩容一次，白费了一次性能开销。

正确做法是：1000 / 0.75 = 1333.33，向上取整数。但因为 HashMap 会把容量调整为 2 的幂次方，所以传入 1334 时会得到 2048 的容量。也可以用new HashMap<>(1000 * 2)这种粗暴方式，保证容量绝对够。

6. 常见问题与性能排查实录

6.1 HashMap 为什么线程不安全

HashMap 在多线程环境下会出各种问题，主要有三个典型场景：

第一，多个线程同时 put 时可能导致数据覆盖。两个线程同时定位到同一个空桶，都执行了“检查为空”的操作，然后一个线程先写入，另一个线程后写入，前者数据就被覆盖了。

第二，扩容过程中可能出现数据丢失。多个线程同时触发扩容，都在迁移同一个桶里的链表节点，很容易出现某个节点的 next 指向被意外修改，导致部分节点丢失。

第三，JDK 1.7 中并发扩容还可能出现循环链表，get 操作进入死循环，CPU 飙升 100%。1.8 改用尾插法后解决了这个问题，但并发安全问题依然存在。

所以并发场景必须用 ConcurrentHashMap，它通过 CAS 和 synchronized（JDK 1.8 之后）等手段保证了线程安全，同时锁粒度更细，性能更好。

6.2 哈希碰撞导致的线上性能问题

有一次我排查线上一个接口变慢的问题，最终定位到是一个 HashMap 的 key 设计不合理。那个 key 是字符串拼接出来的，哈希值分布极度不均匀，大量 key 映射到了同一个桶里。因为数据量不大，没有触发红黑树转换，但链表已经很长了，每次查询都在遍历链表，性能从 O(1) 退化成了 O(n)。

排查思路是这样：先在压测环境复现，通过 jstack 抓线程栈，看到大量线程阻塞在 HashMap.getNode 上。然后写了个小脚本统计 key 哈希值分布，发现确实集中在少数几个桶。最后调整了 key 的生成方式，让哈希值分布更均匀，问题就解决了。

这个案例说明：哈希表性能好不好，哈希函数是关键。即使 HashMap 底层做了扰动处理，但 key 本身如果分布极差，性能还是会受很大影响。

6.3 自定义对象作为 key 的注意事项

工作里用的最多的就是 String 和 Integer，它们的 hashCode 实现已经非常优化了。但碰见需要自定义对象作为 key 的场景，一定要遵守这两条规则：

• 重写 equals 时必须重写 hashCode
• 保证 hash 计算所需的字段不可变

第一点前面已经说过了。第二点也很重要：如果作为 key 的对象的 hashCode 计算字段在放入 HashMap 之后被修改了，那么这个对象在 HashMap 中的位置就“失联”了。即使它还存在，用同样的 key 去 get 也找不到，因为计算出的新下标和存的时候的下标不一样了。这种 bug 非常隐蔽，很难排查。

6.4 常见问题速查表

6.5 一个小技巧：自定义初始容量

在创建 HashMap 时，如果知道元素的大致数量，可以这样设置：

// 预估存 1000 个元素 Map<String, String> map = new HashMap<>((int) (1000 / 0.75f) + 1);

这个写法按照“容量 = 元素数量 / 负载因子 + 1”来计算，能有效避免扩容。加 1 是为了处理浮点数向下取整可能导致的边界问题。

如果对内存不敏感，也可以直接用new HashMap<>(2048)这种“往大了设”的方式。在 JDK 8 中，HashMap 的初始容量只能是 2 的幂次方，传入 2048 就是 2048，不会再有额外的调整开销。

我个人在实际操作中的体会是：哈希表这个东西，表面上一看就会，但真到用的时候很容易踩坑。尤其是扩容机制和 hashCode 的约定，面试问得深一点，或者是线上排查问题，吃亏的基本都是这些细节。手写一个简易版本绝对值得，虽然生产环境不会有人用你自己写的哈希表，但这个从零到一的过程能把整个数据结构的脉络彻底想通。后续有时间的话，我打算写一篇哈希表系列的第二篇，重点讲 ConcurrentHashMap 的实现原理和线程安全方案，那个东西又是另一套值得仔细拆解的学问了。