本文主要作为自己的学习笔记，并不具备过多的指导意义。
哈希函数
哈希函数
- 输入域无穷大
- 输出域有边界(1<<64)
- 输入相同的样本，一定得到相同的输出结果
- 不同的样本，有可能发生碰撞(结果相同)
- 在输入源样本量足够大的情况下，结果将在输出域上均匀分布。
哈希函数的离散性,能够打乱样本规律。
哈希函数实现的方式
通过大量的异或，交换。打乱原本的样本结构，放大样本差异。
生成不相关的hash函数
正常一个hash函数的结果h为16字节，每个字节为一个16进制(09,af中的)的任意值。将前8为作为h1，后8位作为h2。
通过h1 + k * h2生成一个新的结果。并且他将于原本的h无关。
哈希函数特性的使用
大任务(hash % n)分流成N个小任务。
经典哈希表
经典的哈希表结构通过数组+链表的结构实现
哈希表的结构
哈希表的本质是一个数组，数组中每一个元素称为一个箱子(bin)，箱子中存放的是链表，链表节点中存放的键值对。
哈希表存储的过程
- 根据 key 计算出它的哈希值 h。
- 假设箱子的个数为 n，那么这个键值对应该放在第 (h % n) 个箱子中。
- 哈希值h相同，通过链表存储在同一个箱子中。
自动扩容
当哈希表的效率因数组量过大造成损耗，进行扩容并重新简历哈希表
- 当某一个链表上的节点个数超过某个系数(负载因子)，将进行扩容。
- 扩容可以是离线的(在非活跃状态下进行扩容，重建哈希表，重建结束后再使用新的哈希表)
增删改查的时间复杂度
对key进行hash，通过下标寻址，查找一个短链表均为常数时间操作。
时间复杂度===》O(1)
设计RandomPool结构
【题目】 设计一种结构，在该结构中有如下三个功能：
insert(key)：将某个key加入到该结构，做到不重复加入。
delete(key)：将原本在结构中的某个key移除。
getRandom()： 等概率随机返回结构中的任何一个key。
【要求】 Insert、delete和getRandom方法的时间复杂度都是 O(1)
需要的结构：
两个哈希表，一个size变量计数
每次添加一个新的key23：
- 令size+1
- 将key23作为key，size作为value，记录在第一个hashMap中
- 将size作为key，key23作为value，记录在第二个haskMap中
读取随机key时，在第二个hashMap中用(1~size)作为key进行查询返回
删除key时，将末尾元素与删除元素的index互换，删除该元素。并将size-1。
布隆过滤器BloomFilter
布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都比一般的算法要好的多，缺点是有一定的误识别率和删除困难。
可以解决爬虫去重，黑名单问题。
实现一个bit类型数组，将数据容量扩容
- 建立一个[基础类型]类型的数组
- 一个Int类型可以表示成32bit的二进制数据，long类型则是64bit
- 一个[Int]数组将是普通数组的32倍容量
以一个100长度的Int数组([bit]长度为3200)arr为例，当我们想修改第3000个bit：
3000/32获得arr组的indexI
3000%32获得arr[indexI]下，[bit]想要修改的indexB
-
通过
arr[indexI] = (arr[IndexI] | (1 << indexB))进行修改1左移indexB个位置，将会变成00000010000这种形式。然后与原本的arr[IndexI]相交，对应位置将会被修改为1
可以用矩阵，将数据容量继续扩容
以Int数组为例
[1000]的数组可以代表3200个bit位
[1000][1000]的矩阵则可以代表3200*1000个bit位
布隆过滤器的实现
- 准备一个长度为m的数组，通常是bit数组
- 将指定的key用一个hash函数求出hash值
- 将hash % m 确定一个位置，并将该位置从0修改成1
- 重复用k不相关个hash函数，确定多个位置并修改成1
经过这个处理之后的数组，就是布隆过滤器。
- 当一个新的key进行查询时，也通过多次hash计算，确定是否存在于布隆过滤器
布隆过滤器的误差
由于数组长度的限制，有可能导致描黑位置过多，导致失误命中概率过高。
通过调整hash函数个个数k，以及数组长度m。可以得到不同的失误率。
布隆过滤器的优势
由于内部通过hash函数定位，最终过滤器所占内存的大小与单样本的内存大小无关。
比如一个长度为1000000的字符串，也并不需要存进数组。只需要在数组中修改k个位置即可。
布隆过滤器长度公式
[bit]的长度m，样本量n，预期失误率p，ln是自然对数
布隆过滤器hash函数个数公式
布隆过滤器真是失误率
当m和k确定之后的失误率
经典服务器抗压结构
通过对key进行hash % n 可以将读写的压力均匀的分布给三个服务器
而这种结构，当加入新的服务器或减少原有的服务器。我们需要像hashMap的自动扩容一样需要重建整个映射。
一致性哈希
经典抗压结构在扩容时，需要对数据做全量迁移，计算每一条数据的归属。
一致性哈希可以降低数据迁移的代价，同时保证负载均衡。
正常的工作流程
- 根据关键信息计算出三个负载服务器的hashCode：h1,h2,h3。
- 将三个值交由前方的前段服务器持有
- 当进行读写操作时，对key进行hash，用二分的方式寻找顺时针方向最近的负载服务器并交付。
数据迁移的流程
只需要将黑色部分数据从1号服务器迁移给4号服务器即可。
虚拟节点技术
通过将每个服务器分配N个虚拟节点映射，让整个环上的分割区域约等于平均。
