哈希表 Hash table

哈希表（Hash table，散列表）

哈希表也叫做散列表，采用直接寻址技术，用于在表中快速检索信息，所期望的复杂度为O(1)，散列表所要做的就是利用散列函数将关键字集合映射到表上，最好能建立键与下标的一一对应的关系，同时因为压缩了待处理的下标范围，因此可以有效降低空间开销。

选择哈希函数的标准是简单快速计算，而且在下标范围内最好能够出现键的平均分布。

1.哈希表的几种构造方法分别可以用截取，即忽略键的一部分，而用剩余部分直接作为下标，缺点是不能够在表中均匀的分布所要加入的键；

2.折叠法，将键划分为几个部分并采用一种方便的方式进行组合以得到下标，这样做的好处是键中的所有信息都能够影响函数的值，可以比截取法获得更好的下标分布；

3.模运算，取余数作为结果，很大程度上依赖于模的选择，模通常是质数，以保持均匀的分布键。

对于哈希表中开放地址的冲突解决方案，最简单的是线性探测，也就是从冲突地址开始，在表中顺序查找期望的空位置；还有一种是链式的冲突解决方案，将哈希表本身作为一个链表数组。用链接的方式解决冲突的好处是节省空间，并且简单有效的解决了冲突的问题，而且不会出现溢出的问题。

哈希表是根据关键码的值而直接进行访问的数据结构，直白讲其实数组就是一张哈希表。

哈希表中关键码就是数组的索引下标，然后通过下标直接访问数组中的元素，如下图所示：

一般哈希表都是用来快速判断一个元素是否出现集合里。

例如要查询一个名字是否在这所学校里。

要枚举的话时间复杂度是O(n)，但如果使用哈希表的话， 只需要O(1) 就可以做到。

只需要初始化把这所学校里学生的名字都存在哈希表里，在查询的时候通过索引直接就可以知道这位同学在不在这所学校里了。

将学生姓名映射到哈希表上就涉及到了 hash function ，也就是哈希函数。

哈希函数

哈希函数，把学生的姓名直接映射为哈希表上的索引，然后就可以通过查询索引下标快速知道这位同学是否在这所学校里了。

哈希函数如下图所示，通过 hashCode 把名字转化为数值，一般 hashcode 是通过特定编码方式，可以将其他数据格式转化为不同的数值，这样就把学生名字映射为哈希表上的索引数字了。

如果 hashCode 得到的数值大于 哈希表的大小了，也就是大于 tableSize 了，怎么办呢？

此时为了保证映射出来的索引数值都落在哈希表上，会再次对数值做一个取模的操作，就保证了学生姓名一定可以映射到哈希表上了。

如果学生的数量大于哈希表的大小怎么办，此时就算哈希函数计算的再均匀，也避免不了会有几位学生的名字同时映射到哈希表 同一个索引下表的位置。

哈希碰撞

如图所示，小李和小王都映射到了索引下表 1的位置，这一现象叫做哈希碰撞。

一般哈希碰撞有两种解决方法， 拉链法和线性探测法。

拉链法

刚刚小李和小王在索引1的位置发生了冲突，发生冲突的元素都被存储在链表中。 这样我们就可以通过索引找到小李和小王了

（数据规模是 dataSize， 哈希表的大小为 tableSize）

其实拉链法就是要选择适当的哈希表的大小，这样既不会因为数组空值而浪费大量内存，也不会因为链表太长而在查找上浪费太多时间。

线性探测法

使用线性探测法，一定要保证 tableSize 大于 dataSize。 需要依靠哈希表中的空位来解决碰撞问题。

例如冲突的位置，放了小李，那么就向下找一个空位放置小王的信息。所以要求tableSize一定要大于dataSize ，要不然哈希表上就没有空置的位置来存放 冲突的数据了。如图所示：

常见的三种哈希结构

当使用哈希法来解决问题的时候，一般会选择如下三种数据结构。

数组
set （集合）
map（映射）

当遇到了要快速判断一个元素是否出现集合里的时候，就要考虑哈希法。

但是哈希法也是牺牲了空间换取了时间，因为要使用额外的数组，set 或者是map 来存放数据，才能实现快速的查找。