java散列知识点总结

3 minute read

java 的根类 Object 具有 hashcode 方法。当 equal 方法被重写时也应当重写 hashcode 方法。

基本数据类型的散列码

  • byte short int char 类型的搜索键将会转换为 int。
  • float 类型的搜索键使用 Float.floatToIntBits(key) 作为散列码。
  • long 类型的搜索键会进行折叠操作，如下：
1iny hashCode = (int) (key ^ (key >> 32));
  • double 类型的搜索键会使用 Double.doubleToLongBits(key) 方法转换为 long 类型然后再进行折叠。

字符串类型的散列码

对于字符串一般使用多项式散列码进行计算，

这里放个公式的图

b的较好取值为31，33，37，39，41。在 java String 类中 b 取31。

 1public static int hash(String key, int tableSize)
 2{
 3    int hashVal = 0;
 4
 5    for (int i = 0; i < key.length(); i++)
 6        hashVal = 37*hashVal + key.charAt(i);
 7
 8    hashVal %= tableSize;
 9    if (hashVal < 0)
10        hashVal += tableSize;
11
12    return hashVal;
13}

压缩散列码

由于散列码可能是很大的正数，通常应该对其进行压缩以防止超出索引的范围。若索引范围为 0 ~ n - 1 ，通常的做法是 h(hashCode) = hashCode % N ，选择N为大于2的素数。 java.util.HashMap 的实现中，将N设置为2的幂值，这样可以使用位运算代替上述的取模：h(hashCode) = hashCode & (N - 1) ，两者是完全等价的。

处理冲突

开放地址法

开放地址法是在冲突发生时，在散列表中找到一个开放位置的过程。

  • 线性探测，存在成簇问题
  • 二次探测，存在二次成簇问题，并且不能保证一个开放的单元总是可以被找到。
  • 再哈希法

链地址法

链地址法是将具有同样索引的条目放在同一位置，每个位置使用一个桶(ArrayList or LinkedList)来放置多个条目。

装填因子

装填因子衡量一个散列表有多满。lamda = n / N 。对于开放地址法，装填因子介于 0 ~ 1，对于链地址法，装填因子可能为任意值。通常开放地址法需要将装填因子维持在0.5以下，而链地址法为0.9以下。java.util.HashMap 采用了阈值0.75。