哈希表

在日常刷题过程中，只涉及到哈希表的使用，知道哈希表的增删改查的性能都是O(1)。

本文只讲述哈希表最经典的结构原理，优化方面不会深究。

1. 经典结构

哈希表基于Hash函数实现。

假设设置初始区域容量为17，就会有0~16号区域。

Java中最常用的哈希表莫过于HashMap和HashSet了，两者的结构一致，原理一致，唯独区别在于HashMap有伴随数据Value而HashSet没有。本文详解结构时以HashMap为例。

如果要将Key="abc"，Value=1存入哈希表，首先哈希表会使用哈希函数对key进行计算得到out，然后out再%17得到一个0~16的数，假设为1。然后哈希表遍历到1号区域，如果1号区域为空，就在1号区域后创建一个单向链表，将Key="abc"，Value=1作为一个节点连接到单项链表中。多加几对Key-Value与上述同理，最终构成一个经典的哈希表。

由于Hash函数的性质，我们可以知道哈希表每个区域连接的单项链表基本上都是均匀变长的。

如果我们想通过Key找到对应的Value，就把存储Key-Value的流程再走一遍即可。假如当前Key="abc"，那么哈希表先使用哈希函数对Key进行计算得到out，然后out再%17得到1，然后再遍历1号区域的单向链表最终找到对应节点，得到Value=1。

2. 扩容

如果在上面的哈希表中加入大量的Key-Value，假设加入N对Key-Value，那么哈希表遍历的平均长度就是N / 17。如果哈希表容量一直都是17，那么哈希表操作的性能远远达不到O(1)。

因此，我们需要统计哈希表中每一个单向链表的长度，一旦某一个单向链表的长度超过一个阈值，那么就要触发哈希表的扩容机制。

假设每一次扩容都是原来的一倍，那么触发了扩容机制后，区域容量就成了34。原本所有单向链表中的节点都需要被哈希函数重新计算，重新取模，重新挂载到新的哈希表中。原来所有节点由17个区域均分，现在由34个区域均分，因此我们可以将原哈希表中的所有单向链表长度减半。

当扩容后，假设我们需要在哈希表中进行查询操作，哈希函数对Key计算的时间复杂度为O(1)，取模的时间复杂度为O(1)，遍历单向链表的时间复杂度为O(K)（假设链中由K个节点，如果可以保证单向链表不会过长，那么在单向链表中增删改查的时间复杂度都为O(1)）。

扩容复杂度的计算比较复杂，假设我们加入了N对Key-Value且只要单向链表长度超过2就扩容一倍，那总共需要经历logN次扩容。那么加入N次总代价就为O(N)，均摊下来的单次的时间复杂度就为 O(1)

虽然哈希函数计算的时间复杂度为O(1)，但是实际上常数是比较大的，但是指标为O(1)。

像工程上的什么改进，如 链表长度达才多少就扩容，等等都只是在优化常数项时间，并不能改变其时间复杂度为 O(1)

3. 离线扩容技术

该技术像C++这种及时申请内存的语言做不了，但是Java和一些虚拟机托管的语言能够实现。

该技术能够在上述描述的扩容基础上，继续给扩容加速。

假设用户在使用哈希表A，哈希表A中的单向链表已经很长了，虽然操作的时间复杂度仍然可以达到O(1)，但是常数比较大。因此用户想给哈希表A扩容。

因为该哈希表A被JVM托管，所以即使用户不用，它也会在内存中一直存在。那么我们就可以在内存别处给哈希表A做扩容生成哈希表B，在扩容过程中是不妨碍用户使用哈希表A的。等扩容成功后，就把哈希表A的指针指向哈希表B，将哈希表A销毁即可。这样就进一步降低了哈希表的扩容代价。

这就是为什么可以说在使用层面上哈希表的时间复杂度为O(1)，而在理论上不是，理论上就是O(logN)。

4. 不同语言

哈希表在不同语言中的具体实现有所不同，因为不同语言可能会使用其他数据结构来对哈希表做再次优化。

Java就把哈希表中的单链表改成了红黑树，但是C++还是保持了最经典的哈希表结构。

RandomPool结构

题目：

设计一种结构，在该结构中有如下三个功能：

1.insert(key)：将某个Key加入到该结构，做到不重复加入。

2.delete(key)：将原本在结构中的某个Key移除。

3.getRandom()：等概率随机返回结构中的任何一个Key。

要求是以上三个方法的时间复杂度为O(1)。

分析：

本道题是一个使用哈希表层面的数据结构设计，不会使用到哈希表的原理。

本体采用两个哈希表相互辅助实现RandomPool结构，其中一个哈希表中存储的是 key—index，另一个哈希表中存储的是 index—key。两个表之间通过index实现数据的关联，可以完成双向数据查找的操作。

insert和getRandom操作没有什么特别之处，关键在于delete操作。如果直接删除结构中某一个Key和其对应的Index，那么势必会造成Index的不连续从而产生漏洞。这样在Random时就会出现多次随机生成Index，却击中不了当前存储在哈希表中的Index。因此在删除时，我们会将最后存入哈希表的Key覆盖掉目标Key，复用目标Key的Index，然后物理删除最后存入哈希表的Key。这样逻辑上既删除了目标Key，又不会造成Index的漏洞。

代码：

public class RandomPool {
    private int size;
    private final HashMap<K, Integer> keyIndexMap;
    private final HashMap<Integer, K> indexKeyMap;
    public RandomPool() {
        size = 0;
        keyIndexMap = new HashMap<K, Integer>();
        indexKeyMap = new HashMap<Integer, K>();
    }
    // insert(key)：将某个Key加入到该结构，做到不重复加入。
    public void insert(K key) {
        // 如果Key不存在，执行insert操作
        if (!keyIndexMap.containsKey(key)) {
            keyIndexMap.put(key, size);
            indexKeyMap.put(size ++, key);
        }
    }
    // delete(key)：将原本在结构中的某个Key移除。
    public void delete(String key) {
        // 如果Key存在，执行delete操作
        if (keyIndexMap.containsKey(key)) {
            // keyIndexMap中最后Key覆盖目标Key
            keyIndexMap.put(indexKeyMap.get(size), keyIndexMap.get(key));
            // indexKeyMap中最后Key覆盖目标Key
            indexKeyMap.put(keyIndexMap.get(key), indexKeyMap.get(size));
            // keyIndexMap中删除目标Key
            keyIndexMap.remove(key);
            // indexKeyMap中删除最后一个Key
            indexKeyMap.remove(size);
            size --;
        }
    }
    // getRandom()：等概率随机返回结构中的任何一个Key。
    public K getRandom() {
        if (size == 0) {
            return null;
        }
        int randomIndex = (int) (Math.random() * size);
        return indexKeyMap.get(randomIndex);
    }
}