数据结构——哈希表：散列函数与冲突处理

哈希表Hash Table是一种根据键直接访问数据的数据结构查找、插入、删除的平均时间复杂度都是 O(1)。HashMap、ConcurrentHashMap 的底层实现就是哈希表。一、哈希表原理数组 散列函数 键 → 散列函数 → 数组下标 put(张三, 100): 张三.hashCode() → 123456 → 456 % 16 → 下标 8 → 数组[8] 100 get(张三): 张三.hashCode() → 123456 → 456 % 16 → 下标 8 → 返回 数组[8] 的值二、散列函数// 1. 直接定址法H(key) a × key b// 适合关键字连续分布// 2. 除留余数法H(key) key % p最常用// p 一般取不大于表长的质数// 3. 数字分析法取关键字的若干位作为哈希地址// 适合已知关键字分布// 4. 平方取中法取 key² 的中间几位三、冲突处理冲突指不同 key 映射到同一个位置。1. 开放定址法线性探测法Thread 1 H(key) base 如果被占 → base1, base2, base3... 问题容易堆积 二次探测法 H(key) base 如果被占 → base1², base-1², base2², base-2²...2. 链地址法最常用每个位置维护一个链表冲突的元素挂在链表上。这就是 JDK 8 HashMap 的实现方式。// 查找过程// 1. 计算 hash 定位数组下标 O(1)// 2. 遍历链表/红黑树 O(➀) 或 O(log n) 觉得有用的话点赞 关注【张老师技术栈】吧每周更新 Java/Python/爬虫 实战干货不让你白来。