哈希表

Preface

散列表的实现常常叫做散列（hashing），是一种用于以常数平均时间执行插入、删除和查找的技术。

通常又称其为哈希表，是一种非常有用的数据结构，有很多种实现方式，并且包含很多技巧，

整理这篇文章时，也重新阅读《数据结构与算法分析》的哈希部分，结合代码，更进一步了解一些概念。

哈希表与离散化相同点在于，都是将范围比较大的数据映射到范围较小的空间内，但是前者无序，后者有序，

哈希最重要的两个实现地方在于：如何构造一个好的散列函数和如何有效地解决冲突。

关于散列函数，在实际处理中或者算法中，分为整数和字符串两类，有不同的处理方式，

关于解决冲突，常见两种解决方式：分离链接法（拉链法）和开放定址法。

Details

1. 整数

如果 key 为整数，那么常见的方式就是确定一个素数，而后对其取余，一般避免负数。

关于素数的选择是非常有必要的，能够使得关键字的分配均匀，提高整体的性能。

解决算法题中常用的技巧就是寻找比数据规模大的第一个素数（最好尽可能的离 2 的整数幂远）,

比如数据规模是 10⁵ ，如果采用拉链法则声明为 100003，而开放寻址法则为 200003，经验值。

另外一个技巧就是，因为往往使用数组实现，(x % N + N) % N 可以避免负数的出现。

2. 字符串

关于字符串的处理方式，其实是一个具体的算法，称为 Rabin-Karp 算法，相较于 KMP 更常用。

核心思想就是将字符串转为数字处理，将字符串用 P 进制表示，而后计算出每一位的哈希值，

通过比较哈希值，来确定二者是否相等，关于 P 的选择一般为：131 或者 1331，而模数选择 2⁶⁴ ，

在计算子序列时，利用类似前缀和的方法，就可以求出子序列对应的哈希值。

在 Java 中可以用 long 来代替，但是其最大值是 2⁶³ - 1，取模可能会出现负数溢出，但是并不需要处理，

至于原因，经过调试猜测，尽管会溢出，但是并不像整数一样作为数组下标，其是独立的所以不会影响。

（这里如果以后遇到了更好的解答，会再补充）

private void solution(String s, int[][] queries) {
  	// 也可以取为 1331
    int P = 131;
    int N = 100010;
    long[] h = new long[N];
    long[] p = new long[N];
    p[0] = 1;
    
    for (int i = 0; i < s.length(); i++) {
      	// 尽管溢出，但是不需要处理
        h[i + 1] = h[i] * P + s.charAt(i);
        p[i + 1] = p[i] * P;
    }
    
    for (int i = 0; i < queries.length; i++) {
        int left1 = queries[i][0];
        int right1 = queries[i][1];
        int left2 = queries[i][2];
        int right2 = queries[i][3];
        if (get(h, p, left1, right1) == get(h, p, left2, right2)) {
        } else {
        }
    }
}

private long get(long[] h, long[] p, int left, int right) {
    return h[right] - h[left - 1] * p[right - left + 1]; 
}

3. 冲突处理

常见的有两种处理方式：分离链接法和开放定址法，还有一种双散列的方式。

分离链接法

将散列到同一个位置的所有元素保留到一个表中，如果这个元素是新元素，那么采用头插法插入到链表前端，

这样处理不仅仅因为方便，还因为新插入的元素最有可能不久后被访问到。

class Main {
    static int N = 100003;
    static int[] h = new int[N];
    static int[] e = new int[N];
    static int[] ne = new int[N];
    static int idx = 0;
    static {
        Arrays.fill(h, -1);
    }
    
    private static void insert(int x) {
        int k = (x % N + N) % N;
        e[idx] = x;
        ne[idx] = h[k];
        h[k] = idx++;
    }
    
    private static boolean find(int x) {
        int k = (x % N + N) % N;
        for (int i = h[k]; i != -1; i = ne[i]) {
            if (e[i] == x) {
                return true;
            }
        }
        return false;
    }
}

开放定址法

其又有三种处理方式：线性探测法、平方探测法和双散列，代码采用线性探测法实现。

思想比较简单，当前位置如果已经存在元素，那么就看下一个位置是否可取，直至结束。

class Main {
  	// 线性探测法
    static int N = 200003;
    static int[] h = new int[N];
    static int empty = Integer.MAX_VALUE;
    static {
        Arrays.fill(h, empty);
    }
    
    // 插入和删除均使用此方法
    private static int find(int x) {
        int k = (x % N + N) % N;
        while (h[k] != empty && h[k] != x) {
            if (++k == N) {
                k = 0;
            }
        }
        return k;
    }
}

接下来，更具体的深入理解这三种处理方式的差异：

1. 线性探测法糟糕的是，即使表相对较空，这样占据的单元也会开始形成一些区块，称为一次聚集，

   也就意味着，该区块中的任何关键字都需要多次试选才能解决冲突，性能受到影响，

   因此对于线性探测而言，让散列表填满元素并不是一个好主意，意味着大量的冲突出现。

2. 平方探测法是消除线性探测中一次聚集的问题，具体为如果遇到冲突，就平方级位置寻找，

   虽然排除了一次聚集，但是散列到同一位置上的元素带来了二次聚集的麻烦。

   除此之外，平方探测还有一个非常重要的结论：一旦表被填充超过一半，就不能保证插入成功了。

   结论证明：当表一半是空的，并且表的大小是素数，就能保证插入一个新元素。

3. 双散列包含一个用于处理冲突的 hash 函数，但要保证不能计算得到 0 值。

Final

前面介绍了如何散列以及处理冲突的方式，那么来到 JDK 源码中看看是如何实现的。

HashSet 和 HashMap 通常是用分离链接散列实现的，并且有一个重要变量：装填因子。

装填因子（load factor）为散利表中的元素个数对该表大小的比，

在处理过程中，如果超过了默认的界限值，就会 rehash 扩大散列表的大小。

关于源码的具体实现，还有很多值得学习和研究的地方，在以后的学习过程中不断补充。