婚纱摄影在哪个网站找,什么网站是做家教的,保定学校网站建设,天津专业网站设计背景在使⽤word⽂档时#xff0c;word如何判断某个单词是否拼写正确#xff1f;⽹络爬⾍程序#xff0c;怎么让它不去爬相同的url⻚⾯#xff1f;垃圾邮件(短信)过滤算法如何设计#xff1f;公安办案时#xff0c;如何判断某嫌疑⼈是否在⽹逃名单中#xff1f;缓存穿透问…背景在使⽤word⽂档时word如何判断某个单词是否拼写正确⽹络爬⾍程序怎么让它不去爬相同的url⻚⾯垃圾邮件(短信)过滤算法如何设计公安办案时如何判断某嫌疑⼈是否在⽹逃名单中缓存穿透问题如何解决先来看一个场景假如我们的数据库使用的是 mysql缓存使用 redis。serverredismysql数据读取步骤是这样的先访问 redis 如果数据存在直接返回如果不存在则进行步骤 2访问 mysql 如果数据不存在直接返回如果存在则进行步骤 3将 mysql 中存在的 key 写回 redis出现的问题 如果 redis 和 mysql 中都没有相应的数据此时又有大量的该数据的请求(伪造数据攻击)最终的压力还是会全部涌向 mysql。这就是所谓的 缓存穿透。解决方案在 redis 端设置 键值对以避免访问 mysql。当然缺点是如果 过多时会占用过多的内存。我们可以给 key 设置过期时间比如 exoire key 600ms 停止攻击后最终由 redis 自动清除这些无用的 key ;在 server 端设置一个布隆过滤器将 mysql 中包含的 key 放入布隆过滤器中布隆过滤器能过滤一定不存在的数据。布隆过滤器假设我么你现在提出一个需求从海量数据中查询某字符串是否存在。在 c 中我们首先想到的应该是使用 STL 中的 set 或者 map。set 和 mapc 标准库(STL)中的 set 和 map 结构都是采⽤红⿊树实现的它增删改查的时间复杂度是:o(log2n)o(log_{2}n)o(log2n)对于严格平衡⼆叉搜索树(AVL)100w 条数据组成的红⿊树只需要⽐较20次就能找到该值对于10亿条数据只需要⽐较30次就能找到该数据也就是查找次数跟树的⾼度是⼀致的对于红⿊树来说平衡的是⿊节点⾼度所以研究⽐较次数需要考虑树的⾼度差最好情况某条树链路全是⿊节点假设此时⾼度为 h1最差情况某条树链路全是⿊红节点间隔那么此时树⾼度为 2*h1;在红⿊树中每⼀个节点都存储 key 和 val 字段key 是⽤来做⽐较的字段红⿊树并没有要求 key 字段唯⼀在 set 和 map 实现过程中限制了 key 字段唯⼀。另外 set 和 map 的关键区别是 set 不存储 val 字段优点存储效率⾼访问速度⾼效缺点对于数据量⼤且查询字符串⽐较⻓且查询字符串相似时将会是噩梦unordered_mapc 标准库(STL)中的 unordered_map 是采⽤ hashtable 实现的构成数组 hash 函数它是将字符串通过 hash 函数⽣成⼀个整数再映射到数组当中它增删改查的时间复杂度是 o(1);hash 函数的作⽤避免插⼊的时候字符串的⽐较hash函数计算出来的值通过对数组⻓度的取模能随机分布在数组当中hash 函数⼀般返回的是 64 位整数将多个⼤数映射到⼀个⼩数组中必然会产⽣冲突如何选取 hash 函数选取标准选取计算速度快哈希相似字符串能保持强随机分布性(防碰撞)murmurhash1murmurhash2murmurhash3siphash( redis6.0 当中使⽤rust 等⼤多数语⾔选⽤的 hash 算法来实现 hashmap)cityhash 都具备强随机分布性测试地址如下https://github.com/aappleby/smhasher负载因⼦数组存储元素的个数/数组⻓度负载因⼦越⼩冲突越⼩负载因⼦越⼤冲突越⼤hash冲突解决⽅案链表法引⼊链表来处理哈希冲突也就是将冲突元素⽤链表链接起来这也是常⽤的处理冲突的⽅式但是可能出现⼀种极端情况冲突元素⽐较多该冲突链表过⻓这个时候可以将这个链表转换为红⿊树由原来链表时间复杂度 o(n) 转换为红⿊树时间复杂度 那么判断该链表过⻓的依据是多少可以采⽤超过256(经验值)个节点的时候将链表结构转换为红⿊树结构开放寻址法将所有的元素都存放在哈希表的数组中不使⽤额外的数据结构⼀般使⽤线性探查的思路解决当插⼊新元素的时使⽤哈希函数在哈希表中定位元素位置检查数组中该槽位索引是否存在元素。如果该槽位为空则插⼊否则进行第 3 步在第 2 步检测的槽位索引上加⼀定步⻓接着检查第 2 步加⼀定步⻓分为以下⼏种i1,i2,i3,i4 ... ini- ,i ,i- ,1 ...这两种都会导致同类 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。具体原理https://www.cnblogs.com/organic/p/6283476.html同样的 hashtable 中节点存储了 key 和 valhashtable 并没有要求 key 的⼤⼩顺序我们同样可以修改代码让插⼊存在的数据变成修改操作优点访问速度更快不需要进⾏字符串⽐较缺点需要引⼊策略避免冲突存储效率不⾼空间换时间总结红⿊树和 hashtable 都不能解决海量数据问题它们都需要存储具体字符串如果数据量⼤提供不了⼏百 G 的内存所以需要尝试探寻不存储 key 的⽅案并且拥有 hashtable 的优点(不需要⽐较字符串)布隆过滤器布隆过滤器是⼀种概率型数据结构它的特点是⾼效的插⼊和查询能明确告知某个字符串⼀定不存在或者可能存在相⽐传统的查询结构(例如hashsetmap等数据结构)更加⾼效占⽤空间更⼩但是其缺点是它返回的结果是概率性的也就是说结果存在误差的虽然这个误差是可控的同时它不⽀持删除操作组成位图(bit 数组) n 个 hash 函数原理当⼀个元素加⼊位图时通过 k 个 hash 函数将这个元素映射到位图的 k 个点并把它们置为 1当检索时再通过 k 个 hash 函数运算检测位图的 k 个点是否都为 1如果有不为 1 的点那么认为不存在如果全部为1则可能存在(存在误差)[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ahhhbjn3-1610794049644)(原理.png)]在位图中每个槽位只有两种状态(0 或者 1)⼀个槽位被设置为 1 状态但不明确它被设置了多少次也就是不知道被多少个 str1 哈希映射以及是被哪个 hash 函数映射过来的所以不⽀持删除操作在实际应⽤过程中布隆过滤器该如何使⽤要选择多少个 hash 函数要分配多少空间的位图存储多少元素另外如何控制假阳率(布隆过滤器能明确⼀定不存在不能明确⼀定存在那么存在的判断是有误差的假阳率就是错误判断存在的概率)n -- 布隆过滤器中元素的个数如上图 只有str1和str2 两个元素 那么 n2p -- 假阳率在0-1之间 0.000000m -- 位图所占空间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));假定我们选取这四个值为n 4000p 0.000000001m 172532k 30四个值的关系在实际应⽤中我们确定 n 和 p通过上⾯的计算算出 m 和 k也可以在⽹站上选取合适的值https://hur.st/bloomfilter已知 k如何选择 k 个 hash 函数// 采⽤⼀个hash函数给hash传不同的种⼦偏移值// #define MIX_UINT64(v) ((uint32_t)((v32)^(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 是位图的⼤⼩}// 通过这种⽅式来模拟 k 个hash函数 跟我们前⾯开放寻址法 双重hash是⼀样的思路
