哈希数据结构

参考链接：https://blog.csdn.net/CRMEB/article/details/120820682

1. 哈希表

哈希表，即散列表（Hash table），是根据key value而直接进行访问的数据结构。也就是说，它通过把key value映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。

哈希作为一个非常常用的查找结构，它能够在O(1)的时间复杂度下进行数据查找。每次寻找的时候都对键进行计算从而得到一个数组下标值，然后通过下标拿到数组对应的数据，就能知道它是否存在于这个数组中了。

这种数据查找的数据结构就叫做哈希表，对键的计算的方法叫做哈希函数。在Java中，典型的Hash数据结构的类是HashMap。

哈希表的执行步骤：

• 对键进行哈希计算，得到一个哈希值
• 对哈希值进行计算得到一个数组下标
• 通过数组下标得到数组中对应的数组

由于哈希表的查找步骤和哈希函数是恒定不变的，因此哈希表的时间复杂度为O(1)。

2. 哈希函数

哈希函数是一种提取数值特征的算法，针对不同的数据形式有不同的哈希算法，所以哈希函数并不通用，针对不同的场景有很多不同的哈希算法，比如我们常见的MD5就是一种获取文件信息摘要的哈希算法。

再比如在Java中，对于常用的数据类型，JDK实现了多种不同的hash函数。

Integer的哈希函数是直接拿到它的值，对于字符串类型则是使用了对应的算法，对于浮点类型则是使用位运算的方式进行哈希计算。针对不同的数据结构使用不同的哈希计算方法的原因是为了哈希值的均匀，哈希越均匀，说明哈希函数设计的越好，也预示的哈希冲突的减少，关于哈希冲突，将在下一节讲到。

除了计算哈希值，我们还需要计算数组的位置。计算数组的位置有很多种方法可用，我们介绍一下简单的除留余数法：

假设对“中国人”这个key进行计算，得到一个哈希值19942986，那么我们将用这个数字对数组的大小进行取余，假设我们的数组大小为11，得到这样的计算公式：

19942986 % 11 = 8

那么，我们就得出了本次哈希函数的结果为数组下标8，我们就可以把中国人这个字符放到了数组下标为8的位置上。

既然哈希值越均匀越好，那么数组下标是否也有类似的需求呢？

是有的，比如我们上面的除留余数法，在除留余数法中，数组大小的选择将深刻影响着取余结果是否均匀，所以在除留余数法中，我们一般使用质数，这也是为什么HashTable的初始化大小为11，因为11是一个质数。

3. 哈希冲突

哈希冲突指的是多个不同的键散列到了同一个数组下标位置上，案例如下：

在上图中，耳、朵、不这三个字经过散列之后的数组下标都是0，而且因为是三个不同的值，所以也不能直接在数组上覆盖，那么我们就需要有一个办法把这三个值存起来。

这里将介绍两种常用的方法：开放地址法和链地址法。

开放地址法是一种比较简单的解决冲突的方法，它的原理非常简单：

在第一个耳字已经占用下标0后，第二个朵字则向后进行寻找空余的下标，找到后将自己设置进去，所以朵字在下标1处，以此类推。

根据寻找下标的方式不同，开放地址法可以分为以下几种：

线性探测法：下标被占用之后，以步长为1依次向后寻找，上图例中我使用的就是这种方法。

二次探测法：下标被占用之后，步长为2的倍数，依次向后寻找。

伪随机探测法：下标被占用后，随机出一个数字，然后使用这个数字作为下标进行寻找，这种方法全靠天意了。

其实原理都差不多，都是在当前下标的基础上向后寻找空余的下标，不过步长不一样罢了。
链地址法俗称拉链法，就是在冲突的下标元素处维护一个链表，所有冲突的元素都依次放到这个链表上去：

在上图中，我将冲突的两个键就按照顺序放在了链表中，下次寻找时只需要查看该数组元素以及遍历这个链表即可，在Java中的HashMap中就是用了这种方法进行解决哈希冲突。

以上两种方法都有可能随着冲突的增多，导致查找效率变低，所以没有一个完美的方案可以解决哈希冲突的问题，我一般推荐使用拉链法，因为它比较简单易理解。

4. HashMap案例

前文中大量提到了HashMap，这一节就将对HashMap中的一些和上文讲述不一样的关键点进行梳理。

首先是HashMap的表容量，表容量就是这个哈希表中可以装下多少个元素。

前文中我们说，在哈希表中最好使用质数作为表的容量，并且还拿了HashTable作为举例。而在HashMap中，初始容量为16，这不仅是一个偶数还是2的倍数。HashMap之所以没有使用质数而是使用2的倍数作为它的容量，是因为它在计算数组下标时没有使用除留余数法，而是使用了位运算进行计算数组下标。

 static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

计算完哈希值之后，则是使用哈希值和数组长度进行位运算：(tab.length - 1) & hash。

5. 手写哈希表

了解上边的哈希知识之后，我们就可以自己写一个类似Hashmap的数据结构。做一个哈希表的必要条件是：

哈希函数

哈希冲突方法