企业官网建设流程全解析

1 背景

• 使用word文档时，word如何判断某个单词是否拼写正确？
• 网络爬虫程序，怎么让它不去爬相同的url页面？
• 垃圾邮件过滤算法如何设计？
• 公安办案时，如何判断某嫌疑人是否在网逃名单中？
• 缓存穿透问题如何解决？

平衡二叉树

• 增删改查时间复杂度为 O(logn)；
• 平衡的目的是增删改后，保证下次搜索能稳定排除一半的数据；
• O(logn)的直观理解：100万个节点，最多比较20次；10亿个节点，最多比较 30次；

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

2 散列表（hash表）

而散列表，则是通过key进行一定的处理（哈希函数处理对数组长度取余）后，在对应的数组的索引位置存储。

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

2.1 hash函数

映射函数 Hash(key)=addr；hash 函数可能会把两个或两个以上的不同 key 映射到同一地址，这种情况称之为冲突（或者hash 碰撞）；

hash函数的选择

• 计算速度快
• 强随机分布（等概率、均匀地分布在整个地址空间）
• murmurhash1，murmurhash2（使用最多），murmurhash3，siphash（ redis6.0 当中使用，rust 等大多数语言选用的 hash 算法来实现 hashmap），cityhash 都具备强随机分布性；测试地址如下：https://github.com/aappleby/smhasher
• siphash 主要解决字符串接近的强随机分布性

负载因子

• 数组存储元素的个数 / 数组1长度；用来形容散列表的存储密度；负载因子越小，冲突概率越小，负载因子越大，冲突概率越大；

2.2 冲突处理

链表法

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

开放寻址法

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

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聚集现象，下面要讲的布隆过滤器也是使用双重哈希的方式解决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；

2.3 stl中实现的散列表结构

在 STL 中 unordered_map、unordered_set、 unordered_multimap、unordered_multiset 四兄弟底层实现都是散列表；

stl实现的散列表对原始的散列表进行了优化，如上图所示。原因是stl需要对迭代器进行封装，即需要方便寻找某个节点所在的位置。所以有一个_M_before_begin的节点作为头节点将所有节点串成一个链表的结构。而数值中的索引指向的不是所在所以位置的第一个节点，而是指向上一个节点所存储索引位置的最后一个节点。插入节点时类似一种头插法的感觉。

3 布隆过滤器

3.1 背景

上面所讲的数据结构如红黑树、散列表、B树和B+树都是采用的存储k和v数据。但是实际上有时候我们并不需要知道key具体对应的value的值，我们只需要知道对应的key是否在某个容器中。那么这时候就可以使用布隆过滤器

布隆过滤器是一种概率型数据结构，它的特点是高效地插入和查询，能确定某个字符串一定不存在或者可能存在；布隆过滤器不存储具体数据，所以占用空间小，查询结果存在误差，但是误差可控，同时不支持删除操作；例如，我们需要在mysql数据库中插叙某个key对应的值，直接查询需要经过网络交互和查找过程，我们可以先在服务器部署一个布隆过滤器，先判断是否存在于mysql中再进行查询。

3.2 构成

如上图所示，我们可以采用byte buf[8]数据来表示64bit的位图（1byte = 8bit），然后通过对key进行hash计算出一个值映射到位图中，在对应索引位置中置为1。

3.3 原理

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

• 在位图中每个槽位只有两种状态（0 或者 1），一个槽位被设置为 1 状态，但不确定它被设置了多少次；也就是不知道 被多少个 key 哈希映射而来以及是被具体哪个 hash 函数映射而来；
• 只要一个索引位为0，就一定不存在；如果都为1是否一定存在？不一定，可控的（假阳率）

3.4 应用分析

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

n -- 预期布隆过滤器中元素的个数，如上图 只有str1和str2 两个元素 那么 n=2 p -- 假阳率，在0-1之间 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可以使用这个网址通过n和p计算对应的m和k的值

上图引申出一个面试题，在很多的hash函数中经常出现‘31’这个数字，为什么？原因可以通过上面这个图看出来，其实时一个经验值，当k（hash函数个数）为31时，假阳率或者冲突概率最低。

那k个hash函数如何做到几十个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 是位图的⼤⼩ }

3.5 应用场景

布隆过滤器通常用于判断某个 key 一定不存在的场景，同时允许判断存在时有误差的情况；
常见处理场景：① 缓存穿透的解决；② 热 key 限流；

• 描述缓存场景，为了减轻数据库（mysql）的访问压力，在server 端与数据库（mysql）之间加入缓存redis用来存储热点数据；
• 描述缓存穿透，server端请求数据时，缓存和数据库都不包含该数据，最终请求压力全部涌向数据库；
• 数据请求步骤，如图中 2 所示；
• 发生原因：黑客利用漏洞伪造数据攻击或者内部业务 bug 造成大量重复请求不存在的数据；
• 解决方案：如图中 3 所示；

拓展知识：

缓存击穿 vs 缓存穿透 vs 缓存雪崩

• 缓存穿透：查询不存在的数据，缓存和数据库均无记录（恶意攻击）。
• 缓存雪崩：大量缓存同时失效，导致请求批量击穿到数据库。
• 缓存击穿：单个热点数据失效，引发集中式高并发请求。某个热点数据在缓存过期或失效的瞬间，大量并发请求直接穿透缓存层，直接访问数据库

对应解决方案

• 缓存穿透：可以使用布隆过滤器或者缓存空对象的方式解决。
• 缓存雪崩：
  • 缓存数据过期时间分散：在设置缓存过期时间时，增加随机值（如base_time + random_delta），避免同时失效。
  • 多级缓存架构：使用本地缓存（如 Guava Cache）作为一级缓存，Redis 作为二级缓存，分散压力。
  • 热点数据永不过期：对极热点数据设置永不过期，通过异步线程主动更新。
  • 限流与降级：使用熔断器（如 Hystrix）限制并发请求量，或直接返回默认值
• 缓存击穿：
  • 使用互斥锁，在缓存失效时，只允许一个线程去重建缓存，其他线程等待，实现过程：
    • 请求发现缓存未命中时，尝试获取分布式锁（如 Redis 的SETNX）。
    • 获取锁成功的线程查询数据库并重建缓存。
    • 其他线程等待锁释放后，直接从缓存读取数据。

Q：在2GB 内存限制下，从20 亿个整数中找到出现次数最多的数

4 分布式一致性hash

4.1 背景

分布式一致性hash解决的是多个节点分布式缓存扩容的场景，比如之前所学的redis的cluster集群一样。数据库的数据不会存储在一个节点中，而是采用主从节点进行存储。

如上图所示，一个server端和三个redis端的节点，三个节点对应着不同的机器。首先在server端对key进行运算确定存储到哪个节点中进行分布式的存储。但是当增加一个节点后，就会有一个问题，那么我们hash算法就会发生改变。原来对3取余就会变成对4取余。那么就会出现缓存失效的问题，即扩容后算法改变后，原来存储的某些索引再次查询时就找不到了。

于是就引出了分布式一致性hash的解决方法，先固定算法。分布式一致性 hash 算法将哈希空间组织成一个虚拟的圆环，圆环的大小是2^32；算法为：hash(ip) %2^32，最终会得到一个 [0,2^32-1 ] 之间的一个无符号整型，这个整数代表服务器的编号；多个服务器都通过这种方式在 hash 环上映射一个点来标识该服务器的位置；当用户操作某个 key，通过同样的算法生成一个值，沿环顺时针定位某个服务器，那么该 key 就在该服务器中;

但是此时如果进行扩容仍然会出现缓存失效的问题，如下图所示，即原来用户2的数据时存储在服务器2中的，扩容后我们查询时会在服务器3进行查询，很明显是不可能查询到数据的，因此出现缓存失效。但是这个缓存失效时小部分的缓存失效，只是在用户2和服务器3之间的数据失效，只需要将这一部分的数据进行迁移即可。

4.2 hash偏移

我们知道hash算法的强随机分布性的，当样本数过少的时候就有可能出现一个问题如下图所示，服务器的节点可能聚集在某个位置，不能保证服务器节点均匀分布在哈希环上；分布不均匀造成请求访问不均匀，服务器承受的压力不均匀；hash偏移问题本质就是样本数过少的问题

为了解决哈希偏移的问题，增加了虚拟节点的概念；理论上，哈希环上节点数越多，数据分布越均衡；为每个服务节点计算多个哈希节点（虚拟节点）；通常做法是，hash("IP:PORT:seqno") %2^32；即可以在每个ip和端口之后再添加一个序列号的方式从而增加节点，而存储的时候只需要截取前面的ip和端口即可确定对应存储的节点，而且这种密集存储可以减少hash迁移的数据量。