数据结构之哈希表
哈希 (Hash、散列) 是电脑科学中一种对资料的处理方法，通过某种特定的函数/算法（称为散列函数/算法）将要检索的项与用来检索的索引（称为散列，或者散列值）关联起来，生成一种便于搜索的数据结构（称为散列表）。
哈希
Hash 就是把任意长度的输入，通过散列算法，变换成固定长度的输出，该输出就是散列值。直观解释起来，就是对一串数据 m 进行杂糅，输出另一段固定长度的数据 h，作为这段数据的特征（指纹）。也就是说，无论数据块 m 有多大，其输出值 h 为固定长度。这种转换是一种压缩映射。
Hash 主要应用于数据结构中和密码学中。
- 使用 Hash 的数据结构叫做哈希表，主要是为了提高查询的效率。
- 在密码学中，hash 算法的作用主要是用于消息摘要和签名，主要用于对整个消息的完整性进行校验。
hash 函数的特点：根据同一散列函数计算出的散列值如果不同，那么输入值肯定也不同。但是，根据同一散列函数计算出的散列值如果相同，输入值不一定相同。
常见的 hash 函数
直接定址法：直接以关键字k或者k加上某个常数（k+c）作为哈希地址。
数字分析法：提取关键字中取值比较均匀的数字作为哈希地址。
除留余数法：用关键字k除以某个不大于哈希表长度m的数p，将所得余数作为哈希表地址。
分段叠加法：按照哈希表地址位数将关键字分成位数相等的几部分，其中最后一部分可以比较短。然后将这几部分相加，舍弃最高进位后的结果就是该关键字的哈希地址。
平方取中法：如果关键字各个部分分布都不均匀的话，可以先求出它的平方值，然后按照需求取中间的几位作为哈希地址。
伪随机数法：采用一个伪随机数当作哈希函数。
哈希表
哈希表（Hash table，也叫散列表），是根据关键码值 (Key value) 而直接进行访问的数据结构。
根据键（Key）值将数据映射到内存中一个位置的函数称为哈希函数，根据哈希函数建立的记录数据的表称为哈希表。
使用哈希表可以进行非常快速的查找操作，查找时间为 O(1)， 且不需要元素排列有序。
尽管最坏的情况下，哈希表中查找一个元素的时间与链表中查找的时间相同，达到了O(n)。但在实际应用中，散列的查找的性能是极好的。在一些合理的假设下，在散列表中查找一个元素的平均时间是 O(1)。
哈希表实现过程
- 存储时，通过哈希函数计算记录的哈希地址，并按此地址存储该记录。
- 查找记录时，同样通过哈希函数计算记录的散列地址，按此散列地址访问该记录。
所以说散列技术既是一种存储方法，也是一种查找方法。它与线性表、树、图等数据结构不同的是，前面几种结构，数据元素之间都存在某种逻辑关系，而哈希技术之间数据元素不存在逻辑关系，它只与关键字有关系。因此，哈希主要是面向查找的存储结构。
处理冲突
冲突指不同键经过哈希函数计算得到相同的索引，这样造成索引重复的冲突，即 k1≠k2，而 f(k1)=f(k2)。
开放地址法
开放定址法就是产生冲突之后去寻找下一个空闲的空间，需要探测出一个尚未被占用的索引。因为需要探测，所以添加一个 key-value 对可能需要更多的时间，但是查找仍是 O(1) 时间复杂度的。
链表法
散列到同一位置的元素，不是继续往下探测，而是在这个位置是一个链表，这些元素则都放到这一个链表上。
python 中的哈希
hash() 用于获取取一个对象（字符串或者数值等）的哈希值，不能直接应用于 list、set、dict。
在 hash() 对对象使用时，所得的结果不仅和对象的内容有关，还和对象的 id()，也就是内存地址有关。
hash() 函数的对象字符不管有多长，返回的 hash 值都是固定长度的。
python 字典
python 的内建数据类型 dict 字典，就是用哈希表实现的。
Python 是使用开放寻址法中的二次探查来解决冲突的。然后如果使用的容量超过数组大小的 2/3，就申请更大的容量。数组大小较小的时候 resize 为 * 4，较大的时候 resize * 2。实际上是用左移的形式。
dict 和 HashMap 区别
pyhton dict 和 java HashMap 都是采用哈希表实现，不同的是 dict 在发生哈希冲突的时候采用了开放寻址法，而 HashMap 采用了链接法。
HashMap
在 JDK1.8 中，HashMap 底层是用数组 Node<K,V> 数组存储，数组中每个元素用链表存储元素，当元素超过 8 个时，将链表转化成红黑树存储。
布隆过滤器
布隆过滤器 Bloom Filter 是一种多哈希函数映射的快速查找算法。通常应用于快速判断一个元素是否属于集合，但是并不是严格要求 100% 正确的场合。
- 优点： 优空间效率和查询时间都远远超过一般的算法
- 缺点：有一定的误识别率，但是它只会把不存在集合中的元素误判成存在于集合中，而不会把存在集合中的元素误判成不存在集合中。且不能删除已经插入的关键词，因此该元素的位置会影响其他元素。
改进： 改进就是 counting Bloom filter，用一个 counter 数组代替位数组，就可以支持删除了
Bloom Filter 原理
Bloom Filter 实际上是一个很长的二进制向量和一系列随机映射函数，将一个值映射到布隆过滤器中，需要使用多个不同的哈希函数生成多个哈希值，然后在布隆过滤器中，给每个哈希值的 index 置 1。
判断一个元素是否存在于集合中，使用哈希函数得到多个哈希值，判断每个哈希值的 index 是否为 1，只要有一个是 0，这个元素就不可能存在集合中；但可能会误判，因为不同的元素计算出的哈希值可能是相同的，但在布隆过滤器中都是 1，如果计算出的 k 个位置全部为1，则可能在集合中。
如何选择哈希函数个数和布隆过滤器长度
布隆过滤器的长度会直接影响误报率，布隆过滤器越长其误报率越小。
哈希函数的个数越多则布隆过滤器 bit 位置位 1 的速度越快，那么布隆过滤器的效率越低；但是如果太少的话，误报率变高。
应用
利用布隆过滤器减少磁盘 IO 或者网络请求，因为一旦一个值必定不存在的话，就不用进行后续昂贵的查询请求。
性能较高的哈希函数有： MurmurHash、Fnv