HashTable详解
哈希表（HashTable）
- 一个线程安全的哈希表实现，也叫散列表
- 实现了
Map接口，存储key-value 键值对 - key 和 value 都不能为 null
- O (1) 平均时间复杂度插入、删除、查找的数据结构
- 方法都加了
synchronized锁，所以线程安全 - JDK 1.0 就有，非常古老，现在基本不用，但面试 / 老项目会遇到
一、核心概念
1. 哈希函数（Hash Function）
把任意长度的键转换成固定长度的数组下标的函数。 公式：数组索引 = 哈希函数(键)
2. 哈希冲突（Hash Collision）
两个不同的键，通过哈希函数算出了同一个索引，这就是冲突。
哈希表必须解决冲突，常用方案：
- 链地址法（拉链法）：数组每个位置挂一个链表 / 红黑树（主流，如 HashMap）
- 开放寻址法：冲突时向后找空位置存放（如 ThreadLocalMap）
二、哈希表工作原理（极简流程）
- 初始化一个固定 / 动态扩容的数组
- 存入键值对：用哈希函数计算键的索引
- 找到对应位置存放数据
- 查找 / 删除：直接通过哈希函数定位索引，无需遍历整个数组
三、相关数据结构对比
1. 哈希表 vs 数组 vs 链表
| 结构 | 查找 | 插入 / 删除 | 适用场景 |
|---|---|---|---|
| 数组 | O(n) | O(n) | 数据少、有序遍历 |
| 链表 | O(n) | O(1) | 频繁插入删除 |
| 哈希表 | O(1) | O(1) | 快速查找、键值对存储 |
2. HashTable vs HashMap
| 对比项 | HashMap | HashTable |
|---|---|---|
| 线程安全 | 非安全 | 安全（所有方法加 synchronized） |
| 锁机制 | 无锁 | 锁整个哈希表（全表锁） |
| 性能 | 非常快 | 很慢（高并发下性能极差） |
| key/value 是否允许 null | key 允许 1 个 null，value 允许多个 | 都不允许 null，否则 NPE |
| 底层结构 | JDK8：数组 + 链表 + 红黑树 | 数组 + 链表（无红黑树） |
| 默认容量 | 16 | 11 |
| 扩容方式 | 扩容为原来的 2 倍 | 扩容为原来的 2 倍 + 1 |
| 哈希计算 | 优化过，扰动函数 | 简单哈希计算 |
| 迭代器 | 快速失败（fail-fast） | 安全失败（fail-safe） |
| 父类 | 继承 AbstractMap | 继承 Dictionary |
| 推荐使用 | ✅ 推荐（日常开发 99%） | ❌ 不推荐（老项目兼容） |
关键区别：
1)线程安全 vs 非安全
- HashMap：无锁→ 单线程飞快，多线程会数据错乱、覆盖、死循环。
- HashTable：所有方法都加 synchronized→ 多线程安全，但整个表只能一个线程操作，性能极低。
2)是否允许 null
- HashMap：key 可以存1 个 null，value 可以多个 null。
- HashTable：key、value 都不能为 null，否则直接空指针异常。
3)性能差距巨大
- HashMap：无锁，高吞吐。
- HashTable：锁整张表，高并发下性能差
四、Java中的哈希表
- Hashtable：JDK 原生哈希表，老旧、全表锁、线程安全，现在基本不用
- HashMap：主力哈希表，非线程安全，查询 / 增删效率极高
- ConcurrentHashMap：并发场景专用，线程安全、高性能
- HashSet：底层基于
HashMap，只存 key，用来去重
底层统一模型：数组 + 哈希函数 + 拉链法（链表 / 红黑树）
五、HashTable的实际用途
1. 多线程安全的键值存储
用途： 在多个线程同时读写数据时，保证数据不混乱、不丢失、不出现异常。
例如：
- 简单的共享配置存取
- 老项目中的共享计数器
- 多线程日志记录、标记
2. 存在性判断、去重
用途： 判断某个 key 是否已经存在
例如：
- 重复请求拦截
- 黑名单校验
- 任务去重
3. 简单线程安全缓存
用途： 把不常变的数据缓存到内存，提高访问速度。
例如：
- 字典数据
- 系统配置
- 固定映射关系
4. 线程安全计数统计
用途： 多线程环境下统计次数
例如：
- 接口访问次数
- 用户点击次数
- 任务执行次数
六、HashMap的实际用途
1. 存储键值对映射（最常用）：
- 封装接口参数、返回结果
- 状态码映射、字典配置
- 临时数据组装、对象关联
2. 快速查找、判断存在：
- 判断用户是否存在
- 判断手机号是否重复
- 黑名单、白名单校验
- 缓存命中判断
3. 数据去重：
- 列表去重
- 日志去重
- 批量数据去重
4. 数据分组 / 一对多归集：
- 按分类分组商品
- 按状态分组订单
- 按部门分组员工
5. 本地缓存（热点数据）：
- 缓存字典、配置、权限、地区数据
- 减少数据库查询
- 提升接口速度