算法3.5 基于拉链法的散列表

  • 概述:将大小为M的数组中每个元素指向一条链表,链表中每个结点存储了散列值为该元素索引的键值对
  • 基本思想:选择足够大的M,使所有链表都尽可能短,且发生冲突的元素都在链表中
  • 查找:
    1. 根据散列值找到对应链表
    2. 沿着链表找到对应键

实现

使用了一般的链式类型SequentialSearchST扩展成散列表

  1. //拉链法
  2. public class SeparateChainHashST<Key, Value> {
  3.     private int N;//键值对总数
  4.     private int M;//散列表大小
  5.     private SeparateSearchST<Key, Value>[] st;
  7.     public SeparateChainHashST(){
  8.         this(997);//默认使用997条链表
  9.     }
  10.     public SeparateChainHashST(int M){
  11.         this.M = M;
  12.         st = (SeparateSearchST<Key, Value>[]) new  SeparateSearchST[M];
  13.         for (int i = 0; i < M; i++)
  14.             st[i] = new SeparateSearchST();//需要给对象数组元素创建实例
  15.     }
  17.     private int hash(Key key){ return (key.hashCode()&0x7fffffff)%M; }
  18.     public Value get(Key key){ return (Value)st[hash(key)].get(key); }
  19.     public void put(Key key, Value val){ st[hash(key)].put(key, val);}
  20. }

算法分析

  • 链表的平均长度永远为N/M
  • 命题:在M个链表,N个键的散列表中,(均匀散列假设成立时)任意一条链表中键的数量均在N/M的常数因子范围内的概率无限趋向于1
  • 性质:M个链表,N个键的散列表中,未命中查找和插入操作所需的比较次数为~N/M

散列表的大小

  • 选择适当的数组大小M,既不会浪费大量内存,也不会因为链表过长而增加查找时间

有序性操作

  • 散列的目的在于均匀分布键值,因此顺序信息无法保存,一切有序性操作(最大最小键,范围查找等)都需要线性级别时间开销,但在顺序不重要的符号表中,散列表是最快,最广泛使用的