散列表 | Yao's Blog

前言

散列表类似于数组，可以把键映射成的散列值当作数组的索引值。通过这种操作，访问散列表就和访问数组一样快。散列表可以实现常数时间的查找和插入操作。使用散列的查找算法分为两步：

用散列函数将被查找的键映射为数组的一个索引。
若有碰撞冲突则处理碰撞冲突，解决方法主要为拉链法和线性探测法。

散列函数的要求

主要为一致性、均匀性和高效性。

一致性：等价的键一定产生相等的散列值

Java 令所有的数据类型都继承了一个能够返回 32 比特整数的hashCode()。每一种数据类型的 hashCode() 都必须和 equals() 方法一致。也就是说，如果a.equals()返回true()，那么a.hashCode()和b.hashCode()的返回值必然相同。但要注意，如果a.hashCode()和b.hashCode()的返回值相同，a.equals()不一定返回true。

均匀性：均匀地散列所有的键

保证均匀性的最好办法就是保证键的每一位都在散列值的计算中起到了相同的作用；实现散列函数时最常见的错误就是忽略了键的高位。在 Java 的HashMap中，为了保证均匀性将默认散列函数得到的散列值与其高 16 位进行了异或运算重新得到了新的散列值。

高效性：计算简便

为了将一个 32 位的整数散列值转换成数组的索引，我们在实现中还要将默认的hashCode()返回的散列值和除留余数法结合起来产生一个 [0, M-1] 内的整数（M 代表数组的大小）。这在HashMap中是通过这行代码实现的：hash & (table.length - 1)，由于取模运算的效率很低，所以这里使用与运算提高效率。

散列函数构造方法

散列函数将任意键转化为数组范围内的索引值（[0, M-1] 内的整数），最好能够均匀分布所有的键，常用的方法有直接定址法和除留余数法。

直接定址法

直接使用键值本身或一个线性函数的计算结果作为哈希地址。因为关键字很少是连续的，所以直接定址法会造成空间上的大量浪费且适应性不强。

除留余数法

假设散列表的大小为 m，表中存在的元素数量为 n，那么除留余数法的公式为$hash(key)=key\bmod p,\ (p \le m)$。其中 p 为小于等于 m 且在 1.1n～1.7n 之间的一个素数。除留余数法可以很好的减少发生哈希冲突的可能性。

正整数和浮点数都可以直接使用除留余数法（浮点数需要转为二进制数之后再计算）。字符串则需要结合每一个字符：

int hash = 0;
for (int i = 0; i < s.length(); i++) 
    // R 通常取 31
    hash = (R * hash + s.charAt(i)) % M;

Java 默认的hashcode()方法直接使用了对象的内存地址值，结合除留余数法时应该屏蔽符号位之后再计算：

1
2
3

private int hash(Key x) {
	int hash = (x.hashCode() & 0x7fffffff) % M;
}

碰撞处理

基于拉链法的散列表

拉链法是将大小为 M 的数组中的每个元素指向一条链表，链表中的每个节点都存储了散列值为该元素的索引的键值对。基于拉链法的查找分为两步：首先根据散列值找到对应的链表，然后沿着链表顺序查找相应的键。

在实现基于拉链法的散列表时，要选择适当的数组大小 M，既不会因为空链表而浪费大量内存，也不会因为链表太长而在查找上浪费太多时间。

在需要快速查找最大或者最小的键，或者是查找某个范围内的键，散列表都不是最合适的选择，因为这些操作的运行时间都是线性的。

public class SeparateChainingHashST<Key, Value> {
    private int N;
    private int M;
    private SequentialSearchST<Key, Value>[] st;

    public SeparateChainingHashST() {
        this(997);
    }

    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();
        }
    }

    /*
    hash(key) => 散列值（数组索引）=> 数组找到对应的链表 => 链表。get(key) => return Value value
     */
    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 value) {
        st[hash(key)].put(key, value);
    }
}

基于线性探测法的散列表

用大小为 M 的数组保存 N 个键值对，其中 M > N，我们可以通过数组中的空位来解决碰撞冲突，基于这种策略开发的所有方法被称为开放地址散列表。线性探测法是开放地址散列表中最简单的方法。

当碰撞发生时，线性探测法直接查找散列表中的下一个位置，带来 3 种结果：

命中，该位置的键和被查找的键相同；
未命中，键为空（该位置没有键）；
继续查找，该位置的键和被查找的键不同；

开放地址类的散列表的核心思想是将内存作为散列表的空元素，这些空元素可以作为查找结束的标志。

public class LinearProbingHashST<Key, Value> {
    private int N;
    private int M = 16;
    private Key[] keys;
    private Value[] values;

    public LinearProbingHashST() {
        keys = (Key[]) new Object[M];
        values = (Value[]) new Object[M];
    }

    private int hash(Key key) {
        return (key.hashCode() & 0x7ffffff) % M;
    }

    public void put(Key key, Value value)

    public Value get(Key key)
    
    public void delete(Key key)
        
    private void resize(int M)
}

查找

要查找一个键值，我们先计算它的散列值然后开始顺序查找，如果找到则命中，否则直接检查散列表中的下一个位置（索引值+1），直到找到该键值或者一个空元。

public Value get(Key key) {
    for (int i = hash(key); keys[i] != null; i = (i + 1) % M) {
        if (keys[i].equals(key)) return values[i];
    }
    return null;
}

插入

如果新键的散列值的位置是一个空元素，那么就将键保存在那里；否则发生冲突，键值相等时修改 value 值，键值不相等时继续顺序查找直到一个空元素用来保存它。

public void put(Key key, Value value) {
    int i;
    for (i = hash(key); keys[i] != null; i = (i + 1) % M) {
        if (keys[i].equals(key)) {
            values[i] = value;
            return;
        }
    }
    keys[i] = key;
    values[i] = value;
    N++;
}

删除

直接将要删除的键所在的位置设为 null 是不行的，因为这会使在此位置之后的元素无法被查找（簇连续）。因此，我们需要将簇中被删除键的右侧的所有键重新插入散列表。

public void delete(Key key) {
    int i = hash(key);
    while (keys[i] != null && !key.equals(keys[i])) i = (i + 1) % M;

    if (keys[i] == null) return;

    keys[i] = null;
    values[i] = null;

    i = (i + 1) % M;

    while (keys[i] != null) {
        Key keytoRo = keys[i];
        Value valuetoRo = values[i];
        keys[i] = null;
        values[i] = null;

        N--;

        put(keytoRo, valuetoRo);

        i = (i + 1) % M;
    }
    N--;
}

散列表的性能指数

N/M 决定了散列表的性能，也被成为散列表的使用率。对于基于拉链法的散列表，N/M 是每一条链表的长度，一般大于 1；对于线性探测法的散列表，N/M 是表中已经被占用的空间的比例，不可能大于 1。

对于线性探测法，通过动态调整数组来保证使用率在 1/8～1/2 之间。对于拉链法，可以根据查找时间于（1+N/M）成正比选取合适的 M 即可。

调整数组的大小

线性探测法的平均成本取决于元素在插入数组后聚集成的连续的条目的长度，也叫做键簇。长键簇会导致探测次数的增长。为了保证散列表的性能，需要动态调整散列表数组的大小，使散列表的使用率不超过 1/2。

private void resize(int cap) {
    LinearProbingHashST<Key, Value> t;
    t = new LinearProbingHashST<>(cap);
    for (int i = 0; i < M; i++) {
        if (keys[i] != null) t.put(keys[i], values[i]);
    }
    keys = t.keys;
    values = t.values;
    M = t.M;
}

前言