算法第四版 第三章 散列表

作者 柚爸

如果一个符号表里所有的键都是小整数, 那么用数组存放无序的符号表, 其速度要快很多, 无论是插入还查找, 都是常数级别.

现实中的键不可能这么好, 所以需要一种方法, 就是将任意类型的键转换成一个范围内的索引.

此外还有一个问题, 就是不同的键转换成相同的索引, 这时候就会发生碰撞, 即两个实际上不同的键, 对应了同一个位置. 这个时候不能简单的覆盖值, 而需要采取其他的方法来进行存储数据, 有拉链法和线性探测法来解决这个问题.

散列表是典型的空间和时间互相替换的例子, 如果内存很大, 可以直接用二进制键来当成键; 如果时间很充分, 可以直接使用数组, 这样就无需使用额外空间.

散列表则通过数据结构的组合, 找到了一种

  1. 散列函数
  2. 基于拉链法的散列表
  3. 基于线性探测法的散列表

散列函数

散列, 就是把东西打散列出, 其实也就是任意给出一个键, 将其转换成一个整数范围内的值. 而且必须要散, 也就是平均. 来看一些常用的方法:

  1. 正整数, 正整数可以将其取余, 一般余数需要使用一个素数, 否则就会出现不平均的情况. 一般可以取一个离目标所需长度最接近的素数, 比如100长度的数组, 可以取97或者101.
  2. 浮点数, 其实浮点数本质也是一串二进制数, 如果将其乘以一些数字然后取余, 会导致不平均. 所以可以直接用二进制来除
  3. 字符串, 字符串在底层是一个char*指针, 但其实可以将字符串也当成数字, 即把其当成N位的R进制值, 然后除以一个素数并取余.
  4. 组合键, 如果键含有多个整型变量, 可以按一种方法也将其当成一串数字来进行操作

Java的基类Object里带有一个hashcode()方法, 其默认返回对象的内存地址, 但这个一般不太能行, 因为内存地址很可能会重复, 尤其是堆内存反复使用的过程中. 所以一些常用的数据类型, Java为其实现了不同的hashcode()方法, 比如String, Integer, Double, File, URL.

对于普通的默认返回内存地址的hashcode()的结果, 算法里提供了一个去除符号位然后取余的方法:

private int hash(Key key){
    return (x.hashcode() & 0x7fffffff) % M
}

一般来说, 健壮的散列函数都是计算密集型的函数, 很耗费性能, 如果创建对象的时候直接计算, 效率不高. 所以Java里的hashcode会在第一次调用的时候计算散列值, 之后再调用就是缓存之后的散列值了.

基于拉链法的散列表

在有了散列函数之后, 下一步问题就是解决散列碰撞, 即实际不同的键, 经过散列函数计算出相同的值. 拉链法是一种解决方法, 即用一个链表存储相同散列值的键值对.

拉链实际上就是使用了一个指针数组, 每个元素指向一个数据结构用来保存多个键值对. 这里使用的数据结构是一个链表.

来看看散列表的实现:

public class SeparateChainingHashST<Key, Value> {
    private static final int INIT_CAPACITY = 4;

    private int n;
    private int m;
    private SequentialSearchST<Key, Value>[] st;

    //构造函数, 使用INIT_CAPACITY传入有参构造函数, 实际上这个数字就是数组的长度
    public SeparateChainingHashST() {
        this(INIT_CAPACITY);
    }

    //创建长度为m的链表数组
    public SeparateChainingHashST(int m) {
        this.m = m;
        st = (SequentialSearchST<Key, Value>[]) new SequentialSearchST[m];
        for (int i = 0; i < m; i++)
            st[i] = new SequentialSearchST<Key, Value>();
    }

    //哈希函数, 除以m取余数
    private int hash(Key key) {
        return (key.hashCode() & 0x7fffffff) % m;
    }

    //取键值, 先找到对应的数组的索引, 再从链表中符号表中取出key
    public Value get(Key key) {
        if (key == null) throw new IllegalArgumentException("argument to get() is null");
        int i = hash(key);
        return st[i].get(key);
    }

    //存入的时候同样先计算hash, 找到对应的链表, 再进行存储
    public void put(Key key, Value val) {
        if (key == null) throw new IllegalArgumentException("first argument to put() is null");
        if (val == null) {
            delete(key);
            return;
        }
        //这里其实要调整数组的长度了, 目前可以先忽略
        if (n >= 10*m) resize(2*m);

        //计算hash值, 找到对应的链表, 然后存入值.
        int i = hash(key);
        if (!st[i].contains(key)) n++;
        st[i].put(key, val);
    }

}

这其中定义了一个初始的数量, 然后还有两个数值n和m, 初始数量实际上是数组长度, n用来记录这个表中存储的键值对的数量, m是链表的数量, 也就是将n个元素放入m个链表里, 所以要除以m来取余数.

从本质上看, 散列表其实是更加复杂的数据结构组合, 即符号表和数组的组合, 依赖hash计算数组的索引, 然后找到一个符号表, 调用这个符号表来存储真正的键值对.

基于线性探测法的散列表

线性探测法是开放地址散列表的一种. 所谓开放地址, 相对于上一节, 索引是什么, 就放入什么位置, 这种是闭合地址, 即一一对应. 开放地址指的是散列计算出来的索引, 键值不一定就存在那个索引位置, 而是使用数组中的空位来解决碰撞问题.

线性探测法解决碰撞的方法是:

  1. 命中, 键和被查找的键相同
  2. 不命中, 当前的键是null
  3. 不命中, 当前的键不是null, 继续向后查找. 找到就更新或者取数, 如果是插入操作, 直到找到null还没找到, 就存在null的地方

这个算法的本质是将null当做一块连续的区域的终点, 也是查找结束的标记. 如果在一个区域里没有找到对应的键, 那么就新增.

一个使用双数组的线性探测符号表如下:

public class LinearProbingHashST<Key, Value> {
    private static final int INIT_CAPACITY = 4;

    //键值对总数
    private int n;

    //数组的长度, 两个数组一个存放键一个存放值
    private int m;
    private Key[] keys;
    private Value[] vals;

    //构造函数, 使用INIT_CAPACITY作为数组初始的长度
    public LinearProbingHashST() {
        this(INIT_CAPACITY);
    }

    public LinearProbingHashST(int capacity) {
        m = capacity;
        n = 0;
        keys = (Key[])   new Object[m];
        vals = (Value[]) new Object[m];
    }

    //插入函数
    public void put(Key key, Value val) {
        //依然是先判断键和值为空的情况
        if (key == null) throw new IllegalArgumentException("first argument to put() is null");

        if (val == null) {
            delete(key);
            return;
        }

        //如果已插入键值对的数量超过了数组长度的一半, 就扩充一倍的数组
        if (n >= m/2) resize(2*m);

        int i;
        //计算键的hash值, 然后开始搜索直到null的位置.
        for (i = hash(key); keys[i] != null; i = (i + 1) % m) {
            如果发现了键, 就更新值
            if (keys[i].equals(key)) {
                vals[i] = val;
                return;
            }
        }
        //循环结束之后如果没找到, 则i停留在null的位置, 将当前键值插入的两个数组的i索引处
        keys[i] = key;
        vals[i] = val;
        n++;
    }

    //查询函数
    public Value get(Key key) {
        if (key == null) throw new IllegalArgumentException("argument to get() is null");
        //与插入类似, 一样的循环, 在找到null之前如果找到了, 就返回对应的值
        for (int i = hash(key); keys[i] != null; i = (i + 1) % m)
            if (keys[i].equals(key))
                return vals[i];
        //for循环结束之后说明没找到, 返回null, 表明不存在该键
        return null;
    }

    //删除函数
    public void delete(Key key) {
        //检测键是否为空和是否存在
        if (key == null) throw new IllegalArgumentException("argument to delete() is null");
        if (!contains(key)) return;

        //先找到对应的i索引
        int i = hash(key);
        while (!key.equals(keys[i])) {
            i = (i + 1) % m;
        }

        //将两个数组对应的索引设置为空
        keys[i] = null;
        vals[i] = null;

        //这一步操作很关键, 由于设置了为null, 就是一个搜索终点, 其后的元素如果不调整位置, 就不会被找到
        i = (i + 1) % m;
        //从i+1的位置向后不断寻找
        while (keys[i] != null) {
            //用临时变量保存键和值, 然后设置当前位置为null, 数量也减少1, 然后重新插入这个键
            Key   keyToRehash = keys[i];
            Value valToRehash = vals[i];
            keys[i] = null;
            vals[i] = null;
            n--;
            put(keyToRehash, valToRehash);
            i = (i + 1) % m;
        }
        //这个n--是删除要删除的元素的操作, 放到了最后, 在所有其后的元素重新插入完成之后, 再将总键值数量减少1
        n--;

        //删除之后也记得要调整大小
        if (n > 0 && n <= m/8) resize(m/2);

        assert check();
    }

    //所有键的队列实现, 比较简单, 挨个将不是null的Key放入Queue中, 返回这个Queue即可.
    //由于Queue实现了迭代器, 所以可以对返回的Queue使用增强for循环
    public Iterable<Key> keys() {
        Queue<Key> queue = new Queue<Key>();
        for (int i = 0; i < m; i++)
            if (keys[i] != null) queue.enqueue(keys[i]);
        return queue;
    }
}

其他都是一些辅助函数, 可以看到, 其关键是在删除一个元素的同时, 将属于其后同一个查找组(叫做键簇)的元素全部重新插入符号表中.

使用线性探测符号表的话, 其数列长度是一个很重要的因素, 如果n=m, 会导致无限循环, 如果m远大于n, 则效率会好很多, 因为键簇既分散又小.

散列表的特点是:

  1. 很多时候是常数级别的插入和寻找操作
  2. 对键有要求, 每种类型的键都需要一个对应的散列函数
  3. 性能保证来自于散列函数的质量(还有散列表内部的存储空间)
  4. 虽然插入和寻找操作理论上耗时不多, 但散列函数可能是密集计算的性能杀手
  5. 难以实现有序的符号表

Java中的散列表有两种实现, java.util.TreeMap 是红黑树实现的符号表, java.util.HashMap 是散列表实现的符号表. 在实际中可以根据需要来取用.