1. 哈希表（Hash Table）
(1) 定义
哈希表（Hash Table）：一种不允许值重复的顺序数据结构。（散列表）
- 利用 哈希函数(散列函数) 生成 key 对应的 index【￥
】
- 根据 index 操作定位数组元素【
哈希表是【空间换时间】的典型应用
哈希表内部的数组元素，也称Bucket(桶)，整个数组叫Buckets或Bucket Array
哈希表
(2) 哈希冲突（Hash Collision）
哈希冲突（Hash Collision）： 2个不同的key，经过 哈希函数 计算得出相同的结果（哈希碰撞）
- key1
key2，hash(key1)
hash(key2)
哈希冲突的解决办法：
- 开放地址法：按照一定规则向其他地址探测，直到遇到空桶
- 再哈希法：设计多个哈希函数
- 链地址法：比如通过链表将同一index的元素串起来
JDK1.8中的哈希表是使用 链表+红黑树 解决哈希冲突
哈希冲突
哈希冲突解决方法：链表+红黑树
(3) 哈希函数
哈希表中 哈希函数 的实现步骤如下：
- 生成 key的哈希值（必须是整数）
- 让 key的哈希值 跟 数组的大小 进行相关运算，生成一个索引值
public int hash(Object key) {
return hash_code(key) % table.length;
}
// 以 &运算 替代 %元素，以提高效率（将数组长度设计为2的幂 2^n）
public int hash(Object key) {
return hash_code(key) & (table.length - 1);
}
良好的哈希函数
- 让哈希值更加均匀分布 -> 减少哈希冲突次数 -> 提升哈希表的性能
(4) key的哈希值
key 的常见种类可能有
- 整数、浮点数、字符串、自定义对象
不同种类的 key，哈希值的生成方式不一样，但目标是一致的
- 尽量让每个
key的哈希值是唯一的- 尽量让
key的所有信息参与运算
在Java中，HashMap 的 key 必须实现 hashCode、equals 方法，也允许 key 为 null
1> 整数
- 整数值当做哈希值
比如 10 的哈希值就是 10
public static int hashCode(int value) {
return value;
}
2> 浮点数
- 将存储的二进制格式转为整数值
public static int hashCode(float value) {
return floatToIntBits(value);
}
3> Long和Double的哈希值
public static int hashCode(long value) {
return (int)(value ^ (value >>> 32));
}
public static int hashCode(double value) {
long bits = doubleToLongBits(value);
return (int)(bits ^ (bits >>> 32));
}
>>> 和 ^ 的作用是？
- 高
32bit和 低32bit混合计算出32bit的哈希值- 充分利用所有信息计算出哈希值
位运算
^ 按位异或运算符 ：参加运算的两个二进制位相同为0，相异为1
4> 字符串的哈希值
Q：整数 5489 是如何计算出来的？
- 5 ∗ 10^3 + 4 ∗ 10^2 + 8 ∗ 10^1 + 9 ∗ 10^0
字符串是由若干个字符组成的
比如字符串 jack，由 j、a、c、k 四个字符组成（字符的本质就是一个整数）
因此，jack 的哈希值可以表示为
j ∗ n^3 + a ∗ n^2 + c ∗ n^1 + k ∗ n^0
等价于
[ ( j ∗ n + a ) ∗ n + c ] ∗ n + k
Q：在JDK中，乘数 n 为 31，为什么使用 31？
- 31 是一个奇素数，
JVM会将31 * i优化成(i << 5) – i
(5) TreeMap vs HashMap
TreeMap适用：
- 元素具备 可比较性 且 要求升序遍历（按照元素从小到大）
HashMap适用
- 无序遍历
| TreeMap | HashMap | |
|---|---|---|
| 时间复杂度（平均）添加、删除、搜索 | ||
| key的可比较性 | 必须具备 | 不需要 |
| 元素的分布 | 有序 | 无序 |
