3.4散列表

  • 定义:一种数组实现的无序符号表,需要使用算术操作将键转化为数组的索引来访问数组中的键值对

  • 散列的查找算法:

    1. 用散列函数将被查找键值转化为数组索引
    2. 处理碰撞冲突,需要面对多个键散列到相同索引值的情况:拉链法和现象探测法
  • 特点: 散列表在时间和空间取得权衡,是实现常数级别查找和插入的无序符号表

3.4.1 散列函数

  • 定义:对于一个M个键值对的数组,需要有一种散列函数将任意键转化为数组范围内(0~M-1)的索引

3.4.1.2~5 不同类型键对应不同散列函数

  • 正整数:除留余数法,选大小为素数M的数组,对任意正整数k,计算k/M的余数(k%M),就可以控制在0~M-1内,若M非素数,可能无法利用键中所有信息,如:键是十进制数,M是10,则只能利用键的后k位,如232%100=32, 2531%100=31
  • 浮点数:可以将0M-1范围,但有缺陷,高位的作用更大,最低位对结果影响几乎不计,修正方法:将键表示为二进制数后使用除留余数
  • 字符串:将字符串看做大整数后除留余数,Java的charAt()返回一个char值即非负16位整数,若R比任何字符都大,相当于将字符串当作N位R进制值,除以M取余
  1. int hash = 0;
  2. for(int i = 0; i < s.length(); i++){
  3.     hash = (R*hash + s.charAt(i)) % M);
  4. }
  • 组合键:如日期,day(两位数),month(两位数),year(四位数),类比字符串
  1. int hash = (((day*R + month) % M)*R + year) % M;

3.4.1.6 Java中约定

  • Java令所有数据类型都继承了一个返回32bit整数的hashCode()方法,hashCode()方法必须和equals()方法一致,a.equals(b)为true -> a.hashCode()==b.hashCode(),反之不成立两个对象hash值相同对象也可能不同,还需要equals()判断
  • 要为自定义数据类型编写散列函数,要同时重写hashCode()和equals(),因为默认散列函数会返回对象的内存地址.但Java为String,Integer,Double,File和URL这类对象都重写了hashCode()

3.4.1.7 将hashCode()返回值转换为索引

我们需要的是索引而非32位整数,因此需要结合hashCode()和除留余数法产生0~M-1索引

  1. private int hash(Key x){
  2.     return (x.hashCode() & 0x7fffffff) % M;
  3. }
  • 这个方法会将符号位屏蔽,将32位整数变成31位非负整数,然后对M取模,M通常为素数
  • Java中取模%操作可能是负数,所以不能直接x.hashCode()%M,且最大的整数Math.abs(x.hashCode())也会返回负值

均匀散列假设:散列函数能均匀且独立得将所有键散步在0~M-1之间

3.4.2 基于拉链法的散列表(算法3.5)

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