算法复习 (二) 查找-散列表

发表于 更新于 分类于
本文字数： 4.9k 阅读时长 ≈ 4 分钟
简单整理了散列表的相关内容，内容包括：概述（什么是散列表、散列函数、哈希碰撞），实现（基于拉链法的散列表、基于线性探测法的散列表），总结。

散列表

一. 概述

1.1 什么是散列表

散列表（Hash table，也叫哈希表），是根据键（Key）而直接访问在内存储存位置的数据结构。也就是说，它通过计算一个关于键值的函数，将所需查询的数据映射到表中一个位置来访问记录，这加快了查找速度。这个映射函数称做散列函数，存放记录的数组称做散列表。

通过散列表我们可以在一般应用中拥有（均摊后）常数级别的查找和插入操作。

散列表的查找分为两步：

  1. 通过散列函数将被查找的键转化为数组的一个索引。
  2. 处理碰撞冲突的情况。

1.2 散列函数

散列函数的计算过程将键转化为数组的索引：如果我们有一个能保持M个键值对的数组，就需要一个能够将任意键转化为该数组范围内的索引（[0,M-1]）的散列函数。

严格来说，对于每种类型的键都需要一个与之对应的散列函数。

  • 正整数：常用除留余数法，数组大小为素数M，任意整数k除以M获得余数。选用素数的原因是避免无法均匀的散列。
  • 浮点数：0到1间的实数，可以乘以M并四舍五入得到一个0至M-1间的索引值。但这种方法使键的高位占更大作用，低位则没什么影响，Java中采用的修正方法是将键表示为二进制再使用除留余数法。
  • 字符串：也可以使用除留余数法，Java中有 charAt() 函数能返回一个char值，即一个非负16位整数。把字符串当作一个N位的R进制值，除以M并取余。Java默认使用类似 Horner 方法的算法，用N次乘法、加法和取余计算一个字符串的散列值。
  • 组合键：键类型包含多种类型，如多个整型变量组合，比如Date类型，可以通过 int hash = (((day * R + month) % M ) * R + year) % M 来计算散列值。只要R足够小，就可以得到一个0至M-1间的散列值。

Java为很多常用的数据类型重写了 hashcode() 方法（如String、Integer、Double、File和URL）。

总结，构建散列函数的常见方法：

  • 直接寻址法：

    取key或key的某个线性函数值为散列地址，如 h(key) = key 或 h(key) = a * key + b 。

    该方案效率较低，时间复杂度为 O(1) ，空间复杂度为 O(n) 。

    该方案不会有哈希冲突，但难以应对集合很大的情况。

  • 取模法：

    选择一个合适的正整数p，令 hash(key) = Key mod p ，一般选p为散列表长度。

  • 数字分析法：

    假设key是以r为基的数（如10为基的十进制），共有n个key，则key的每个位可能有r个不同的字符出现（0到9），但每个字符出现的频率未必相同，比较均分出现的次数会接近n/r，可以选取这些位重新组成新的数来作为散列地址。适合预先知道key的取值的情况。

  • 折叠法：

    将关键字分成位数为t的几个部分，然后把各部分按位对齐进行相加，所得的和舍弃进位，留下t位作为散列地址。适合于关键字位数很多且每位数字都分布比较均匀。

  • 平方取中法：

    将key进行平方运算，从结果中取若干位（与散列地址位数相同）作为散列地址。

  • 除留余数法：

    用key除以数字p（不大于散列表长度）的余数作为散列地址：Hash(key) = key % p 。

  • 随机数法：

    选取一个随机函数，用其返回值作为散列地址：Hash(key) = random(key) 。

    当关键字长度不相等时，可以采用该方法。

1.3 哈希碰撞

对不同的关键字可能得到同一散列地址，即 k1 != k2 ，而 f(k1) == f(k2) ，这种现象称为冲突（英语：Collision），也叫哈希冲突/碰撞。

处理哈希碰撞的方法，最常见的为前两种：

  • 开放地址法：当遇到哈希冲突时，依照增量规则向后取地址直到找到空闲地址为止。

    Hi(key) = ( H(key) + di ) mod m( i = 1, 2, … , k(k <= m - 1) )

    • H(key)为key的直接散列地址
    • m为散列表长度
    • di 为每次再探测时的地址增量

    首先计算出关键字的直接散列地址 H(key) 。若该地址已被占用，则继续查看 H(key) + di 的地址，直到找到空间地址为止。

    di 的取法有：

    • 线性探测法：di = 1, 2, 3, …, m - 1，弊端是元素积聚，没有均匀的分布元素，导致性能降低，多查询了越来越多的无关项。
    • 二次探测法：di = 12, -12, 22, -22, …, -k2( k <= m / 2 )，或 di = ( i++ )^2^ * ( di / |di| ) [ 1, -1, 4, -4, 9, -9 …… ] ，弊端是当剩余空间较少时，在还有空间的情况下会极有可能插入失败。
    • 双散列探测法：di = (i++) * Hash^2^(key) [ 1H, 2H, 3H …… ] ，Hash2(key) = p – (key mod p) ，Hash2(key) = (key % 97) + 1 ，其中p为小于表长的任意素数。通过另外一个散列函数来减少积聚问题，第二个函数需要排出散列值为0的情况，计算的散列值要和表长互素。
    • di = 伪随机序列，即伪随机再散列。

    使用该方案时删除操作不能直接删除，因为会影响到其它具有相同散列地址的元素查找地址，一般会添加一个特殊的标记来表示元素已被删除。

  • 链地址法/拉链法：

    • 若散列表空间为[0, m-1]，设置一个由m个指针组成的一维数组CH[m]，然后将所有散列地址为i的元素都插入到头指针为CH[i]的链表中。
    • 即将散列表每一个地址都对应一个链表，似乎链表会占用更多的空间，但实际使用中，因为装填因子的存在所以链地址法可能会更节省空间。
    • 通常情况下哈希表都非常高效，插入或查询都是O(1)，最差情况是集中映射到少量地址上，就会退化为链表查询，若被人通过Hash攻击的方式产生大量的碰撞，会导致本来高效的服务处理变得异常缓慢，可以通过限制表单提交长度等方法来防止此类攻击。

  • 再散列法：发生哈希冲突时，使用第二、第三个散列函数计算地址，直到无冲突，弊端是计算时间会大幅增加。

  • 建立一个公共溢出区：

    假设散列函数值域为[0, m-1]，HashTable[0, m-1]为基本表，另设存储空间OverTable[0, v]用于存储发生冲突的记录。

二. 实现

2.1 基于拉链法的散列表

下面这个简单的符号表维护了一条链表数组，通过散列函数来为每个键选择链表。创建 st[] 时需要进行类型转换，因为 Java 不允许泛型的数组。默认构造器会使用997条链表，此段简单的代码已经可以在已知符号表大小时得到不错的性能，当然还可以添加动态调整链表数组的大小（rehash-再散列）的功能，从而能在任意大小都能保证链表的短小。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public class SeparateChainingHashST<Key, Value> {
    private int N;//键值对总数
    private int M;//散列表大小
    private SequentialSearchST<Key, Value>[] st;//存放链表对象的数组
    
    public SeparateChainingHashST(){
        this(997);
    }
    
    public SeparateChainingHashST(int M){
        //创建M条链表
        this.M = M;
        st = (SequentialSearchST<Key, Value>[]) new SequentialSearchST[M];
        for(int i = 0;i < M;i++)
            st[i] = new SequentialSearchST();
    }
    
    private int hash(Key key){
        return (key.hashCode() & 0x7fffffff) % M;
    }
    
    public Value get(Key key){
        return (Value) st[hash(key)].get(key);
    }
    
    public void put(Key key, Value val){
        st[hash(key)].put(key, val);
    }
    
    ...
}

2.2 基于线性探测法的散列表

线性探测表通过空（null）来表示一簇键的结束，对于删除操作来说，直接将对应元素值设置为 null 是不行的，会导致此位置之后的元素无法被查找。正确的做法是将右侧所有键重新插入散列表。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
public class LinearProbingHashST<Key, Value> {
    private int N;//键值对总数
    private int M = 16;//线性探测表大小
    private key[] keys;//键数组
    private value[] vals;//值数组
    
    public LinearProbingHashST(){
        keys = (key[]) new Object[M];
        vals = (value[]) new Object[M];
    }    
    
    private int hash(Key key){//散列函数
        return (key.hashCode() & 0x7fffffff) % M;
    }
    
    private void resize(int cap){//再散列
        //实例化新的线性探测表
        LinearProbingHashST<Key, Value> t;
        t = new LinearProbingHashST<Key, Value>(cap);
        //循环遍历拷贝旧表元素
        for(int i = 0;i < M;i++)
        	if(keys[i] != null)
                t.put(keys[i], vals[i]);
        //更新当前引用，t为局部变量
        keys = t.keys;
        vals = t.vals;
        M = t.M;
    }
    
    public void put(Key key, Value val){
        if(N >= M/2) resize(M*2); //M加倍扩容散列表
        int i;
        //i散列得到索引，若键相等则替换值，否则检查下一个位置，直到对应key为空
        for(i = hash(key);keys[i] != null;i = (i + 1) % M)
            if(keys[i].equals(key)){
                vals[i] = val;
                return;
            }
		//将键值放入当前i
        keys[i] = key;
        vals[i] = val;
        N++;
    }
    
    public Value get(Key key){
        for(int i = hash(key);keys[i] != null;i = (i + 1) % M)
            if(keys[i].equals(key))
                return vals[i];
        return null;
    }
    
    public void delete(Key key){
        if(!contains(key)) return;
        int i = hash(key);
        //遍历键簇直到找到对应key
        while(!key.equals(key[i]))
            i = (i + 1) % M;
        
        //先将对应索引置空
        keys[i] = null;
        vals[i] = null;
        //更新i到下一个位置
        i = (i + 1) % M;
        
        //循环将后面元素重新加入散列表，直到遍历到下一个空
        while(keys[i] != null){
            Key keyToRedo = keys[i];
            Value valueToRedo = vals[i];
        	keys[i] = null;
        	vals[i] = null;
            N--;
            put(keyToRedo, valueToRedo);
            i = (i + 1) % M;
        }
        N--;
        //若此时键值对总数达到1/8表大小，则再散列缩小
        if(N > 0 && N == M/8) 
            resize(M/2);
    }
    
    ...
}

三. 各种符号表渐进性能的总结

参考：

🔗 《算法 第4版》