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

　　摘要
　　哈希表整体结构就是一个数组，元素的结构是keyvalue形式，因为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的哈希值与数组的大小进行相关运算，生成一个索引值publicinthash（Objectkey）｛returnhashcode（key）table。length；｝
　　hashcode是生成哈希值的函数，也可以直接用JAVA中的标准函数hashCode（）。
　　这里可以用位运算替换运算，来提高效率。因为位运算是二进制运算，所以在设计数组的时候，需要将数组的长度设计为2的幂次方。publicinthash（Objectkey）｛returnhashcode（key）table。length；｝
　　一个良好的哈希函数，可以让生成的哈希值分布更加均匀，减少哈希冲突的次数，最终可以提升哈希表的性能。
　　Key的常见类型可能有证书、浮点数、字符串或者自定义对象，不同的类型生成哈希值的方式也会不一样，但是目标是一致的，就是尽量让每个Key的哈希值唯一，尽量让Key中的所有信息参与运算。
　　比如在Java中，Long的哈希值实现如下代码：publicstaticinthashCode（longvalue）｛return（int）（value（value）32））；｝
　　这里的和就是将高32bit和低32bit混合计算出32bit的哈希值。
　　在计算字符串的哈希值时，可以将字符串拆解成若干个字符，比如jack，将它拆解成j、a、c、k（字符的本质就是一个整数，所以jack的哈希值可以表示为jn3an2cn1kn0，表达式也可以写成〔（jna）nc〕nk，代码实现如下：Stringstringjack；inthashCode0；intlenstring。length（）；for（inti0；ilen；i）｛charcstring。charAt（i）；hashCode31hashCodec；｝
　　看上面代码时，可以发现，表达式中的n使用的是31这个数字，那么为什么用31呢？
　　因为31不仅符合221，而且它还是个奇素数（既是技术，又是素数，还是质数），素数和其他数相乘的结果比其他方式更容易产生唯一性，减少哈希冲突。
　　JDK中，乘数n也是用31，31也是经过观测分布结果后的选择，关于31的变体可以有以下几种：
　　31i（251）ii25i（i5）i