算法基础之哈希表

大家好，这里是教授.F

什么是哈希表：

      哈希表其实就是数组的pro版本。数组有下标，每个下标对应着一个值。哈希表也类似，哈希表有很多哈希值，然后每一个哈希值都会对应着一个值。就是这样：hash(key)

哈希表的要求：

        1.key必须是不变的。

这点非常重要。

所谓不可变类型，就是说这个对象一旦创建，它的值就不能再改变了。比如 Java 中的 String, Integer 等类型，一旦创建了这些对象，你就只能读取它的值，而不能再修改它的值了。

作为对比，Java 中的 ArrayList、LinkedList 这些对象，它们创建出来之后，可以往里面随意增删元素，所以它们是可变类型。

因此，你可以把 String 对象作为哈希表的 key，但不能把 ArrayList 对象作为哈希表的 key。

 如果使用ArrayList对象作为哈希表的key，那经常性的改变会导致每次计算 hashCode 都要遍历整个数组，复杂度是 O(N)，这样就会导致哈希表的增删查改操作的复杂度退化成 O(N)。

哈希函数：

        我们先来讨论一下，关于哈希表中key的取值我们想怎么来搞定？？？

我们想怎么根据key来得到一个唯一值。首先在java中每一个对象都有int hashCode()这个方法。在我们不重写hashCode()这个方法的时候，该方法就会返回对象的内存地址，恰恰我们就想拿到一个唯一的数值来进行转换。所以唯一值思路我们已经确定。但还有一个问题：hashCode()的类型是int类型，int可是有负数的啊。索引可不兴是负数啊！如果只是这样想 :

int h = key.hashCode();
h = Math.abs(h);

也是不行。因为int类型得负数 2 ^31 ，正数是 2 ^ 31 - 1。会发现数据溢出了。

               我们可以通过位运算来进行操作，将最高位得符号去掉。这样不仅能解决问题，而且位运算比算术运算快得多。

h = h & 0x7fffffff;
h 是一个整数变量，它代表某个哈希值。
0x7fffffff 是一个十六进制常量，
对应的二进制表示是 0111 1111 1111 1111 1111 1111 1111 1111。
它的最高位（即最左边的一位）是 0，其余位都是 1。
& 是按位与（AND）操作符，它将两个操作数的对应位进行逻辑与运算。
只有当两个操作数的对应位都是 1 时，结果位才是 1，否则结果位为 0。

但还有一个问题，就是这个 hashCode 一般都很大，我们需要把它映射成 table 数组的合法索引。

这是使用的技巧是取模。

 h % table.length;
这样就保证了在table数组的范围内
但是考虑性能，我们可以通过位运算来替代：
要将取模运算 h % table.length 用位运算来代替，
通常要求 table.length 是 2 的幂次方。这是因为取模运算可以用位运算来模拟，
而且当除数是 2 的幂次方时，这种替代特别高效。

假设 table.length 是 2 的幂次方，
比如 table.length = 2^k，那么 h % table.length 
可以等价地表示为 h & (table.length - 1)。

具体的替代方法如下：

将 table.length 减去 1，得到一个二进制全是 1 的数，
例如，当 table.length = 16 时，table.length - 1 = 15，
其二进制表示为 0000 0000 0000 1111。
这样得到的结果就是一个与原数相比，位数更低的数字。
比如对于 table.length = 16，它相当于对 h 的低 4 位进行了保留，而将高位清零。
这个结果就等价于对 h 取模 table.length，
因为对于任何整数 x，x % 2^k 的结果就是 x 的低 k 位的值。

 哈希冲突：

        现实中，我们通过这样计算哈希值，但是往往会造成哈希值相同，也就是哈希冲突，所以对于哈希冲突我们还要有解决方案：

以上就是出现情况的解决方案。

扩容和负载因子：

        为什么要引入这个东西，这个东西是什么？？？

首先上面出现的哈希冲突的解决方案会降低性能。

拉链法：就是在同一个位置使用链表进行串联，在查找的时候，时间复杂度为：O(K)，K 是这个链表的长度。

线性探查法：就是如果算出的哈希值位置已经被占了。我们就继续往后面寻找位置，直到找到一个空位置。时间复杂度为：O(K)，K 为连续探查的次数。

当哈希表有太多的key-value时，很容易出现冲突的情况，所以我们需要进行扩容。

负载因子（Load Factor）是指哈希表（Hash Table）中已存储元素数量与哈希表容量之比。

负载因子的计算公式也很简单，就是 size / table.length。其中 size 是哈希表里面的 key-value 对的数量，table.length 是哈希表底层数组的容量。

当哈希表内元素数量达到负载因子的时候，table数组就会进行扩容。