# 查找算法 - 散列表 - 《Yao' Blog》

#前言
#散列方法的三个条件
#散列函数
#碰撞处理

#前言

散列表类似于数组，可以把键映射成的散列值当作数组的索引值。通过这种操作，访问散列表就和访问数组一样快。散列表可以实现常数时间的查找和插入操作。使用散列的查找算法分为两步：第一步是用散列函数将被查找的键映射为数组的一个索引；第二步使处理碰撞冲突，碰撞冲突的解决方法主要为拉链法和线性探测法。

#散列方法的三个条件

一致性——等价的键一定产生相等的散列值；
高效性——计算简便；
均匀性——均匀地散列所有的键；

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

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

为了将一个32位的整数散列值转换成数组的索引，我们在实现中还要将默认的hashCode()得到的散列值和除留余数法结合起来产生一个0到M-1（M代表数组的大小）的整数。这在HashMap中是通过这行代码实现的：hash & (table.length - 1)。

#散列函数

散列函数将任意键转化为数组范围内的索引值（[0, M-1]内的整数），同时能够均匀分布所有的键。

正整数

将整数散列最常用的方法是除留余数法。选择大小为素数M的数组，对于任意正整数k，计算k%M可以得到一个位于[0, M-1]之间的散列值。注意 M 最好是一个素数，否则无法利用键包含的所有信息。例如 M 为 10k，那么只能利用键的后 k 位。

浮点数

将键表示为二进制数然后再使用除留余数法。

字符串

int hash = 0;
for (int i = 0; i < s.length(); i++) 
    hash = (R * hash + s.charAt(i)) % M;

R通常取31；

#将hashCode()的返回值转化为一个数组索引

Java 中的 hashCode() 实现了哈希函数，但是默认使用对象的内存地址值。在使用 hashCode() 时，应当结合除留余数法来使用。因为内存地址是 32 位整数，我们只需要 31 位的非负整数，因此应当屏蔽符号位之后再使用除留余数法。

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

#自定义hashCode()

使用 Java 的 HashMap 等自带的哈希表实现时，只需要去实现 Key 类型的 hashCode() 函数即可。Java 规定 hashCode() 能够将键均匀分布于所有的 32 位整数，Java 中的 String、Integer 等对象的 hashCode() 都能实现这一点。

public class Transaction {
    private final String who;
    private final Date when;
    private final double amount;
    public Transaction(String who, Date when, double amount) {
        this.who = who;
        this.when = when;
        this.amount = amount;
    }
    public int hashCode() {
        int hash = 17;
        int R = 31;
        hash = R * hash + who.hashCode();
        hash = R * hash + when.hashCode();
        hash = R * hash + ((Double) amount).hashCode();
        return hash;
    }
}

#碰撞处理

#基于拉链法的散列表

拉链法是将大小为 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;
}