散列表

链表实现 Github源码
数组实现 Github源码

如果你需要一个简单而不失优雅的无序数据表，那么散列表一定是你的首选。

在我们分布较好（近似均摊）的散列表内，查找、插入等操作一般在常数级别。

所有的数据结构都是在时间与空间上作出了平衡选择，而散列表则非常好的找到了平衡点。

散列表的难度比较简单，核心难度在于如何设计出一个优秀的散列函数，可以使我们均匀的分布每个键值。幸运的是，Java已经为我们准备好了不少常用的数据类型（Integer, String, Double, File, URL等）的散列函数——hashCode()。

散列函数

对于散列表而言，所有存储的键值，不论是什么类型的数据，都要通过散列函数转化为数组中的索引实现存储。而如何设计优秀散列函数，一直是算法专家和数学专家的问题。我们在这里仅提供一种简单思路。

• 假设散列表大小为M长度的整数数组，则每个存储的键值都应该分布在 0~M-1的数组区间。

假设键值的散列值为正整数k，则我们可以将**k % M**，那么我们得到的就是分布在0~M-1的某个值了。

• hashCode()返回的是一个32位比特整数，一般为内存地址经算法产生。

private int hash(Key key) {
    if (key == null) throw new IllegalArgumentException();
    return ((key.hashCode() & 0x7fffffff) % M);
}

上述代码是一个简单的散列函数，其中0x7fffffff是最大的正整数（无符号32位 0111 1111 1111 1111 1111 1111 1111 1111），通过&0x7fffffff，可以得到一个去符号的31位整数，然后再与M取余即可得到键的hash索引。

• 有时候hash索引会产生重复，处理好小整数M内的重复情况是关键。

软缓存

对于有些散列函数，在处理过程中比较耗时，我们可以采用临时变量存储计算后的hashCode()，Java中的String就是如此处理的。

散列表实现——链表

链表实现即为每个键所转化的索引放入一个M大小的数组中，再将索引重复的键值以链表的方式存储在每个数组内。（数组嵌套链表）

假设我们这里有一个顺序存放数据的链表SequentialSearchST，拥有get(key), put(key,value), delete(key)几个常用的方法，具体代码参见我的Github源码。

构造 constructor：

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

    private int hash(Key key) {
        if (key == null) throw new IllegalArgumentException();
        return ((key.hashCode() & 0x7fffffff) % M);
    }
}

查找 get：

public Value get(Key key) {
    if (key == null) throw new IllegalArgumentException();
    if (isEmpty()) throw new NoSuchElementException();
    return (Value) st[hash(key)].get(key);
}

插入 put：

public void put(Key key, Value value) {
    if (key == null) throw new IllegalArgumentException();
    if (value == null) {
        delete(key);
    } else {
     //动态调整散列表的大小
        if (N >= 10 * M) resize(2 * M);
        if (!st[hash(key)].contains(key)) N++;
        st[hash(key)].put(key, value);
    }
}

动态调整散列表的大小，这里的调整临界值非固定，这里达到1/10就调整只是为了较为均衡的分布利用空间。

动态调整 resize：

动态调整散列表的大小不是必须的，但如同数组的动态变换大小一样，这样可以优化内存的空间利用，减少重复copy次数带来的开销。

private void resize(int chains) {
    SeparateChainingHashST<Key, Value> temp = new SeparateChainingHashST(chains);
    for (int i = 0; i < M; i++) {
        Iterator<Key> iterator = st[i].keys().iterator();
        while (iterator.hasNext()) {
            Key key = iterator.next();
            Value value = st[i].get(key);
            temp.put(key, value);
        }
    }
    M = temp.M;
    N = temp.N;
    st = temp.st;
}

删除 delete：

public void delete(Key key) {
        if (key == null) throw new IllegalArgumentException();
        if (isEmpty()) throw new NoSuchElementException();
        if (get(key) == null) throw new NoSuchElementException();
        if (st[hash(key)].contains(key))
            N--;
        st[hash(key)].delete(key);
        if (M > 4 && N <= 2 * M) resize(M / 2);
    }

散列表实现——数组

实现散列表的另一种方式是通过数组来完成，用大小为M 的数组和N 的键值对（M > N）来存储。其中当键值对重复时，我们需要使用数组中的空位来解决冲突。这种方法也被称为开放地址散列表。

当碰撞发生时（某键的散列值已被使用），则我们直接向下寻找位置：

• 命中，键值相同。
• 未命中，键值为空（没有键），此时可执行插入。
• 继续向下，该键与当前键不同。

开放地址散列表的核心思想是与其将内存用作链表（与链表实现对比），不如将他们作为散列表中的空元素，这些空元素可以作为查找结束的标志。

我们在维护键对应的值的时候，采用并行数组来解决，一条保存键，一条保存值。

public class LinearProbingHashST<Key, Value> {
    private int N;      //total number of item
    private int M;      //Size of map , M > N
    private Key[] keys;
    private Value[] values;

    public LinearProbingHashST() {
        this(16);//default construct
    }

    public LinearProbingHashST(int cap) {
        this.M = cap;
        this.N = 0;
        keys = (Key[]) new Object[M];
        values = (Value[]) new Object[M];
    }

    private int hash(Key key) {
        if (key == null) throw new IllegalArgumentException();
        return ((key.hashCode() & 0x7fffffff) % M);
    }
    ...
}

查找 get：

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

由于是使用数组实现，所以查找比较简单，开销很小，最差情况也能在 O(logN) 内能完成。

插入 put：

public void put(Key key, Value value) {
    if (key == null) throw new IllegalArgumentException();
    if (N >= M / 2) resize(2 * M);
    if (value == null) delete(key);
    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++;
}

插入的时候，要注意散列表大小最好需要动态变化。这里为了保证使用的内存量和键值对数量的比例在某一范围内，采用1/2。

删除 delete：

1. 先查找到键的位置
2. 将键赋空删除
3. 如果删除的键后面没有键（不连续），则删除操作结束。
4. 如果删除的键后面连续还有键，则需要将后面的连续键向前移动一格位置。

前三步不难理解，那么第四步这么做的原因，主要是因为如果不将后面的键向前移动位置使之保持连续，那么在之后的查找过程中会出现错误。
比如（见上图）我们查找H，此时C已被删除。若我们不向前移动H，那么查找操作将会返回不存在H，因为H实际存储在7的位置（散列值为4）。

public void delete(Key key) {
    if (key == null) return;
    if (isEmpty() || !contains(key)) throw new NoSuchElementException();
    int i = hash(key);
    while (!key.equals(keys[i])) {
        i = (i + 1) % M;
    }
    keys[i] = null;
    values[i] = null;
    i = (i + 1) % M;
    while (keys[i] != null) {
        Key keyToRedo = keys[i];
        Value valueToRedo = values[i];
        keys[i] = null;
        values[i] = null;
        N--;
        put(keyToRedo, valueToRedo);
        i = (i + 1) % M;
    }
    N--;
    if (N > 0 && N <= M / 8) resize(M / 2);
}

键簇：

上面删除操作中提到连续的键值，这里引入一个概念——键簇来表示连续的键。数组实现的散列表操作平均开销是与键簇的分布直接相关的。

显然只有短小的键簇才能保证较高的效率。

因为当键簇长了后，每次查找（例如查找H）的遍历次数会越来越多，导致耗时增加。我们希望散列表中键簇的分布均匀且长度大部分合适。
对于不断的插入键，散列表会越填越满，直至连成大的键簇。这样性能会变的很差，为了保证性能，我们只能牺牲内存开销，动态的调整散列表的大小。

调整数组大小 resize：

private void resize(int cap) {//must be needed
    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;
}

实现比较简单，直接赋值一个新的大小的数组即可。

性能：

对于各种常见的符号表而言，这里做一个性能汇总：

算法	最坏情况	平均情况	内存使用
顺序查找（无序链表）	N	N	48N
二分查找（有序数组）	logN	logN	16N
二叉树查找（二叉树）	N	1.39logN	64N
红黑树查找（红黑树）	2logN	logN	64N
散列表（数组）	logN	N/M	48N+32M
散列表（链表）	logN	1.5(get) 2.5(put)	32N~128N

根据经验而言，一般会优先选用散列表，实现简单并且性能优秀。除非是其他因素，才会选择红黑树来实现，因为红黑树在logN内支持的操作更多。

谢谢观看。

---

参考文献：《算法导论》 《Algorithms, 4th Edition》