如何解决以下问题？

有两个字符串数组，每个数组大约有 10 万条字符串，如何快速找出两个数组中相同的字符串？

用两个for循环暴力循环吗？ No，这是不可以接受的
如果用Hash表来作为数据结构，就可以完美解决以上问题。

散列函数

散列函数我们可以把它定义成hash(key)，其中 key 表示元素的键，hash(key) 的值表示经过散列函数计算得到的散列值。
image.png

散列冲突

不同的key对应着同一个散列值的情况我们称为散列冲突。

如何解决散列冲突？

  1. 开放寻址法，如果出现了散列冲突，我们就重新探测一个空闲位置，将其插入。散列表中的数据都存储在数组中，可以有效地利用 CPU 缓存加快查询速度，当数据量比较小、装载因子小的时候，适合采用开放寻址法）
  2. 链表法，相同的散列值用一个链表存取，例如LinkedHashMap（这种方法对装载因子容忍度更高，假设装载因子大于1，也仅仅是链表长度的增加而已，而且也可以把链表更改为红黑树等结构，降低查询效率）

而如果散列冲突次数过多（也就是装载因子过大），链表法拉起了太长的链子，那么查询效率也会大大降低，这时候就可以对散列表进行扩容。

装载因子的计算公式是：

装载因子= 填入表中的元素个数 / 散列表的长度

  • 假设每次扩容我们都申请一个原来散列表大小两倍的空间。如果原来散列表的装载因子是 0.8，那经过扩容之后，新散列表的装载因子就下降为原来的一半，变成了 0.4。

动态扩容

在散列表中，扩容后即会重新计算每一个key的散列值然后搬移到新的散列表中，这势必是需要时间计算的，如果此时有插入操作发生，就会发生极个别非常慢的插入操作。

如何避免这种现象？答案就是非一致性扩容。

  1. 扩容时仅仅扩容而不搬移数据
  2. 当有新数据要插入时，我们将新数据插入新散列表中，并且从老的散列表中拿出一个数据放入到新散列表。
  3. 重复以上2操作

分布式存储导致缓存雪崩

背景：分布式缓存。我们有海量的数据需要缓存，所以一个缓存机 器肯定是不够的。于是，我们就需要将数据分布在多台机器上，假设我们的集群机器数量是10。如果数据增多，原来的 10 个机器已经无法承受了，我们就需要扩容了，比如扩到 11 个机器，这时候麻烦就来了…

image.png
这会导致海量数据要重新计算hash值，也称为缓存雪崩。

这时候，一致性哈希算法就要登场了

一致性hash

一致性哈希算法(Consistent Hashing Algorithm)是一种分布式算法，常用于负载均衡。

原理：

  1. 构建环形hash空间
  2. 将服务器节点都映射到此环形空间
  3. 首先确定对象hash 值在环上的位置，从此位置沿环顺时针“行走”，第一台遇到的服务器就是其应该定位到的服务器
  4. 当发生增删服务器节点时，仅影响一部分机器：

image.png