Version: Next

哈希表

哈希表(Hash Table)也称散列表

  • 是一种键值对形式的数据结构key: value

哈希冲突 Hash Collision

  • 不同的 key 经过哈希函数计算出了相同的哈希值

解决哈希冲突的常见方法

开放定址法 (Open Addressing)

  • 按照一定的规则向其他地址探测，直到遇到空桶
  • 规则：
    • 线性探测：一个一个遍历着找
    • 平方探测：按照 1² 、2²、3²..间隔去找，意思就是先找附近的，附近没有就立刻加大步长往远处找

再哈希法 (Re-Hashing)

  • 设计多个哈希函数

链地址法 (Separate Chaining)

  • 通过链表将同一索引的元素串起来 (HashMap 的实现方式)

哈希函数

在哈希表中

  1. 先根据 Key 生成 哈希值，必须是 整数
  2. 让 哈希值 与 数组的大小 进行相关运算，生成一个 索引
public int hash(Object Key) {
return hash_code(key) % table.length; // 使用模
}
  • 为了提高效率可以用 & 位运算，将数组长度设定为 2的幂，这样 table.length 的二进制形式就是只有一位为 1 的二进制数，减 1 就可以变成 0000 1111 1111 类似的形式，再通过 & 运算可以最大程度反映哈希变化
    • 运算结果一定落在 [0, table.length - 1] 区间，正好可以做 索引
public int hash(Object Key) {
return hash_code(key) & (table.length - 1); // 二进制掩码
}

如何生成哈希值

良好哈希函数的标准

  • 让哈希值更加均匀分布 -> 减少哈希冲突 -> 提升哈希表性能

要计算哈希值的参数的类型可能是

  • 整数、浮点数、字符串、自定义对象
  • 不同的类型，生成哈希值的方式不同，但都要尽量使每个 key 的哈希值唯一
  • 尽量让 key 的所有信息参与运算
小贴士

在 Java 中，HashMap 的 Key 必须实现 hashCode 和 equals 方法，也允许 key 为 null

  • 因为 HashMap 的实现要用这两个方法

整数 Key

  • 直接使用整数作为 HashCode
Integer.toBinaryString(123);

浮点数 Key

  • 把浮点数在内存中的 0、1 编码当成一个整数作为 HashCode
int code = Float.floatToIntBits(10.6f);
Integer.toBinaryString(code);

Long Key

  • Long 8个字节，64位，而 Java 中 hashCode() 方法返回类型为 int ，4字节 32位
  • 无符号右移 32 位，再跟自身做异或
public static int hashCode(long value) {
return (int)(value ^ (value >>> 32));
}
  • >>> 和 ^
    • 实现 高32位 与 低32位 混合计算，得到 64位 哈希值
    • 返回时砍掉 高32位

字符串哈希

一个整数 5489 可被表示为 5 * 10³ + 4 * 10² + 8 * 10¹ + 9 * 10º

一个字符串由若干个 字符 组成

  • 字符的本质是一个整数，即 ASCII 码
  • 例如 work 可以表示为 w * n³ + o * n² + r * n + k * nº
  • 等价于 [(w * n + a) * n + c] * n + k
  • 在 JDK 中， n = 31
    • 31 是一个奇素数，JVM会将 31 * i 优化为 (i << 5) - i
public static void main(String[] args) {
String str = "work";
int len = str.length();
int hashCode = 0;
for (int i = 0; i < len; i++) {
char c = str.charAt(i);
hashCode = hashCode * 31 + c;
}
System.out.println("hashCode = " + hashCode);
}