hash与bloomfilter

,

hash与bloomfilter

hash冲突的处理

链表法：

引用链表来处理哈希冲突；也就是将冲突元素用链表链接起来；这也是常用的处理冲突的方式；但是可能出现一种极端情 况，冲突元素比较多，该冲突链表过长，这个时候可以将这个链表转换为红黑树、最小堆；由原来链表时间复杂度转 换为红黑树时间复杂度 ；那么判断该链表过长的依据是多少？可以采用超过 256（经验值）个节点的时候将链表结构转换为红黑树或堆结构

开放寻址法:

将所有的元素都存放在哈希表的数组中，不使用额外的数据结构；一般使用线性探查的思路解决；

  1. 当插入新元素的时，使用哈希函数在哈希表中定位元素位置

  2. 检查数组中该槽位索引是否存在元素。如果该槽位为空，则 插入，否则3；

  3. 在 2 检测的槽位索引上加一定步长接着检查2； 加一定步长 分为以下几种：

    • i+1,i+2,i+3,i+4, … ,i+n
    • i-1^2 , i+2^2 ,i-3^2 ,1+4^2 , …

    这两种都会导致同类 hash 聚集；也就是近似值它的hash值也近似，那么它的数组槽 位也靠近，形成 hash 聚集；第一种同类聚集冲突在前， 第二种只是将聚集冲突延后； 另外还可以使用双重哈希来解决上面出现hash聚集现象：

当负载因子不在合理范围如：userd / size > 0.9 userd /size < 0.1 要进行适当的扩容或缩容，在进行完扩容或缩容后要进行rehash

布隆过滤器

有些时候，由于内粗是有限的，只想确定key是否存在，而关心value的内容，这样就可以使用bloom_filter，布隆过滤器，由位图实现

原理

当一个元素加入位图时，通过 k 个 hash 函数将这个元素映射到位图的 k 个点，并把它们置为 1；当检索时，再通过 k 个 hash 函数运算检测位图的 k 个点是否都为 1；如果有不为 1 的点，那么认为该 key 不存在；如果全部为 1，则可能存在，当一个key不存在时是可以通过布隆过滤器确认的

在位图中每个槽位只有两种状态（0 或者 1），一个槽位被 设置为 1 状态，但不确定它被设置了多少次；也就是不知道被多少个 key 哈希映射而来以及是被具体哪个 hash 函数映射而来，所以布隆过滤器不支持删除操作

在实际应用中，该选择多少个 hash 函数？要分配多少空间的位 图？预期存储多少元素？如何控制误差？

n – 预期布隆过滤器中元素的个数

p – 假阳率，在0-1之间 0.000000

m – 位图所占空间

k – hash函数的个数

公式如下：
n = ceil(m / (-k / log(1 - exp(log(p) / k))))
p = pow(1 - exp(-k / (m / n)), k)
m = ceil((n * log(p)) / log(1 / pow(2, log(2))));
k = round((m / n) * log(2));

常通过Bloom filter calculator (hur.st)站点，输入n 和 p 计算得到所需要的bit位和哈希函数的数量

如何只用2G内存在20亿整数中寻找出现最多的数？

首先想到散列表，存储k v键值对，v的最大值为20亿，故uint32可以满足，故一个kv占字节，这里有20亿个，故占用16GB，明显超出2G，想办法将20亿整数拆分到若干个文件中，当然不能盲目拆分，要将相同的值放到同一个文件中，可以使用hash函数来解决这个问题(相同的值经过同一个hash函数会得到相同的结果)，将hash函数的结果对文件数取余，存放到对应的文件中

大文件可以用hash拆为小文件

单台机器无法解决，通过hash分流到多台机器

分布式一致性 hash

问题：

在主服务器从数据缓存服务器中请求数据时，往往根据数据的key求出的hash值与服务器的个数取余，以此来找到对应的服务器，当扩充数据缓存服务器时，就出现了大问题，由于服务器增加了故模数要变化，就导致对应的key找不到正确的数据服务器

解决：

分布式一致性 hash 算法将哈希空间组织成一个虚拟的圆环，圆 环的大小是 ；

算法为：hash(ip) ，最终会得到一个 [0, ] 之间的一个无符号整型，这个整数代表服务器的编号；多个服务器都通过这种方式在 hash 环上映射一个点来标识该服务器的位置；当用户操作某个 key，通过同样的算法生成一个值，沿环顺时针定位某个服务器，那么该 key 就在该服务器中；

此时有三台数据服务器，以及四个数据，k1 -> 10.0.0.2 k2->10.0.0.3 k3 k4 -> 10.0.0.1

当增加一个服务器时

此时寻找 k3 会到 10.0.0.5 中寻找，但是k3存储在 10.0.0.1 中，这就造成了局部失效，虽然无法根治问题，但是只是局部失效，原方法会造成大面积的数据失效，为了解决数据失效，要进行部分的数据迁移，即：将hash后结果落在 10.0.0.3 到10.0.0.5 服务器对应hash值之间的 key 存储到新加的服务器中，并在原服务器中删除，这个hash值直接在原服务器中寻找就好了

虚拟节点

当我们的服务器过少时，节点无法均匀的分散在圆环上，这样会导致某一个服务器上存放了大量数据

为了解决这种问题，我们采用虚拟节点，即在对应的ip：port后添加 : 编号,编号从 1 - 255 ，这样一个服务器就产生了255个节点，使得节点的分布根据随机性，在数据存储时，只需将本应该存储在对应虚拟节点的数据存储在其本身节点上即可，在进行数据查找时，找到对应的ip:port:编号，只需将编号截取掉就是存放数据的服务器，这样解决了数据分配不均问题也使得在扩容时进行hash迁移的数据减少了