数据结构与算法基础（十八）哈希表

　　摘要
　　哈希表 整体结构就是一个数组，元素的结构是 key-value 形式，因为 key 可以是任意可能类型，那么就需要一个标准性的生成唯一索引方式，所以就引出哈希值这个名称。本文在介绍哈希表时，也着重的说明哈希值，了解哈希值的背景以及生成逻辑，才能更好地理解哈希表。
　　上期使用 红黑树 实现映射结构，这样的结构满足  Key 必须具备可比性，元素有顺序地分布 这两个特点。在实际的应用场景中，存在结构中的 元素是不需要有序的，并且 Key 也不具备可比较性 ，哈希表完全满足这样的应用场景。
　　比如设计一个公司的通讯录，存放所有员工的通讯信息，就可以拿手机号作为 index，员工的名称、职位等作为 value。用哈希表的方式可以将添加、删除和搜索的时间复杂度控制在 O(1)。
　　这时创建一个数组，手机号作为 index，然后存放 value。这样能将复杂度控制在 O(1)，但是这种 空间换时间 的方式也造成了一些其他问题，比如空间复杂度大（需要更多的空间），空间使用率极其低，非常浪费内存空间。
　　哈希表 就是空间换时间的处理方式，但是做了优化，在空间和时间两个纬度中达到适当的平衡。
　　哈希表也叫做散列表，整体结构就是一个数组 ，哈希表会将 key 用哈希函数处理之后返回 hash（哈希值），hash 就是哈希表中的 index这样的处理方式就可以满足搜索时间是 O(1)，这样的处理方式就可以满足搜索时间是 O(1)。因为哈希表中的 key 可能不具备可比较性，所以要做哈希处理。
　　在执行哈希函数之后返回的 hash，可能会出现相同的情况 ，这样的情况就是 哈希冲突 。解决哈希冲突常见的方法有这三种： 开放定址法：按照一定规则向其他地址探测，直到遇见空的位置插入； 再哈希法：设计多个哈希函数，避免出现 hash 相同的情况； 链地址法：比如通过链表将相同 index 的元素串联起来。
　　JDK1.8 解决哈希冲突的方式就是使用链地址法，其中的链表就是通过链表+红黑树的组合来实现 。比如当哈希表中的容量大于等于 64，并且单向链表的节点数大于 8 时，转换为红黑树，不满足这个条件时就使用单向链表。
　　哈希函数 是生成哈希值的实现方法，哈希函数的实现步骤大致分为两步： 生成 key 的哈希值（哈希值为整数值） key 的哈希值与数组的大小进行相关运算，生成一个索引值 public int hash(Object key) {   return hash_code(key) % table.length; }
　　hash_code   是生成哈希值的函数，也可以直接用 JAVA 中的标准函数  hashCode()  。
　　这里可以用  &   位运算替换  %   运算，来提高效率。因为  &   位运算是二进制运算，所以在设计数组的时候，需要将数组的长度设计为 2 的幂次方。 public int hash(Object key) {   return hash_code(key) & table.length; }
　　一个良好的哈希函数，可以让生成的哈希值分布更加均匀，减少哈希冲突的次数，最终可以提升哈希表的性能。
　　Key 的常见类型可能有证书、浮点数、字符串或者自定义对象，不同的类型生成哈希值的方式也会不一样，但是目标是一致的，就是 尽量让每个 Key 的哈希值唯一，尽量让 Key 中的所有信息参与运算 。
　　比如在 Java 中， Long   的哈希值实现如下代码： public static int hashCode(long value) {     return (int)(value ^ (value) >>> 32)); }
　　这里的  >>>   和  ^   就是将高 32 bit 和低 32 bit 混合计算出 32 bit 的哈希值。
　　在计算字符串的哈希值时，可以将字符串拆解成若干个字符，比如 jack，将它拆解成 j、a、c、k（字符的本质就是一个整数，所以 jack 的哈希值可以表示为 j * n3 + a * n2 + c * n1 + k * n0，表达式也可以写成 [(j * n + a) * n + c] * n + k，代码实现如下： String string = ＂jack＂; int hashCode = 0; int len = string.length(); for (int i = 0; i < len; i++) {     char c = string.charAt(i);     hashCode = 31 * hashCode + c; }
　　看上面代码时，可以发现，表达式中的  n   使用的是 31 这个数字，那么为什么用 31 呢？
　　因为 31 不仅符合 22 - 1 , 而且它还是个奇素数（既是技术，又是素数，还是质数），素数和其他数相乘的结果比其他方式更容易产生唯一性，减少哈希冲突。
　　JDK 中，乘数 n 也是用 31，31 也是经过观测分布结果后的选择，关于 31 的变体可以有以下几种：
　　31 * i = (25 - 1) * i = i * 25 - i = (i << 5) - i