1. 哈希表入门：为什么我们需要它？

1.1 先从一个生活中的例子说起

想象你开了一家快递驿站，每天要处理几百个快递。如果把所有快递都随便堆在地上，有人来取件时，你就得一个一个翻找，效率极低 —— 这就像 Java 中的数组顺序查找，时间复杂度是 O (n)。

如果给每个快递编个号，然后按照编号放到对应的格子里：1 号快递放 1 号格，2 号放 2 号格... 有人来取件时，只要报出编号，你直接去对应格子拿就行，一秒搞定 —— 这就是数组随机访问的优势，时间复杂度 O (1)。

但问题来了：如果快递的编号是 "SF1234567890" 这样的长字符串，而不是连续的数字呢？总不能开一个能放下所有可能字符串编号的格子柜吧？这太浪费空间了。

哈希表就是为了解决这个问题而生的：它能把任意类型的 "键"(比如字符串、对象) 转换成数组的下标，然后把 "值"(比如快递) 存在对应的位置上。这样既保留了数组 O (1) 随机访问的速度，又能灵活处理各种类型的键。

1.2 哈希表的核心定义

哈希表 (Hash Table)，也叫散列表，是一种基于键值对 (Key-Value) 存储数据的数据结构。它的核心思想是：

1. 通过一个哈希函数，将键 (Key) 映射成一个整数 (称为哈希值)
2. 将这个整数对数组长度取模，得到数组的下标
3. 将值 (Value) 存储在该下标对应的数组位置上

当需要查找数据时，我们用同样的哈希函数计算键的哈希值，直接定位到数组的对应位置取出值，整个过程几乎是瞬间完成的。

2. 哈希表的核心原理：搞懂这两个问题就够了

2.1 第一个问题：什么是哈希函数？

2.1.1 哈希函数的本质

哈希函数就是一个 "转换器"，它能把任意长度、任意类型的输入 (键)，转换成一个固定长度的整数输出 (哈希值)。

一个好的哈希函数应该满足：

• 一致性：相同的键必须产生相同的哈希值
• 均匀性：不同的键应该尽可能产生不同的哈希值，均匀分布在整个整数范围内
• 高效性：计算速度要非常快

2.1.2 Java 中 Object 类的 hashCode () 方法

在 Java 中，所有对象都继承自Object类，而Object类提供了一个native的hashCode()方法，用于返回对象的哈希值。

默认情况下，hashCode()方法返回的是对象的内存地址经过某种转换后的整数。但对于很多类来说，这个默认实现并不合适，比如：

String s1 = new String("hello");
String s2 = new String("hello");
System.out.println(s1 == s2); // false，两个不同的对象
System.out.println(s1.hashCode() == s2.hashCode()); // true，相同的内容产生相同的哈希值

String类重写了hashCode()方法，使得内容相同的字符串返回相同的哈希值，这样才能正确地作为哈希表的键。

2.2 第二个问题：哈希冲突怎么解决？

2.2.1 什么是哈希冲突？

理想情况下，每个不同的键都能映射到不同的数组下标。但现实是，哈希函数不可能做到绝对完美，总会出现两个不同的键，经过哈希函数计算后得到了相同的数组下标的情况，这就是哈希冲突。

比如，我们有一个长度为 10 的数组，键 "apple" 的哈希值是 15，对 10 取模得到下标 5；键 "banana" 的哈希值是 25，对 10 取模也得到下标 5。这时候两个键就冲突了，都想存在数组的 5 号位置。

2.2.2 解决哈希冲突的两种主流方法

解决哈希冲突的方法有很多，最常用的是以下两种：

方法一：链地址法 (拉链法)

这是 Java 中HashMap采用的方法。它的思想是：数组的每个位置不直接存值，而是存一个链表的头节点。当发生哈希冲突时，就把冲突的键值对添加到对应位置的链表中。

查找时，先通过哈希值找到数组下标，然后遍历该位置的链表，通过equals()方法比较键，找到对应的节点。

方法二：开放地址法

开放地址法的思想是：当发生哈希冲突时，就按照某种规则去寻找数组中其他空闲的位置，把数据存进去。最常见的是线性探测法：如果当前位置被占用了，就依次检查下一个位置，直到找到空闲位置。

开放地址法的优点是不需要额外的链表空间，但缺点是容易产生 "聚集" 现象，即连续的位置被占用，导致查找效率下降。Java 中的ThreadLocalMap采用的就是开放地址法。

3. Java 中 HashMap 的实现：从 JDK1.7 到 JDK1.8 + 的进化

3.1 HashMap 的整体数据结构

3.1.1 JDK1.7 及之前：数组 + 链表

在 JDK1.7 及之前，HashMap的底层就是一个数组 + 链表的结构。数组是HashMap的主体，链表是为了解决哈希冲突而存在的。

数组中的每个元素称为 "桶"(Bucket)，每个桶对应一个链表。当链表长度较长时，查找效率会退化为 O (n)，这是 JDK1.7HashMap的一个明显缺点。

3.1.2 JDK1.8 及之后：数组 + 链表 + 红黑树

为了解决链表过长导致的查找效率问题，JDK1.8 对HashMap进行了重大优化，引入了红黑树。

当某个桶中的链表长度大于等于 8，并且数组的总长度大于等于 64时，该链表会自动转换成红黑树。红黑树的查找时间复杂度是 O (log n)，比链表的 O (n) 快得多。

当红黑树中的节点数小于等于 6时，又会自动转换回链表。这是因为当节点数较少时，链表的遍历速度比红黑树的查找速度更快，而且红黑树需要额外的空间存储颜色、左右孩子等信息。

3.2 HashMap 的核心成员变量

要理解HashMap的工作原理，必须先搞懂它的几个核心成员变量：

// 默认初始容量：16，必须是2的幂
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 16

// 最大容量：2^30
static final int MAXIMUM_CAPACITY = 1 << 30;

// 默认负载因子：0.75
static final float DEFAULT_LOAD_FACTOR = 0.75f;

// 链表转红黑树的阈值：8
static final int TREEIFY_THRESHOLD = 8;

// 红黑树转链表的阈值：6
static final int UNTREEIFY_THRESHOLD = 6;

// 链表转红黑树的最小数组容量：64
static final int MIN_TREEIFY_CAPACITY = 64;

// 存储键值对的数组，长度总是2的幂
transient Node<K,V>[] table;

// 键值对的数量
transient int size;

// 扩容阈值：当size >= threshold时，触发扩容
// threshold = capacity * loadFactor
int threshold;

// 负载因子
final float loadFactor;

这里有一个非常重要的设计：HashMap 的容量总是 2 的幂。为什么要这么设计？我们在后面讲哈希函数和扩容机制时会详细解释。

3.3 HashMap 的核心方法源码解析

3.3.1 put () 方法：数据是怎么存进去的？

put()方法是HashMap最核心的方法，它的执行流程可以分为以下几步：

1. 判断数组是否为空：如果数组为空，调用resize()方法进行初始化
2. 计算键的哈希值和数组下标
3. 判断该下标位置是否为空：
   • 如果为空，直接创建一个新的Node节点存入该位置
   • 如果不为空，说明发生了哈希冲突，进入下一步
4. 判断该位置的节点类型：
   • 如果是红黑树节点，调用红黑树的putTreeVal()方法插入节点
   • 如果是链表节点，遍历链表：
     • 如果找到相同的键，用新值替换旧值
     • 如果遍历到链表末尾都没找到相同的键，在链表尾部插入新节点
     • 插入后判断链表长度是否达到 8，如果达到，调用treeifyBin()方法尝试将链表转为红黑树
5. 判断是否需要扩容：如果插入后size大于等于threshold，调用resize()方法进行扩容

JDK1.7 和 JDK1.8 的一个重要区别：JDK1.7 采用头插法插入链表节点，而 JDK1.8 采用尾插法。头插法在多线程环境下可能会导致链表成环，引发死循环，而尾插法避免了这个问题 (但HashMap仍然不是线程安全的)。

3.3.2 get () 方法：数据是怎么取出来的？

get()方法的执行流程相对简单：

1. 计算键的哈希值和数组下标
2. 获取该下标位置的第一个节点：
   • 如果第一个节点的键与要查找的键相同，直接返回该节点的值
   • 如果不同，判断节点类型：
     • 如果是红黑树节点，调用红黑树的getTreeNode()方法查找
     • 如果是链表节点，遍历链表，通过equals()方法比较键，找到对应的节点返回
3. 如果没找到，返回 null

3.3.3 resize () 方法：扩容机制详解

resize()方法是HashMap中最复杂的方法，它负责初始化数组和扩容数组。

什么时候触发扩容？

• 当数组为空时，初始化数组为默认容量 16
• 当size >= threshold时，触发扩容，数组容量变为原来的 2 倍

为什么容量总是 2 的幂？ 这是HashMap设计的精髓之一。当容量是 2 的幂时，hash & (capacity - 1)等价于hash % capacity，但位运算的效率比取模运算高得多。

比如，容量是 16 (二进制 10000)，capacity - 1就是 15 (二进制 01111)。任何数与 15 进行与运算，结果就是这个数的低 4 位，正好对应 0-15 的数组下标。

扩容时元素怎么重新分布？ 这是另一个精妙的设计。当容量变为原来的 2 倍时，元素的新下标只有两种可能：

• 原下标
• 原下标 + 原容量

这是因为，容量变为 2 倍后，capacity - 1的二进制表示只是在高位多了一个 1。比如，原容量 16 (01111)，新容量 32 (11111)。

元素的哈希值与新的capacity - 1进行与运算时，结果只比原来多了一位。如果这一位是 0，新下标就等于原下标；如果这一位是 1，新下标就等于原下标 + 原容量。

这样，我们不需要重新计算每个元素的哈希值，只需要看哈希值的这一位是 0 还是 1，就能确定它的新位置，大大提高了扩容的效率。

4. HashMap 的关键特性与常见陷阱

4.1 负载因子为什么默认是 0.75？

负载因子 (load factor) 是哈希表中 "填满程度" 的度量，它等于size / capacity。

负载因子越大，数组的空间利用率越高，但发生哈希冲突的概率也越大，查找效率越低；负载因子越小，哈希冲突的概率越小，但空间浪费越严重。

0.75 是一个在时间和空间之间取得平衡的最佳值。这是基于大量统计数据得出的结论：当负载因子为 0.75 时，哈希冲突的概率大约为 10%，此时哈希表的性能最好。

4.2 HashMap 允许 null 键和 null 值吗？

HashMap允许一个 null 键和多个 null 值。

当键为 null 时，它的哈希值被固定为 0，所以 null 键总是存在数组的 0 号位置。

注意：Hashtable不允许 null 键和 null 值，这是HashMap和Hashtable的一个重要区别。

4.3 自定义对象作为键时，为什么必须重写 hashCode () 和 equals ()？

如果我们用自定义的对象作为HashMap的键，而没有重写hashCode()和equals()方法，会发生什么？

class Person {
    String name;
    int age;

    public Person(String name, int age) {
        this.name = name;
        this.age = age;
    }
}

public class Test {
    public static void main(String[] args) {
        HashMap<Person, String> map = new HashMap<>();
        map.put(new Person("张三", 20), "学生");
        
        // 我们期望能通过相同内容的Person对象取出"学生"，但实际返回null
        System.out.println(map.get(new Person("张三", 20))); // null
    }
}

这是因为，默认的hashCode()方法返回的是对象的内存地址，两个不同的Person对象，即使内容相同，它们的内存地址也不同，所以哈希值不同，会被映射到数组的不同位置。

而默认的equals()方法也是比较对象的内存地址，所以即使碰巧哈希值相同，在遍历链表时也会认为这是两个不同的键。

正确的做法是：重写hashCode()方法，使得内容相同的对象返回相同的哈希值；重写equals()方法，使得内容相同的对象返回 true。

@Override
public int hashCode() {
    return Objects.hash(name, age);
}

@Override
public boolean equals(Object o) {
    if (this == o) return true;
    if (o == null || getClass() != o.getClass()) return false;
    Person person = (Person) o;
    return age == person.age && Objects.equals(name, person.name);
}

4.4 HashMap 是线程安全的吗？

HashMap 不是线程安全的。在多线程环境下，同时对HashMap进行修改操作 (比如 put、remove)，可能会导致数据不一致、链表成环等问题。

JDK1.7 中，多线程扩容可能会导致链表成环，引发死循环；JDK1.8 虽然用尾插法避免了死循环，但仍然可能出现数据丢失、覆盖等问题。

如果需要在多线程环境下使用哈希表，应该使用：

• ConcurrentHashMap：推荐使用，性能高，线程安全
• Hashtable：不推荐，性能低，所有方法都用synchronized修饰
• Collections.synchronizedMap(new HashMap<>())：不推荐，性能低，将所有操作都同步

5. Java 中其他常见的哈希表实现类

5.1 Hashtable

Hashtable是 Java 早期的哈希表实现，它的底层也是数组 + 链表。

与HashMap的主要区别：

• 线程安全：所有方法都用synchronized修饰，性能低
• 不允许 null 键和 null 值
• 初始容量是 11，扩容时变为原来的 2 倍 + 1
• 哈希函数不同：直接使用键的hashCode()值对容量取模

5.2 LinkedHashMap

LinkedHashMap继承自HashMap，它在HashMap的基础上，增加了一个双向链表，用于维护键值对的插入顺序或访问顺序。

LinkedHashMap有一个构造方法，可以指定accessOrder参数：

• accessOrder = false(默认)：按照插入顺序排序
• accessOrder = true：按照访问顺序排序，每次调用get()方法，都会将访问的节点移到链表尾部

LinkedHashMap非常适合实现LRU (最近最少使用) 缓存。

5.3 ConcurrentHashMap

ConcurrentHashMap是线程安全的哈希表，它的性能比Hashtable高得多。

JDK1.7 中，ConcurrentHashMap采用分段锁机制，将数组分成多个段 (Segment)，每个段有自己的锁。多个线程可以同时访问不同段的数据，提高了并发度。

JDK1.8 中，ConcurrentHashMap摒弃了分段锁，改用CAS + synchronized机制，粒度更细，性能更高。它的底层数据结构与 JDK1.8 的HashMap相同，也是数组 + 链表 + 红黑树。

6. 哈希表的优缺点与最佳实践

6.1 哈希表的优缺点

优点：

• 查找、插入、删除操作的平均时间复杂度都是 O (1)，性能极高
• 支持快速的键值对查找，非常适合需要频繁根据键查找值的场景

缺点：

• 哈希冲突会降低性能
• 无序，不支持按照键的顺序遍历
• 空间利用率不高，有一定的空间浪费

6.2 最佳实践

1. 合理设置初始容量：如果能预估数据量，在创建HashMap时指定初始容量，可以避免频繁扩容，提高性能。初始容量建议设置为预估数据量 / 0.75 + 1。
2. 使用不可变对象作为键：比如String、Integer等。如果使用可变对象作为键，当对象的内容发生变化时，它的哈希值也会变化，导致无法找到之前存储的值。
3. 重写 hashCode () 和 equals () 方法：当使用自定义对象作为键时，必须正确重写这两个方法。
4. 优先使用 ConcurrentHashMap：在多线程环境下，优先使用ConcurrentHashMap，而不是Hashtable或Collections.synchronizedMap()。
5. 避免频繁扩容：扩容是一个耗时的操作，尽量在初始化时就设置合适的容量。

7. 总结

哈希表是 Java 中最常用的数据结构之一，它的核心思想是通过哈希函数将键映射到数组下标，从而实现 O (1) 的随机访问。

JDK1.8 对HashMap进行了重大优化，引入了红黑树，解决了链表过长导致的性能问题。HashMap的容量总是 2 的幂，这是为了提高哈希计算和扩容的效率。

HashMap不是线程安全的，在多线程环境下应该使用ConcurrentHashMap。LinkedHashMap可以维护插入顺序或访问顺序，适合实现 LRU 缓存。

理解哈希表的原理，不仅能帮助我们写出更高效的代码，也是面试中必考的知识点。希望这篇文章能让你对 Java 哈希表有一个全面、深入的理解。