数据结构基础--哈希表

通过大量的异或，交换。打乱原本的样本结构，放大样本差异。

生成不相关的hash函数

正常一个hash函数的结果h为16字节，每个字节为一个16进制(0~9,a~f中的)的任意值。将前8为作为h1，后8位作为h2。

通过h1 + k * h2生成一个新的结果。并且他将于原本的h无关。

哈希函数特性的使用

大任务( hash % n )分流成N个小任务。

经典哈希表

经典的哈希表结构通过数组+链表的结构实现

哈希表的结构

哈希表的本质是一个数组，数组中每一个元素称为一个箱子(bin)，箱子中存放的是链表，链表节点中存放的键值对。

哈希表存储的过程

1. 根据 key 计算出它的哈希值 h。
2. 假设箱子的个数为 n，那么这个键值对应该放在第 (h % n) 个箱子中。
3. 哈希值h相同，通过链表存储在同一个箱子中。

自动扩容

当哈希表的效率因数组量过大造成损耗，进行扩容并重新简历哈希表

1. 当某一个链表上的节点个数超过某个系数(负载因子)，将进行扩容。
2. 扩容可以是离线的(在非活跃状态下进行扩容，重建哈希表，重建结束后再使用新的哈希表)

增删改查的时间复杂度

对key进行hash，通过下标寻址，查找一个短链表均为常数时间操作。

时间复杂度===》O(1)

设计RandomPool结构

需要的结构：

两个哈希表，一个size变量计数

每次添加一个新的key23：

1. 令size+1
2. 将key23作为key，size作为value，记录在第一个hashMap中
3. 将size作为key，key23作为value，记录在第二个haskMap中

读取随机key时，在第二个hashMap中用(1~size)作为key进行查询返回

删除key时，将末尾元素与删除元素的index互换，删除该元素。并将size-1。

布隆过滤器BloomFilter

布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都比一般的算法要好的多，缺点是有一定的误识别率和删除困难。

可以解决爬虫去重，黑名单问题。

实现一个bit类型数组，将数据容量扩容

1. 建立一个[基础类型]类型的数组
2. 一个Int类型可以表示成32bit的二进制数据，long类型则是64bit
3. 一个[Int]数组将是普通数组的32倍容量

以一个100长度的Int数组([bit]长度为3200)arr为例，当我们想修改第3000个bit：

1. 3000/32获得arr组的indexI

2. 3000%32获得arr[indexI]下，[bit]想要修改的indexB

3. 通过 arr[indexI] = (arr[IndexI] | (1 << indexB)) 进行修改

   1 左移 indexB 个位置，将会变成 00000010000 这种形式。然后与原本的 arr[IndexI] 相交，对应位置将会被修改为 1

可以用矩阵，将数据容量继续扩容

以Int数组为例

[1000]的数组可以代表3200个bit位

[1000][1000]的矩阵则可以代表3200*1000个bit位

布隆过滤器的实现

1. 准备一个长度为m的数组，通常是bit数组
2. 将指定的key用一个hash函数求出hash值
3. 将hash % m 确定一个位置，并将该位置从0修改成1
4. 重复用k不相关个hash函数，确定多个位置并修改成1

经过这个处理之后的数组，就是布隆过滤器。

5. 当一个新的key进行查询时，也通过多次hash计算，确定是否存在于布隆过滤器

布隆过滤器的误差

由于数组长度的限制，有可能导致描黑位置过多，导致失误命中概率过高。

通过调整hash函数个个数k，以及数组长度m。可以得到不同的失误率。

布隆过滤器的优势

由于内部通过hash函数定位，最终过滤器所占内存的大小与单样本的内存大小无关。

比如一个长度为1000000的字符串，也并不需要存进数组。只需要在数组中修改k个位置即可。

布隆过滤器长度公式

[bit]的长度m，样本量n，预期失误率p，ln是自然对数

布隆过滤器hash函数个数公式

布隆过滤器真是失误率

当m和k确定之后的失误率

经典服务器抗压结构

通过对key进行hash % n 可以将读写的压力均匀的分布给三个服务器

而这种结构，当加入新的服务器或减少原有的服务器。我们需要像hashMap的自动扩容一样需要重建整个映射。