哈希表 / 散列表

哈希表

• 哈希表也叫散列表
• 其添加、搜索、删除的流程都是类似的
  1、首先利用哈希函数生成 key 对应的 index, 复杂度级别
  2、根据 index 操作定位数组元素, 复杂度级别
• 哈希表示 空间换时间 的典型应用
• 哈希函数,也叫做散列函数
• 哈希表内部的数组元素,很多地方也叫 Bucket(桶),整个数组交 Buckets 或者 Bucket Array

哈希冲突

• 哈希冲突也叫做哈希碰撞, 两个不同的 key,经过哈希函数计算出相同的结果,称为哈希冲突
• 解决哈希冲突的常见方法有以下几种:
  1.开放定址法:按照一定规则向其他地址探测,直到遇到空桶
  2.再哈希:设计多个哈希函数
  3.链地址法:比如通过链表将同一 index 的元素串起来

JDK1.8 中的哈希冲突解决方案

• 默认使用单向链表将元素串起来
• 在添加元素时,可能会由单向链表转为红黑树来存储元素
  • 比如当哈希表容量≥64 且单向链表的节点数量大于 8 时
• 当红黑树节点数量少到一定程度时,又会转为单向链表
• JDK1.8 中的哈希表是使用链表+红黑树解决哈希冲突的

哈希函数

• 哈希表中哈希函数的实现步骤大概如下:
  1.先生成key的哈希值(必须是整数)
  2.再让 key 的哈希值跟数组的大小进行相关运算,生成一个索引值
• 为了提高效率,可以使用 & 位运算取代 % 运算,前提是将数组的长度设计为 2 的幂(2ⁿ)
• 良好的哈希函数可以使 哈希值更加均匀的分布,减少哈希冲突次数,提升哈希表的性能

如何生成 key 的哈希值

• key 的常见种类可能有: 整数、浮点数、字符串、自定义对象。不同种类的 key,哈希值的生成方式不一样,但目标是一致的
  • 尽量让每个 key 的哈希
  • 尽量让 key 的所有信息参与运算
• 在 java 中,HashMap 的 key 必须实现 hashCode、equals 方法,也允许 key 为 null

整数的哈希值

- [ ] 整数值当做哈希值, 比如 10 的哈希值就是 10

浮点数的哈希值

- [ ] 将存储的二进制格式转为整数值

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)(value ^ (value >>> 32));
} 

这里使用 >>> (右移) 和 ^ (异或) 的作用是:
1.高 32bit 和低 32bit 混合计算出 32bit 的哈希值
2.充分利用所有信息计算出哈希值

value	1111 1111 1111 1111 1111 1111 1111 1111 1011 0110 0011 1001 0110 1111 1100 1010
value >>> 32	0000 0000 0000 0000 0000 0000 0000 0000 1111 1111 1111 1111 1111 1111 1111 1111
value ^ (value >>> 32)	1111 1111 1111 1111 1111 1111 1111 1111 0100 1001 1100 0110 1001 0000 0011 0101

字符串的哈希值

• 整数 5489 是如何计算出来的

  • 5 * 10³ + 4 * 10² + 8 * 10¹ + 9 * 10⁰

• 字符串是由若干个字符组成的

  • 比如字符串 jack,由 j、a、c、k四个字符组成(字符的本质是一个整数)
  • 因此,jack 的哈希值可以表示为j * n³ + a * n² + c * n¹ + k * n⁰,等价于[(j * n + a) * n + c] * n + k

• 在 JDK,乘数 n 为 31,为什么使用 31?
  31 是一个寄素数, JVM 会将 31 * i 优化成(i << 5) - i
  31 不仅仅是符合 2ⁿ - 1,它还是一个寄素数(即是奇数,又是素数,也就是质数)
  素数和其他数相乘的结果比其他方式更容易产成唯一性,减少哈希冲突, 最终选择 31 是经过观测分布结果后的选择

• 如果哈希值太大,整型溢出怎么办?
  这里不需要做任何处理,因为我们需要的就是一个整型数值,溢出了那就溢出位截掉好了,反正也能得到整型数据

自定义对象作为 key

• 自定义对象作为 key ,最好同时重写 hashCode、equals 方法。
• equals: 用以判断 2 个 key 是否为同一个 key
  • 自反性: 对于任何非 null 的x, x.equals(x)必须返回 true
  • 对称性: 对于任何非 null 的x, y、如果 y.equals(x) 返回 true, x.equals(y) 必须返回 true
  • 传递性: 对于任何非 null 的 x、y、z,如果 x.equals(y)、y.equals(z)返回 true,那么 x.equals(z) 必须返回 true
  • 一致性: 对于任何非 null 的 x、y 只要 equals 的比较操作在对象中所用的信息没有被修改,多次调用 x.equals(y) 就会一致地返回 true,或者一致地返回 false
  • 对于任何非 null 的 x,x.equals(null) 必须返回 false
• hashCode: 必须保证 equals 为 true 的 2 个 key 的哈希值一样
• 反过来 hashCode 相等的 key,不一定 equals 为 true
• 不重写 hashCode 方法只重写 equals 会有什么后果?
  可能会导致 2 个 equals 为 true 的key 同时存在哈希表中

哈希值的进一步处理: 扰动计算

• 当我们获取别人的 hash 值,我们并不知道别人生成的 hash 是什么情况,所以有了扰动计算

private int hash(K key) {
  if(key == null) return 0;
  int h = key.hashCode();
  return (h^ (h >>> 16)) & (table.length - 1);
}

装填因子

• 装填因子(Load Factor): 节点总数量/哈希表桶数组长度,也叫负载因子
• 在 JDK1.8 的 HashMap 中,如果装填因子超过 0.75,就扩容为原来的 2 倍

TreeMap VS HashMap

• 何时选择 TreeMap?
  • 元素具备可比较性且要求升序遍历(按照元素从小到大)
• 何时选择HashMap
  • 无序遍历

LinkedHashMap

• 在 HashMap 的基础上维护元素的添加顺序,使得遍历的结果是遵从添加顺序的