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。

comments powered by Disqus