哈希表的基本原理

• 在真正实现一个东西之前，我们需要搞清楚hash表

• 数组通过下标访问数据的一种扩展

• 核心：利用哈希函数，将键值映射到数组上（bucket）

• 哈希冲突：不同的键值对放在同样的位置

Hash Function 哈希函数

• 哈希函数是用来将一个字符串（或任何其他类型） 转化为小于哈希表大小且大于等于零的整数

• 一个好的哈希函数：
• 可以尽可能地减少冲突
• 算得快

哈希函数案例

• 一种广泛使用的哈希函数算法是使用数值33（Times 33 算法）

• hashcode(“abcd”) = (ascii(a) * 33 ^ 3 + ascii(b) * 33 ^ 2 + ascii(c) * 33 + ascii(d)) % HASH_SIZE = (97 * 33 ^ 3 + 98 * 33 ^ 2 + 99 * 33 + 100) % HASH_SIZE = 3595978 % HASH_SIZE

• 其中HASH_SIZE 表示哈希表的大小

• 给出一个字符串作为 key 和一个哈希表的大小，返回这个字符串的哈希值

哈希冲突

• 无论使用什么 hash function , 都需考虑冲突问题

• 为什么会有冲突？
• 表面原因：有一些 key 会 map 到相同的index上
• 本质：无限空间有限空间映射

如何解决冲突

• 设计好的 hash 函数

• 改变哈希索引
• Open hashing
• Closed hashing

• 扩容
• 装填因子 Load factor：size/capacity
• Java：LF > 0.75 , resize()

解决哈希冲突：Closed hashing

• 闭散列：开放定址法

• 线性探测
• hash = ( hash(key) + i ) % HASH_SIZE
i = 0, 1, 2, 3 ,,,,

• 插入/查找/删除怎么做？
• 二次探测/ 双重散列

• 闭散列存在的问题
• 数组容易被挤满

解决哈希冲突：Open hashing

• 开散列：拉链法

• 每个bucket对应一条链表，哈希值相同的元素直接连接在对应链表中

• 链表的头结点存储在哈希表中

• 拉链法的极端情况
• 一个数组全部都是 5 的倍数
• 这种情况会使链表非常长

• Java 7 hashMap 底层数据结构
• 数组 + 链表

• Jaava 8
• 数组 + 链表 + 红黑树

扩容：重哈希 rehashing

• 哈希表容量的大小在一开始是不确定的，在需要的时候，可以对底层数组进行扩容

• 一种简单策略：如果哈希表存储单元太多，将哈希表容量扩大一倍，并将所有的 key 的哈希值重新计算映射到新的 bucket 上

实现一个HashMap

• 属性

• 构造器

• 哈希函数

• 解决哈希冲突
• 拉链法
• 扩容

• 装填因子

• 方法实现
• put/get/remove