散列 - 简书

一般想法

理想的散列表数据结构只不过是一个包含有关键字的具有固定大小的数组。

每个关键字被映射到从 $0$ ~ $TableSize-1$ 这个范围中的某个数，并且被放到合适的单元中。这个映射就叫做散列函数。理想情况下它应该计算起来简单，并且应该保证任何两个不同的关键字映射到不同的单元。不过这是不可能的，因为单元的数目是有限的，而关键字实际上是用不完的。因此，我们寻找一个散列函数，该函数要在单元间均匀地分配关键字。

这就是散列的基本想法。剩下的问题就是要选择一个函数，决定当两个关键字散列到同一个值的时候（这就叫做冲突），应该做什么以及如何确定散列表的大小。

散列函数（Hash函数）

JDK中String的hashCode函数：

    public int hashCode() {
        int h = hash;
        if (h == 0 && value.length > 0) {
            char val[] = value;  // value即String的字符数组

            for (int i = 0; i < value.length; i++) {
                h = 31 * h + val[i];
            }
            hash = h;
        }
        return h;
    }

散列函数：允许溢出，增加了小于0的检测

散列函数选择完成之后，剩下的主要编程细节就是如何解决冲突的消除问题。如果当一个元素被插入时与一个已经插入的元素散列到相同的值，那么就会产生一个冲突。解决这种冲突的方法有几种，下面讨论其中最简单的两种：分离链接法和开放定址法。

分离链接法

其做法是将散列到同一个值的所有元素保留到一个表中。

分离链接法的实现：

除链表外，很多方案都可以解决冲突现象：一颗二叉查找树或者另一个散列表等都将胜任这个工作。但是，我们期望散列表是大的并且散列函数是好的，那么所有的链表都应该是短的，从而任何复杂的尝试就都不值得考虑了。

因为一次查找的时间是计算散列函数值（对应数组下标）所需要的常数时间加上遍历链表所用的时间，所以我们希望链表尽可能的短。通过定义散列表的装填因子以及适当时候执行rehash函数，可以保证链表尽可能的短。

我们定义散列表的装填因子（load factor）为 $\lambda$ ：散列表中元素的个数与该表大小的比。分离链接法中的一般法则是使得表的大小与预料的元素个数大致相等（即让 $\lambda \approx 1$ ）。在上面的程序中，可以看出对应的装填因子大小为1：

  if(++currentSize > theLists.length)
      rehash();

如果装填因子超过1，那么我们将调用rehash函数扩大散列表的大小（即程序中数组的大小）。

不用链表的散列表（开放地址法）

线性探测法

平方探测法

双散列

再散列（rehash）

分离链接表的再散列：

探测散列表的再散列：

标准库中的散列表

HashMap的工作原理：
https://blog.csdn.net/suifeng629/article/details/82179996
https://zhuanlan.zhihu.com/p/28501879

ConcurrentHashMap底层实现原理：
https://www.jianshu.com/p/865c813f2726

最坏情形下O(1)访问的散列表

完美散列
布谷鸟散列
跳房子散列