• C/C++数据结构之Hash与BloomFilter详解


    平衡二叉树

    平衡二叉树查找数据采用二分查找,每次查找排除一半。平衡的目的是增删改之后,保证下次搜索能够稳定排除一半的数据。
    平衡二叉树增删改查的时间复杂度为 O ( log ⁡ 2 n ) O(\log_2n) O(log2n)。比如,100万个节点,最多比较 20 次;10 亿
    个节点,最多比较 30 次;

    平衡二叉树通过比较保证有序,通过每次排除一半的元素达到快速索引的目的。

    二分查找
    有序数组
    平衡二叉树
    平衡多路搜索树
    多层级有序链表
    调表
    红黑树
    AVL
    B树
    B+树

    散列表

    在平衡二叉树中,搜索数据时总是对key进行比较,如果在海量数据中使用这种方式,搜索效率会很低。

    散列表是一种不比较key,而是根据key计算key在表中的位置的数据结构;是key和其所在存储地址的映射关系。散列表通过此方式达到快速索引的目的。
    注意:散列表的节点中key-value是存储在一起的。

    struct node {
    void *key;
    void *val;
    struct node *next;
    };
    

    散列表的构成

    (1)hash函数
    hash函数的作用是映射,通过key找到其存储地址。
    (2)数组。
    key通过hash函数找到数组的位置,该位置就是存储value的地方。

    hash的选择

    hash的选择遵循两个原则:
    (1)计算速度快。
    (2)强随机分布(等概率、均匀的分布在整个地址空间)。
    满足这两个原则的hash有:murmurhash1、murmurhash2、murmurhash3、siphash、cityhash等。
    murmurhash1:计算速度非常快,但质量一般。
    murmurhash2:计算速度较快,质量也可以。
    murmurhash3:计算速度较慢,但质量很好。
    siphash:redis 6.0中使用,因为redis设置的key非常有规律而且字符串接近,siphash 主要解决字符串接近的强随机分布性。

    注意,hash函数可能会把两个或两个以上的不同key映射到同一地址,这种现象称为hash冲突。

    散列表操作流程

    散列表的插入操作和搜索操作都要经过hash函数找到key对应的存储地址。首先,key经过hash函数hash(key)等到一个64bit/32bit的值maddr;然后maddr对数组长度取余,得到的值就是存储节点的位置。

    指针数组
    0
    1
    2
    3
    4
    5
    6
    7
    node
    node
    node
    node
    node

    冲突

    冲突产生原因

    在数组大小不变情况下,随着数据的越来越多,必然产生冲突;而且hash是随机性的,这也可能产生冲突。
    比如把n+1个元素放入n大小的数组,势必有一个空间需要存放两个元素,这就是冲突。另外,hash是随机的,产生的数对数组长度取余很可能相同,这也会冲突。

    负载因子

    负载因子=数组存储元素的个数 / 数组长度; 负载因子用于描述冲突的激烈程度和存储的密度。负载因子越小,冲突概率越小,负载因子越大,冲突概率越大。

    冲突处理

    解决冲突的方法有很多,比较常用的有:链表法 / 拉链法、开放寻址法等。
    一般,链表法和开放寻址法适用于负载因子在合理范围内的情况,即数组存储元素的个数小于数组长度的情况。

    链表法

    链表法是常用的处理冲突的方式。通过引用链表来处理hash冲突,即将冲突元素用链表链接起来。
    但可能出现极端情况,冲突元素比较多,该冲突链表过长;这个时候可以考虑将链表转换为红黑树、最小堆;由原来链表时间复杂度 O ( n ) O(n) O(n)转换为红黑树时间复杂度 O ( log ⁡ 2 n ) O(\log_2n) O(log2n);可以采用超过 256(经验值)个节点的时候将链表结构转换为红黑树或堆结构。

    指针数组
    0
    1
    2
    3
    4
    5
    6
    7
    node
    node
    node
    node
    node

    开放寻址法

    开放寻址法将所有的元素都存放在哈希表的数组中,不使用额外的数据结构。一般使用线性探查的的思路解决:
    (1)当插入新元素时,使用hash函数在hash表中定位元素的位置;
    (2)检查数组中该槽位索引是否存在元素,如果该槽位为空,则插入数据,否则进入(3)。
    (3)在(2)检测的槽位索引上加一定步长接着检查(2);加步长有以下几种:
    ( a ) i+1,i+2,i+3,i+4,…,i+n
    ( b ) i- 1 2 1^2 12,i+ 2 2 2^2 22,i- 3 2 3^2 32,i+ 4 2 4^2 42,…
    ( c ) 双重hash
    前两种都会产生同类hash聚集,也就是近似值它的hash值也近似,那么它的数组槽位也靠近,形成 hash 聚集;第一种同类聚集冲突在前,第二种只是将聚集冲突延后; 可以使用双重哈希来解决上面出现hash聚集现象。
    比如,在.net HashTable类的hash函数Hk定义如下:
    Hk(key) = [GetHash(key) + k * (1 +(((GetHash(key) >> 5) + 1) %(hashsize – 1)))] % hashsize
    在此 (1 + (((GetHash(key) >> 5) + 1) %(hashsize – 1))) 与 hashsize互为素数(两数互为素数表示两者没有共同的质因⼦);执⾏了 hashsize 次探查后,哈希表中的每⼀个位置都有且只有⼀次被访问到,即对于给定的 key,对哈希表中的同⼀位置不会同时使⽤Hi 和 Hj;

    扩容和缩容

    以上两种解决冲突的方式都是负载因子在合理范围内。当负载因子不在合理范围内,如何处理?
    (1)当used > size,即要使用的空间大于数组的空间,这时就需要通过扩容来避免或降低冲突。扩容通常采用翻倍扩容

    (2)当used < 0.1 * size,即要使用的空间远远小于数组的空间,这时就需要缩容;缩容不能解决冲突,只能节约空间,减少内存浪费。
    (3)rehash,重新hash。因为容量发生了改变,前面解释过key在数组的位置是通过key % size的方式;所以,需要重新做key % new_size找到key的槽位,然后重新放到新的数组中去。

    扩容
    rehash
    缩容
    旧数组的key重新映射,搬到新数组中,释放旧数组的内存

    STL unordered_* 散列表实现

    在 STL 中 unordered_map、unordered_set、unordered_multimap、unordered_multiset 四个容器的底层实现都是散列表。

    STL
    红黑树
    散列表
    set
    map
    multiset
    multimap
    unorder_set
    unorder_map
    unorder_multiset
    unorder_multimap

    原理图:

    指针数组
    0
    1
    2
    3
    4
    5
    6
    7
    8
    _hash_node_base* _M_before_begin
    _hash_node_base*
    _hash_node_base*
    _hash_node_base*
    _hash_node_base*
    _hash_node_base*
    _hash_node_base*

    一般,hash table里面的槽位单独通过链表串联所属槽位的数据;STL散列表的槽位指针不再这么做,做了优化,将后面具体结点串成一个单链表,而槽位指针指向上一的结点。

    举个例子:
    现在的hash table是空的,还没有数据插入,当第一个hash(key) % array_size插入时,假设这个hash(key) % array_size=4,那么4的_hash_node_base指向头指针_M_before_begin,_M_before_begin.next=新插入的_hash_node_base;后面又来一个插入,假设hash(key) % array_size=1,那么1的_hash_node_base指向头结点_M_before_begin,_M_before_begin.next=新插入的_hash_node_base,新插入的_hash_node_base.next=4的_hash_node_base,4的槽位指针指向新插入的_hash_node_base*。
    hashtable

    布隆过滤器

    背景

    无论是红黑树、平衡二叉树、散列表,结点都是存储的key-value对。而有些场景,内存是有限的,仅需要了解key是否存在,不想知道具体内容(value)。

    这时就需要布隆过滤器。布隆过滤器是一种概率型数据结构,它的特点是高效的插入和查询,能确定某个字符串一定存在或者可能存在。
    布隆过滤器不存储具体数据,所以占用空间小,查询结果存在误差,但误差可控,同时不支持删除操作。

    (1)一个巨大的数据文件,需要知道是否存在某个key,如果把整个文件读取进行查找,这个效率就比较低。那么可以添加一个布隆过滤器,插入数据时对key做标识,查询key是否存在时直接查询布隆过滤器。
    (2)一个数据库查询,想要查询数据库中是否存在key,可以添加一个布隆过滤器,查询key时直接查询布隆过滤器,不需要IO操作,大大提升查询效率。

    构成

    布隆过滤器的原理本质上和散列表是一样的。但布隆过滤器为了节约内存,不是使用的数组,而是使用的位图。
    (1)位图
    bit的数组,实现方式有多种。

    // 例如
    vector bitmap;
    uint64_t bitmap;
    

    (2)n个hash函数

    举例:
    使用byte buf[8]构建64bit的位图,那么n=i*8+j;假设hash(key)=173,n=173%64=173&63=45,j=n%8=45%8=5,i=n/8=45/8=5。因此将(5,5)位置置 1。

    bit012345678
    0
    1
    2
    3
    4
    51
    6
    7
    8

    原理

    当一个元素加入位图时,通过k个hash函数将元素映射到位图的k个点,并把它们置1;当检索时,再通过k个hash函数运算检查位图的k个点是否都为1;如果有不为1的点,那么认为该key不存在;如果全部为1,则可能存在。

    布隆过滤器是不支持删除操作的,原因在于:在位图中每个槽位只有两种状态(0或者1),一个槽位被置为1,但不确定它被设置了多少次;也不知道被多少个key hash映射而来;以及具体被哪个hash函数映射而来。

    值得注意的是,只要有一个槽位为0,则key一定不存在;如果key映射的所有槽位都为1,不能说明一定存在,只能说明可能存在(假阳率)。

    bitmap
    0
    0
    1
    0
    0
    1
    0
    0
    1
    0
    1
    1
    hash函数
    Hash1(key)
    Hash2(key)
    Hash3(key)
    str1
    str2

    应用场景

    布隆过滤器通常用于判断某个key一定不存在的情况。同时允许判断存在时有误差的情况。
    常见处理场景:
    (1)缓存穿透的解决
    (2)热key限流

    缓存场景:为了减轻数据库(MySQL)的访问压力,在数据库(MySQL)和服务端(server)直接加入缓存用来存储热点数据。
    缓存穿透:服务端(server)请求数据时,缓存和数据库都不包含数据,最终请求压力全部涌向数据库。

    数据请求步骤:
    先访问redis,如果存在则直接返回,如果不存在则走2访问数据库;
    访问数据库,如果不存在直接返回,如果存在则将MySQL存在的key写回redis。

    key
    Yes
    No
    key
    NO
    Yes
    Server
    redis
    是否存在
    return
    MySQL
    是否存在
    key写回redis

    发生原因:黑客利用漏洞伪造数据攻击或内部业务bug造成大量重复请求不存在的数据。

    解决方案:
    (1)在redis设置键值对,依次避免访问数据库;缺点是过多会占用过多内存,可以给key设置过期expire key 600ms,停止攻击后最终由redis自动清除无用的key。
    (2)在服务端(server)存储一个布隆过滤器,将MySQL存在的key放入布隆过滤器中,布隆过滤器可以过滤一定不存在的数据。

    应用分析

    在实际应用中,该选择多少个 hash 函数?要分配多少空间的位图?预期存储多少元素?如何控制误差?
    可以使用如下公式计算:
    n = ceil(m / (-k / log(1 - exp(log§ / k))))
    p = pow(1 - exp(-k / (m / n)), k)
    m = ceil((n * log§) / log(1 / pow(2, log(2))));
    k = round((m / n) * log(2));
    其中
    n – 预期布隆过滤器中元素的个数,如上图 只有str1和str2 两元素 那么 n=2
    p – 假阳率,在0-1之间 0.000000
    m – 位图所占空间
    k – hash函数的个数

    数学公式:
    n = ⌈ m ÷ ( − k ÷ log ⁡ ( 1 − e ( log ⁡ ( p ) ÷ k ) ) ) ⌉ n=\lceil m\div(-k\div\log(1-e^{(\log(p)\div k))}) \rceil n=m÷(k÷log(1e(log(p)÷k)))⌉
    p = ( 1 − e − k ÷ ( m ÷ n ) ) k p=(1-e^{-k\div(m\div n)})^k p=(1ek÷(m÷n))k
    m = ⌈ ( n × log ⁡ ( p ) ) ÷ log ⁡ ( 1 ÷ 2 log ⁡ 2 ) ⌉ m=\lceil (n\times\log(p)) \div \log(1\div 2^{\log2} ) \rceil m=⌈(n×log(p))÷log(1÷2log2)⌉
    r o u n d ( ( m ÷ n ) ∗ log ⁡ 2 ) round((m\div n)*\log2) round((m÷n)log2)

    变量关系

    假设:
    n = 6000
    p = 0.000000001
    m = 258797 (31.59KiB)
    k = 30
    得到如下关系图:
    bloomfitter
    (1)假阳率p会随着插入元素的增多而逐渐变高。
    (2)假阳率p会随着位图所占空间的增大而减小。
    (3)假阳率p会随着hash函数个数增多,呈现快速减小后缓慢增长的趋势。hash函数个数在31时假阳率最低。

    确定n和p

    在实际使用布隆过滤器时,首先需要确定 n 和 p,通过上面的运算得出 m 和 k;推荐一个布隆过滤器计算器可以选出合适的值。

    选择hash函数

    选择一个 hash 函数,通过给 hash 传递不同的种子偏移值,采用线性探寻的方式构造多个 hash 函数;

    #define MIX_UINT64(v) ((uint32_t)((v>>32)^(v)))
    
    uint64_t hash1 = MurmurHash2_x64(key, len, Seed);
    uint64_t hash2 = MurmurHash2_x64(key, len,MIX_UINT64(hash1));
    for (i = 0; i < k; i++) // k 是hash函数的个数
    {
         Pos[i] = (hash1 + i*hash2) % m; // m 是位图的⼤⼩
    }
    

    分布式一致性hash

    背景

    假设一个服务器,只有一个缓存结点,当存储的数据越来越多时,效率就越来越低,这时就需要增加结点进行分流分压。那么如何实现优雅的扩容(数据随机、均匀分布)?首先想到使用hash方法解决,但扩容时(增加结点)会出现算法改变;比如原来有n个结点,key通过hash(key)%n确定存储在哪个结点,现在添加新的结点变成了n+1,key通过hash(key)%(n+1)寻找存储结点就会出现缓存失效。

    扩容
    扩容n=4
    缓存失效
    缓存失效
    1号结点
    2号结点
    3号结点
    0号结点
    hash(key=1)%4=1
    hash(key=2)%4=2
    hash(key=3)%4=3
    hash(key=4)%4=0
    现在n=3
    1号结点
    2号结点
    0号结点
    hash(key=1)%3=1
    hash(key=2)%3=2
    hash(key=3)%3=0
    hash(key=4)%3=1

    分布式一致性hash就解决了缓存扩容的问题。分布式一致性hash算法将hash空间组织成一个虚拟的圆环,圆环大小为 2 32 2^{32} 232
    算法为:hash(ip) % 2 32 2^{32} 232,最终会得到一个 [0, 2 32 − 1 2^{32}-1 2321] 之间的一个无符号整型,这个整数代表服务器的编号;多个服务器都通过这种方式在 hash 环上映射一个点来标识该服务器的位置;当用户操作某个 key,通过同样的算法生成一个值,沿环顺时针定位某个服务器,那么该 key 就在该服务器中。
    图片来自网络:
    hashmap

    服务器1
    key1
    服务器3
    服务器0
    key2
    服务器2

    一致性hash原理

    (1)映射空间可抽象为一个环,长度为 2 32 2^{32} 232,范围为[0, 2 32 − 1 2^{32}-1 2321],每个服务器节点根据自己的哈希值被映射到这个环上;

    (2)判断一条数据属于哪个服务器节点的方法:根据数据的哈希值,去哈希环找到第一个大于等于数据哈希值的机器(可以理解为离它最近)。如果数据的哈希值大于当前最大的机器哈希值,那么就把这个数据放在位置最靠前(哈希值最小)的机器上,因为是一个环。

    (3)为了解决实际机器过少导致的数据倾斜问题(例如目前一共3个机器,机器A、B的哈希值分别为1和2,而另一个机器C的哈希值为 2^32-1,那么大部分的数据都会被分给机器C),引入了虚拟节点概念,虚拟节点相当于真实节点的分身,一个真实节点可以有很多个虚拟节点,当数据被分配给这些虚拟节点时,本质上是分给这个真实节点的。由于数量变多了,数据分布的均衡性会有所提高;

    (4)新增节点时:例如原本的节点哈希值列表为[1,100,500,1000],新增节点800后,在501~799范围内的数据原本是分给哈希值为1000的节点的,现在要把这部分数据迁移到节点800;

    (5)删除节点:例如原本的节点哈希值列表为[1,100,500,800,1000],删除节点500后,原本范围是101~500的数据要迁移到节点800.

    应用场景

    (1)分布式缓存;将数据均衡地分散在不同的服务器当中,用来分摊缓存服务器的压力;
    (2)解决缓存服务器数量变化尽量不影响缓存失效.

    hash偏移

    hash算法得到的结果是随机的,不能保证服务器节点均匀分布在hash环上;分布不均造成请求访问不均匀,服务器承受的压力不均匀。
    图片来自网络:
    hash_offset

    服务器1
    key1
    key3
    key4
    key...
    服务器3
    服务器0
    key2
    服务器2

    为了解决实际机器过少导致的数据倾斜问题(例如目前一共3个机器,机器A、B的哈希值分别为1和2,而另一个机器C的哈希值为 2^32-1,那么大部分的数据都会被分给机器C),引入了虚拟节点概念,虚拟节点相当于真实节点的分身,一个真实节点可以有很多个虚拟节点,当数据被分配给这些虚拟节点时,本质上是分给这个真实节点的。由于数量变多了,数据分布的均衡性会有所提高;

    hash迁移

    新增节点时,例如原本的节点哈希值列表为[1,100,500,1000],新增节点800后,在501~799范围内的数据原本是分给哈希值为1000的节点的,现在要把这部分数据迁移到节点800。

    虚拟结点

    为了解决哈希偏移的问题,增加了虚拟节点的概念;理论上,哈希环上节点数越多,数据分布越均衡;为每个服务节点计算多个哈希节点(虚拟节点);通常做法
    是,hash(“IP:PORT:seqno”) % 2 32 2^{32} 232
    vnode

    添加虚拟节点解决了哈希偏移的问题,同时使hash迁移的数据量变小。

    思考

    (1)只用 2GB 内存在 20 亿个整数中找到出现次数最多的数?
    关键点,内存有限、海量数据、次数最多。要找出现次数最多,那么就一定要统计,使用key-value键值对,key保存整数,value保存出现次数。统计可以使用散列表来解决。
    对于key-value键值对,key是整数占4字节,如果按照最坏情况(即1个整数出现20 亿次),value可以使用uint32存储(uint32可达21亿多,刚好能存储下20亿),uint32也是占4字节;因此一个key-value对占8个字节。如果要在内存中处理20亿个数据就需要 2000000000 × 8 = 16 G B 2000000000 \times 8=16 GB 2000000000×8=16GB内存,超出2GB内存的限制。
    要在有限内存里处理,可以采用拆分的思维,将20亿拆分成若干等份。那么采用什么策略来拆分?首先要清楚,20亿的数据是散列分布的,不能采用等分的方式,我们的目的要把相同的整数放在同一个文件中,hash函数可以实现这个目的(相同的key经过hash得到的值总是相同)。
    一个hash函数两个用途,一方面是对数据拆分将相同整数放入同一个文件或等份,另一方面将其应用到散列表中(散列表的存储数据取余)。hash函数具有强随机性,数据属于海量数据,那么数据拆分多少份?可以计算最差情况需要拆分多少份和最好的情况需要拆分多少份,如果随机性不能达到预期,再增加份数。
    比如,将20亿拆分为10份(如果不能达到预期的随机性再增大),平均的情况是每份2亿,具体情况再具体调整。

    key
    key
    拆分
    0
    1
    2
    3
    4
    5
    6
    7
    8
    9
    20 亿个整数
    hash(key) % 10
    hash(key) % array_size
    散列表

    总结

    平衡二叉树通过比较,保证结构有序,从而提升搜索效率,稳定时间复杂度是 O ( log ⁡ 2 n ) O(\log_2n) O(log2n);而散列表是通过key与存储位置的映射关系来提高搜索效率,整个散列表是无序的。

    散列表的组成主要有:hash函数、数组、运算流程(算法是hash(key) % array_size)。

    散列表hash函数的作用是建立映射关系;选择hash函数要满足计算速度快、强随机分布的要求,比如murmurhash2、siphash、cityhash等使用比较广泛的hash算法。

    解决hash冲突的方法有链表法、开放寻址法、扩容等;链表法中如果槽位的链表很长(超过256个元素),可以转换为红黑树或最小堆的数据结构,将时间复杂度由O(n)变为 O ( l o g 2 n ) O(log_2n) O(log2n)。扩容、缩容后都需要重新hash,即重新映射。

    散列表的操作流程都是需要经过同样的运算(映射),找到存储位置再插入。

    STL的散列表实现中,为了实现迭代器,将后面具体结点串成一个单链表。

    布隆过滤器由位图和n个hash函数构成。布隆过滤器的操作是一个key经过多个hash函数,然后对位图大小进行取余等到多个槽位并对应置为1。判断时只要有一个槽位为0就一定不存在该key。
    布隆过滤器能确定一个key一定不存在,不能判断key一定存在,但可控假阳率确定存在。

    布隆过滤器不支持删除操作,可以通过两个布隆过滤器解决(依然存在假阳率,但会低一些),添加放在第一个布隆过滤器,删除放在第二个布隆过滤器。即要判断key是否存在,首先检查第二个布隆过滤器是否删除过,如果删除过就往第一个布隆过滤器插入。

    布隆过滤器根据n和p算出m和k,hash函数个数是利用开放寻址法来计算的。

    在大数据中,涉及到大文件或海量数据的,解决方案都是通过hash将大文件拆分为小文件;涉及单台机器无法承受或处理不过来的问题,解决方案都是通过hash分流到多台机器;选择hash的原因是利用其强随机分布的特性,以及把相同的数据分配到相同的位置。

    分布式一致性hash算法通过固定算法,改变查找结点的映射关系,数据迁移,避免缓存失效,解决分布式扩容的问题;通过虚拟节点的方式保证数据均衡。
    在这里插入图片描述

  • 相关阅读:
    第一届全国高校将计算机技能大赛知识点整理
    ADS村田电感.mod(spice netlist文件)和.s2p模型导入与区别
    MySQL数据库基础知识要点总结
    C++与C编译后符号表对比(一百九十二)
    3、宽带对称式高回退Doherty放大器ADS仿真(带版图)
    2023年高教社杯数学建模国赛C题详细版思路
    python如何与前端交互
    LSM树原理详解
    SpringCloud: RestTemplate 带header发送post请求
    HTB_Start Point_Tier2——Oopsie
  • 原文地址:https://blog.csdn.net/Long_xu/article/details/126906014