布隆过滤器vs哈希表理解
哈希表和布隆过滤器都是常用的结构
其中哈希表可以构建key-value的形式，准确查找到每个key对应的value是否存在，值是什么
而布隆过滤器则是可以快速判断一个元素是否已经存在于布隆过滤器中，不过由于哈希冲突的存在，如果布隆过滤器命中不一定代表这个元素存在于布隆过滤器中，而如果布隆过滤器没有命中，则代表这个元素一定不存在在布隆过滤器中
这两种结构在存储空间，查找效率，以及适用场景上都有不同的优劣，借助本文查找一些博客资料形成一下自己的理解
1. 哈希表也可以判断一个元素是否已经存在，从而看是否命中了，为什么还需要使用布隆过滤器？
1.1 哈希表
哈希表的优点：
- 精确查找：可以准确判断一个元素是否存在于数据集中
- 可以存储数据：将元素本身，还有元素所对应的值可以存在表中，而不是只判断是否存在
哈希表是如何实现以上两点的？用redis种的hash数据结构来进行一个解答！
哈希表是一种保存键值对的数据结构，哈希表中的每一个key都是独一无二的，程序可以根据key查找到与之关联的value，或者通过key来更新value，根据key删除整个key-value对等
优点在于，能够以O(1)的复杂度快速查询数据：将key通过hash函数的计算，就能够确定表中的位置，因为哈希表实际上就是数组，可以通过索引值快速查询到数据
但是随着数据不断增多，那么哈希冲突可能性也会更高，考虑到哈希表的特性，需要解决哈希冲突的问题，如链式哈希等方式，将具有相同哈希值的数据串起来，形成链接以便这些数据在表中仍然可以被查询到
个人在这里补充一下，哈希表解决了哈希冲突问题，而布隆过滤器只是通过多个哈希函数的方式，缓解了哈希冲突问题
1.1.1 哈希表结构设计
哈希表是一个数组dictEntry table[][]，二维的，数组的每个元素是一个指向哈希表节点的dictEntry的指针
自己想象一下这里是二维的数组，一般来说只会用到第一维，也就是想象数组的第一列，而当哈希冲突发生的时候，会开始对哈希冲突行的列进行扩充使用
每一个哈希节点不仅包含对键和值的存储，同时还有指向下一个哈希表节点的指针，这个指针可将多个哈希值相同的键值对链接起来，链式哈希解决哈希冲突
1.1.2 哈希冲突
哈希表实际上就是一个数组！数组里的每一个元素就是一个哈希桶
当一个key-value对经过hash函数计算后得到哈希值，再将哈希值%哈希表大小，就可以对应到这个key-value对应的数组元素位置，第几个哈希桶
经过上面的这种描述后，当有两个以上的key被分配到了哈希表中同一个哈希桶上时，这些key发生了冲突
1.1.3 链式哈希与rehash
被分配到同一个哈希桶上的多个节点，可以用单向链表连接起来
链式哈希的局限性很明显，随着链表的长度增加，在查询这一位置上的数据的耗时就会增加，要解决这个问题就要进行rehash
redis定义了一个dict结构体，两个哈希表！在rehash的时候就需要用上2个哈希表了
在正常服务请求阶段，插入的数据都会写到「哈希表1」，此时的「哈希表2」并没有被分配空间
数据增多，会触发rehash，分为三步操作
- 给「哈希表2」分配空间，一般会比「哈希表1」大2倍
- 将「哈希表1」的数据迁移到「哈希表2」中
- 迁移完成后，「哈希表1」的空间会被释放，并把「哈希表2」设置为哈希表1，然后在「哈希表2」新创建一个空白的哈希表，为下次rehash做准备
这个过程的问题在于，如果「哈希表1」的数据量非常大，迁移到「哈希表2」的时候，会涉及大量的数据拷贝，对redis阻塞，无法服务其他请求
1.1.4 渐进式rehash
将数据迁移的工作不再是一次性完成
- 给「哈希表2」分配空间
- 在rehash进行期间，每次哈希表元素进行新增、删除、查找、更新等操作的时候，除了执行对应操作，还会把「哈希表1」索引位置上的所有key-value迁移到「哈希表2」
- 随着客户端发起哈希表的请求数量增多，在某个时间点会把「哈希表1」的所有kv迁移到「哈希表2」，从而完成rehash
在进行渐进式 rehash 的过程中，会有两个哈希表，所以在渐进式 rehash 进行期间，哈希表元素的删除、查找、更新等操作都会在这两个哈希表进行。
比如，查找一个 key 的值的话，先会在「哈希表 1」 里面进行查找，如果没找到，就会继续到哈希表 2 里面进行找到。
另外，在渐进式 rehash 进行期间，新增一个 key-value 时，会被保存到「哈希表 2 」里面，而「哈希表 1」 则不再进行任何添加操作，这样保证了「哈希表 1 」的 key-value 数量只会减少，随着 rehash 操作的完成，最终「哈希表 1 」就会变成空表。
1.1.5 rehash触发条件
- 负载因子达到一定时候
触发 rehash 操作的条件，主要有两个：
- 当负载因子大于等于 1 ，并且 Redis 没有在执行 bgsave 命令或者 bgrewiteaof 命令，也就是没有执行 RDB 快照或没有进行 AOF 重写的时候，就会进行 rehash 操作。
- 当负载因子大于等于 5 时，此时说明哈希冲突非常严重了，不管有没有有在执行 RDB 快照或 AOF 重写，都会强制进行 rehash 操作。