算法3.6 基于线性探测法的散列表

  • 概述:另一种散列表用大小M的数组保存N个键值对,M>N,依靠数组的空位解决碰撞冲突,这种方法叫做开放地址散列表
  • 线性探测法:碰撞发生时(某个散列值已经被占用),直接检查散列表下一位置,产生三种结果:
    1. 命中:该位置键和被查找键相同
    2. 未命中,键值为空
    3. 继续查找,该位置键和被查找键不同
  • 核心思想:与其将内存用作链表,不如作为散列表的空元素

实现

键与值分别在两个数组中

  1. public class LinearProbingHashST<Key, Value> {
  2.     private int N;//键值对总数
  3.     private int M;//散列表大小
  4.     private Key[] keys;//键
  5.     private Value[] vals;//值
  6.     public LinearProbingHashST(int M){
  7.         this.M = M;
  8.         keys = (Key[]) new Object[M];
  9.         vals = (Value[]) new Object[M];
  10.     }
  12.     private int hash(Key key){ return (key.hashCode()&0x7fffffff)%M;}
  14.     //可变长数组
  15.     private void resize(int cap){}
  17.     private boolean contains(Key key){
  18.         for (int i = hash(key); keys[i] != null; i = (i+1)%M){
  19.             if (keys[i].equals(key)) return true;
  20.         }
  21.         return false;
  22.     }
  24.     public Value get(Key key){
  25.         for (int i = hash(key); keys != null; i = (i+1)&M){
  26.             if (keys[i].equals(key)) return vals[i];
  27.         }
  28.         return null;
  30.     }
  31.     public void put(Key key, Value val){
  32.         if (N == M/2) resize(2*M);
  33.         for (int i = hash(key); keys[i] != null; i = (i+1)%M){//以键簇头开始,找到键簇末尾空元素
  34.             if (keys[i].equals(key)){ vals[i] = val;return; }//已存在,更新
  35.             keys[i] = key;
  36.             vals[i] = val;
  37.             N++;
  38.         }
  39.     }
  41.     public void delete(Key key){}
  42. }
  • 键和值分别在两个数组中,连续的键值叫做一簇,null为一簇的结束
    1. 一个新键的散列值是null,则保存在该位置
    2. 如果不是,则往后找到一个空位置

resize():变长函数

  1. //可变长数组
  2. private void resize(int cap){
  3.     LinearProbingHashST<Key, Value> t;
  4.     t = new LinearProbingHashST<>(cap);
  5.     for (int i = 0; i < M; i++)//读出所有非空键重新插入t
  6.         if (keys[i] != null)
  7.             put(keys[i], vals[i]);
  8.         keys = t.keys;
  9.         vals = t.vals;
  10. }
  • 开放地址散列表的N/M叫做散列表使用率,和拉链法意义完全不同,此时比值不被允许达到1(散列表满),因为散列表满会导致未命中的查找无限循环,需要动态调整使用率在1/8~1/2之间

delete():删除函数

  1. public void delete(Key key){
  2.     if (!contains(key)) return;
  3.     int i = hash(key);
  4.     //找到待删键值对
  5.     while (!keys[i].equals(key)){
  6.         i = (i+1)%M;
  7.     }
  8.     keys[i] = null;
  9.     vals[i] = null;
  10.     i = (i+1)%M;
  11.     //避免丢失同键簇的元素,需要依次删除再put()
  12.     while (keys[i] != null){
  13.         Key keyToRedo = keys[i];
  14.         Value valToRedo = vals[i];
  15.         keys[i] = null;
  16.         vals[i] = null;
  17.         N--;
  18.         put(keyToRedo, valToRedo);
  19.         i = (i+1)%M;
  20.     }
  21.     N--;
  22.     if (N > 0 && N == M/8) resize(M/2);
  23. }
  • 直接删除某个元素是错误的,会导致同一簇后面的元素无法再被访问,需要将被删除键右侧所有键值重新插入散列表

算法分析

  • 键簇:短小的键簇才能保证较高的效率
  • 命题:在大小M含有N=αM个键的线性探测散列表中,基于假设,命中和未命中查找所需探测次数分别为1/2(1+1/(1-α)²),当α为1/2时,分别为1.5次和2.5次,因此要动态调整大小

两种散列表对比

  • 大小调整:
    • 拉链法:调整不是必须的,只需要根据和(1+N/M)成正比选合适M
    • 线性探测法:必须调整,否则可能无限循环
  • 内存使用:
    • 拉链法:为每个键值都分配了一小块内存
    • 线性探测法: 整张表使用了两个很大的数组