哈希表HashTable一个线程安全的哈希表实现也叫散列表实现了Map接口存储key-value 键值对key 和 value 都不能为 nullO (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对比项HashMapHashTable线程安全非安全安全所有方法加 synchronized锁机制无锁锁整个哈希表全表锁性能非常快很慢高并发下性能极差key/value 是否允许 nullkey 允许 1 个 nullvalue 允许多个都不允许 null否则 NPE底层结构JDK8数组 链表 红黑树数组 链表无红黑树默认容量1611扩容方式扩容为原来的 2 倍扩容为原来的 2 倍 1哈希计算优化过扰动函数简单哈希计算迭代器快速失败fail-fast安全失败fail-safe父类继承 AbstractMap继承 Dictionary推荐使用✅ 推荐日常开发 99%❌ 不推荐老项目兼容关键区别1)线程安全 vs 非安全HashMap无锁→ 单线程飞快多线程会数据错乱、覆盖、死循环。HashTable所有方法都加 synchronized→ 多线程安全但整个表只能一个线程操作性能极低。2)是否允许 nullHashMapkey 可以存1 个 nullvalue 可以多个 null。HashTablekey、value 都不能为 null否则直接空指针异常。3)性能差距巨大HashMap无锁高吞吐。HashTable锁整张表高并发下性能差四、Java中的哈希表HashtableJDK 原生哈希表老旧、全表锁、线程安全现在基本不用HashMap主力哈希表非线程安全查询 / 增删效率极高ConcurrentHashMap并发场景专用线程安全、高性能HashSet底层基于HashMap只存 key用来去重底层统一模型数组 哈希函数 拉链法链表 / 红黑树五、HashTable的实际用途1. 多线程安全的键值存储用途 在多个线程同时读写数据时保证数据不混乱、不丢失、不出现异常。例如简单的共享配置存取老项目中的共享计数器多线程日志记录、标记2. 存在性判断、去重用途 判断某个 key 是否已经存在例如重复请求拦截黑名单校验任务去重3. 简单线程安全缓存用途 把不常变的数据缓存到内存提高访问速度。例如字典数据系统配置固定映射关系4. 线程安全计数统计用途 多线程环境下统计次数例如接口访问次数用户点击次数任务执行次数六、HashMap的实际用途1. 存储键值对映射最常用封装接口参数、返回结果状态码映射、字典配置临时数据组装、对象关联2. 快速查找、判断存在判断用户是否存在判断手机号是否重复黑名单、白名单校验缓存命中判断3. 数据去重列表去重日志去重批量数据去重4. 数据分组 / 一对多归集按分类分组商品按状态分组订单按部门分组员工5. 本地缓存热点数据缓存字典、配置、权限、地区数据减少数据库查询提升接口速度
HashTable详解
发布时间：2026/6/15 12:01:40
哈希表HashTable一个线程安全的哈希表实现也叫散列表实现了Map接口存储key-value 键值对key 和 value 都不能为 nullO (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对比项HashMapHashTable线程安全非安全安全所有方法加 synchronized锁机制无锁锁整个哈希表全表锁性能非常快很慢高并发下性能极差key/value 是否允许 nullkey 允许 1 个 nullvalue 允许多个都不允许 null否则 NPE底层结构JDK8数组 链表 红黑树数组 链表无红黑树默认容量1611扩容方式扩容为原来的 2 倍扩容为原来的 2 倍 1哈希计算优化过扰动函数简单哈希计算迭代器快速失败fail-fast安全失败fail-safe父类继承 AbstractMap继承 Dictionary推荐使用✅ 推荐日常开发 99%❌ 不推荐老项目兼容关键区别1)线程安全 vs 非安全HashMap无锁→ 单线程飞快多线程会数据错乱、覆盖、死循环。HashTable所有方法都加 synchronized→ 多线程安全但整个表只能一个线程操作性能极低。2)是否允许 nullHashMapkey 可以存1 个 nullvalue 可以多个 null。HashTablekey、value 都不能为 null否则直接空指针异常。3)性能差距巨大HashMap无锁高吞吐。HashTable锁整张表高并发下性能差四、Java中的哈希表HashtableJDK 原生哈希表老旧、全表锁、线程安全现在基本不用HashMap主力哈希表非线程安全查询 / 增删效率极高ConcurrentHashMap并发场景专用线程安全、高性能HashSet底层基于HashMap只存 key用来去重底层统一模型数组 哈希函数 拉链法链表 / 红黑树五、HashTable的实际用途1. 多线程安全的键值存储用途 在多个线程同时读写数据时保证数据不混乱、不丢失、不出现异常。例如简单的共享配置存取老项目中的共享计数器多线程日志记录、标记2. 存在性判断、去重用途 判断某个 key 是否已经存在例如重复请求拦截黑名单校验任务去重3. 简单线程安全缓存用途 把不常变的数据缓存到内存提高访问速度。例如字典数据系统配置固定映射关系4. 线程安全计数统计用途 多线程环境下统计次数例如接口访问次数用户点击次数任务执行次数六、HashMap的实际用途1. 存储键值对映射最常用封装接口参数、返回结果状态码映射、字典配置临时数据组装、对象关联2. 快速查找、判断存在判断用户是否存在判断手机号是否重复黑名单、白名单校验缓存命中判断3. 数据去重列表去重日志去重批量数据去重4. 数据分组 / 一对多归集按分类分组商品按状态分组订单按部门分组员工5. 本地缓存热点数据缓存字典、配置、权限、地区数据减少数据库查询提升接口速度
原理与嵌入式无感定位实战)
