少部分网站ie打不开这些网站域名ping不通,在线小游戏,wordpress微信机器人下载地址,如何选择做pc端网站文章目录 hash表与布隆过滤器1. hash函数2. 选择hash函数3. 散列冲突3.1 负载因子3.2 冲突解决3. STL中的散列表 4. 布隆过滤器4.1 背景1. 应用场景2. 常见的处理场景#xff1a; 4.2 布隆过滤器构成4.3 原理4.4 应用分析4.5 要点 5. 分布式一致性hash5.1 缓存失效问题 6. 大数… 文章目录 hash表与布隆过滤器1. hash函数2. 选择hash函数3. 散列冲突3.1 负载因子3.2 冲突解决3. STL中的散列表 4. 布隆过滤器4.1 背景1. 应用场景2. 常见的处理场景 4.2 布隆过滤器构成4.3 原理4.4 应用分析4.5 要点 5. 分布式一致性hash5.1 缓存失效问题 6. 大数据相关的面试题学习参考 hash表与布隆过滤器 本文讲述了hash表的原理与实现、hash冲突及解决方法、基于位图和hash函数实现的布隆过滤器、以及用于负载均衡的分布式一致性hash等。 1. hash函数
用来求hash值的一种映射函数hash函数可能会把两个或者两个以上的不同key映射到同一地址这种情况称之为冲突或者hash碰撞
与平衡二叉树比较
平衡二叉树利用二分查找的思维通过每次比较排除一半元素来达到快速查找的目的。时间复杂度为O(logn)。10万结点比较20次10亿结点比较30次即可。散列表通过简历key值到索引位置的映射关系来实现快速查找实现这种映射的函数叫做哈希函数或者散列函数平均时间复杂度为O(1)。
2. 选择hash函数
计算速度快强随机分布等概率、均匀地分布在整个地址空间murmurhash1, murmurhash2, murmurhash3, siphash(redis6.0当中使用也是rust等大多数语言选用的hash算法来实现hashmap)cityhash都具备强随机分布性。siphash主要解决相近的字符串的随机分布性。murmurhash2是使用最频繁的hash算法。
测试地址https://github.com/aappleby/smhasher
3. 散列冲突 不同的key可能会被映射到同一个地址这种情况就叫做散列冲突。 3.1 负载因子
负载因子是指哈希表中已存储元素的数量与哈希表中桶bucket数量之间的比例能够描述存储密度或者散列冲突的激烈程度。
3.2 冲突解决
如果负载因子在合理范围内 拉链法 将冲突元素用一个链表链接起来查找时在链表内进行线性查找。 这样可能出现一种极端情况当冲突的元素比较多冲突链表过长时会显著影响查询性能这时可以将这个链表转换为红黑树、最小堆。可以采用超过256经验值个结点的时候将链表结构转换为红黑树或者堆结构。 开放寻址法 线性探查法有hash聚集也叫主聚集问题即当多个元素发生hash冲突后会被集中插入到hash表中的相邻位置从而导致后续的冲突更容易发生在这些已占用的区域形成聚集效应。这样新插入的元素需要花费更多的时间探查空闲位置最终导致插入和查找的效率下降。二次探查法使用非线性方式进行探查次聚集问题即由于探查模式相同而导致不同的键分布在相邻的位置上。再散列法相比线性探查法就能够使插入的结点分布更加均匀次聚集问题。
如果负载因子不在合理范围内
扩容翻倍扩容缩容
然后进行rehash
3. STL中的散列表
unordered_map, unordered_set, unordered_multimap, unordered_multiset STL中的hash表采用类似拉链法的方法解决散列冲突。不同的是为了实现迭代器STL中会将每个桶对应的链表串连起来这样所有的键值对就被组织成了一个单链表方便迭代器的实现。这种情况下为了实现头插法每个桶中保存的是上一个拉链的尾结点。
以下是STL中插入一个结点时的代码实现每个桶中的指针指向的的是另一个桶中的最后一个结点。 if (_M_buckets[__bkt]){// Bucket is not empty, we just need to insert the new node// after the bucket before begin.__node-_M_nxt _M_buckets[__bkt]-_M_nxt;_M_buckets[__bkt]-_M_nxt __node;}
else
{// The bucket is empty, the new node is inserted at the// beginning of the singly-linked list and the bucket will// contain _M_before_begin pointer.__node-_M_nxt _M_before_begin._M_nxt;_M_before_begin._M_nxt __node;if (__node-_M_nxt)// We must update former begin bucket that is pointing to// _M_before_begin._M_buckets[_M_bucket_index(__node-_M_next())] __node;_M_buckets[__bkt] _M_before_begin;
}4. 布隆过滤器 布隆过滤器Bloom Filter是一种基于哈希函数和哈希表实现的空间效率非常高的概率型数据结构用于测试一个元素是否是一个集合的成员。它有一个重要的特点可以判断元素是否属于某个集合但不能确定元素不属于该集合。简单来说布隆过滤器允许有一定的误判率但不会漏判。 4.1 背景
1. 应用场景 内存有限只想确定某个key是否存在不想知道具体内容。 布隆过滤器通常用于判断某个key一定不存在的场景同时允许判断存在时由误差的情况。
过滤对不存在的值的查询
某个文件如果要查询其中某条记录可以先通过布隆过滤器判断该记录是否存在。某个数据库在执行查询之前可以先通过布隆过滤器判断目标是否存在。
2. 常见的处理场景
缓存穿透 缓存穿透的概念 缓存穿透是指当查询的数据既不在缓存中也不在数据库中时缓存系统没有对这些无效请求进行有效过滤导致请求直接穿透缓存频繁访问数据库从而给数据库带来巨大的压力。这种情况通常出现在分布式系统中特别是在使用缓存如 Redis、Memcached来优化数据访问的场景。 缓存穿透的成因
恶意攻击攻击者通过大量查询不存在的数据绕过缓存系统直接将请求压向数据库。这种行为可能会使数据库负载过大影响系统性能。自然请求如果系统没有针对查询条件做有效过滤用户可能请求不存在的数据如查询一个从未有过的ID也会直接穿透缓存访问数据库。
缓存穿透的解决
缓存空值当某个键查询不到数据时可以将空结果也存入缓存并设置一个较短的过期时间。这样即使再次查询同样不存在的键也会直接返回缓存中的空值避免穿透到数据库。布隆过滤器使用布隆过滤器对所有可能存在的数据进行预先判断。在访问缓存之前首先通过布隆过滤器判断查询的键是否可能存在。如果布隆过滤器判断该数据不可能存在则直接返回空值避免查询数据库。
总结 缓存穿透是缓存系统中的一个常见问题主要是由于缓存没有有效过滤无效请求导致数据库承受过大的负载。通过缓存空值、使用布隆过滤器、参数校验等方法可以有效减少缓存穿透提升系统整体性能。 热key限流
热key 热Key指的是在缓存中某些特定键被大量并发请求访问的现象。因为请求集中于少数几个Key缓存服务器的负载会非常高当缓存失效时可能会导致大量请求穿透到数据库从而引发更大的压力甚至导致数据库宕机。 热Key的影响
缓存节点压力集中缓存系统是分布式的但由于热Key的访问量远超其他Key某些缓存节点可能会成为性能瓶颈导致这些节点比其他节点负载严重失衡。缓存失效冲击数据库在缓存失效时所有的请求瞬间落到数据库数据库处理不过来可能会导致整个系统崩溃。
热key限流策略 请求合并Batching当大量请求访问某个热Key且缓存过期时可以使用请求合并策略只让第一个请求去加载数据其他请求等待第一个请求的结果。这种方式可以有效避免瞬间大量请求同时去查询数据库。 限流保护对于访问量过高的Key可以对其进行限流控制每秒对该Key的最大请求次数令牌桶算法和漏桶算法常被用于限流实现。 多副本缓存在不同的缓存节点上放置同一个热Key的数据这样可以将访问压力分散到多个缓存节点上。可以通过一致性哈希算法和副本策略来实现。 数据预热在某些特定场景中如系统重启、缓存失效后可以提前预加载一些热点数据到缓存中避免缓存初始化时发生大量请求直接穿透到数据库。 动态调整TTL对于热Key可以设置相对较长的缓存过期时间TTL这样可以避免频繁的缓存失效和更新。甚至可以根据热Key的访问频率动态调整其TTL使得热Key在高峰期保持长时间不失效。 降级策略在极端情况下可以采用降级策略对于热Key的请求进行降级处理例如返回默认值或静态页面确保系统的可用性不受单个热Key的影响。当缓存和数据库压力都很大时可以设置简单的降级逻辑避免系统崩溃。
总结 热Key限流是一种应对高频访问缓存键的策略主要目的是为了避免缓存过载和缓存失效后对数据库的冲击。常见的限流措施包括请求合并、限流保护、多副本缓存、数据预热和分级缓存等这些方法能够有效减轻系统负担保证系统的稳定性和高可用性。 4.2 布隆过滤器构成
布隆过滤器由一个位示图和k个哈希函数构成。位图的大小m和哈希函数的个数k由预期存储的最大元素数和最大假阳率决定。
位图 n个hash函数
4.3 原理 如何判断某个key不存在 bitmap[hash(key) % bit_size] 0 ? 只要一个位置为0就说明不存在。 如果判断某个key存在 无法判断某个key一定存在只能判断某个key一定不存在。 布隆过滤器不支持删除操作 bitmap中的一个位可能对应多个key 假阳率 布隆过滤器判断一个key存在但实际上不存在的情况。
4.4 应用分析
n预期存入的元素个数p最大的假阳率即判断hash值对应的位置都为1判断为存在而实际不存在的情况占比m位图的大小khash函数的个数
从n和p计算m和khttps://hur.st/bloomfilter/
结论当k31时假阳率hash冲突率是最低的。
4.5 要点 能确定一个key一定不存在可控假阳率确定存在 不能删除 先根据n和p算出m和k
5. 分布式一致性hash 一致性哈希的核心思想是通过将数据和节点映射到一个环形的哈希空间中。每个数据和节点都通过哈希函数映射到这个空间然后通过哈希值来确定数据与节点的对应关系。 5.1 缓存失效问题
假设要对请求做负载均衡原理是通过hash函数将请求的key值映射到一台缓存服务器中因为hash值的分布是均匀的所以每台服务器的负载应该也是均匀的。但是当服务器的数量发生变化时就会导致所有请求的映射关系都被破坏所有服务器中的缓存全部失效。 解决办法
引入哈希环将数据和服务器结点都映射到该环上距离数据顺时针方向上最近的服务器结点保存该节点的缓存。
固定算法 hash(key) % 2 ^ 32 indexhash迁移改变节点的映射关系解决大面积缓存失效变为局部缓存失效增加虚拟结点使迁移数据量减少
如图所示在哈希环上每个数据被映射到顺时针方向距离其最近的服务器结点。 hash偏移
该问题是指当服务器结点较少时可能服务器结点的间隔十分不均匀导致服务器负载不均衡。
如图所示s1服务器结点负载相对过大。
解决办法
增加虚拟结点即一台服务器可以对应多个服务器结点这样就增加了总的服务器结点数量使各个服务器分布的更加均匀。
6. 大数据相关的面试题 题目 只用2G内存找到20亿个整数中出现次数最多的数
思路将大文件用hash拆成小文件确保相同得key值被放入同一个文件映射并且每个每个文件中得数据量大致相同利用其强随机特性。单台机器通过hash分流到多台机器
学习参考
学习更多相关知识请参考零声 github。
