---

哈希函数

`哈希函数是一种将任意长度的输入（又称为预映射），通过散列算法，变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，即散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，而这种映射通常是不可逆的。

哈希函数的主要特点

确定性

对于同一个输入值，哈希函数在每次执行时都会产生相同的哈希值。例如，假设有一个哈希函数H，输入字符串“hello”，每次计算得到的哈希值都是固定的一个值，比如“348920349234”。这种确定性使得哈希函数可以用于数据校验等场景，只要输入不变，就可以通过比较哈希值来判断数据是否被篡改。

快速计算

能够快速计算出输入值的哈希值。在很多应用中，如数据库索引、文件系统等，需要频繁地对大量数据进行哈希计算。如果哈希函数计算速度很慢，就会严重影响系统的性能。例如，在一个大规模的分布式存储系统中，当需要对海量文件进行索引时，快速计算文件内容的哈希值可以加快索引构建的速度。

输出长度固定

不管输入数据的长度如何，哈希函数产生的输出长度是固定的。例如，MD5哈希函数的输出长度总是128位（16字节）。这意味着无论输入是一个字节还是一个TB（太字节）的数据，输出都是长度相同的一串二进制数。这种固定长度的输出便于存储和比较，例如在一些安全协议中，固定长度的哈希值可以方便地在网络中传输和进行安全校验。

离散性

哈希函数的离散性是指输出的哈希值在值域内是均匀分布的，即不同的输入值通过哈希函数映射后，得到的哈希值在哈希空间中是随机且均匀散布的。这一特性对于哈希函数的性能和应用至关重要。

哈希表

哈希表的原理

哈希表是通过链表，哈希函数，数组的共同作用下形成的。
一个字符串通过哈希函数计算得到一个哈希值，将哈希值模上规定的数组的长度，将字符串连同得到的哈希值包装起来，如果模完得到的结果在数组中已存在节点，便将包装后的结果用链表的方式串联在原本节点之后，如果没有便直接放在数组的对应位置，这样便得到了一个哈希表。由于哈希函数的离散性，数据种类一多最终得到的结果便是分布均匀的，为了避免链表过长，在链表的长度达到某个阈值时，便会对数组进行扩容。由哈希函数的原理可知，查找哈希函数中的某个字符串时，尽管其常数时间会很大但其时间复杂度为O（1）。

解题

在求解这道题中，我们需要用到两个哈希表，第一个哈希表存储值与其对应的下标，第二个哈希表存储下标与其对应的值。

在insert时，我们先查询map1，如果map1中并不存在要插入的key，我们便可以按照上述规则进行插入，由于哈希表的时间复杂度为O（1），则该结构的插入操作也是O（1）的时间复杂度。

在getrandom时，我们只需要用一个random函数在0-size这个范围内得到一个随机的数，之后在map2哈希表中查找并返回就可以了。

在delete时，由于需要维护这个连续性，会麻烦一点，在删除操作中，我们需要将map1中最后一个字段对应的下标先修改为和要删除的字段对应的下标一致，之后删除map1的最后一个要删除的数。在map2中，我们先从map1中查询出要删除的下标，并在map2中得到最后一个下标对应的key，将map2中对应下标的值修改为最后一个下标对应的key，并将最后一个字段删除。
完整代码

布隆过滤器

布隆过滤器（Bloom Filter）是一种空间效率很高的概率型数据结构，由Burton Howard Bloom在1970年提出，它用于判断一个元素是否在一个集合中。

布隆过滤器的主要特点

高效性

布隆过滤器使用多个哈希函数和位数组来存储数据，占用的内存空间远小于存储实际集合所需的空间。

快速查询

可以在常数时间内完成对元素的查找，即查询速度非常快。

空间效率

由于其概率性质，布隆过滤器可以在非常小的空间内存储大量数据。

误报率

布隆过滤器可能会有误报，即可能会错误地认为某个元素存在于集合中，但不会漏报（即如果元素真的存在于集合中，布隆过滤器一定不会说它不存在）。布隆过滤器不能从集合中删除元素，因为删除操作可能会影响其他元素的判断结果。

布隆过滤器的原理

布隆过滤器本质上是一个位图。其原理为：将一个字段用k个哈希函数计算得到k个值，将这些值分别模上布隆过滤器的长度m，将布隆过滤器对应位置涂黑便代表这个字段已经加入到布隆过滤器的黑名单中。那如何判断一个字段是否在黑名单中呢，我们可以使用相同的方法对字段进行计算得到k个位置，只有当这k个字段均黑时，才代表该字段在黑名单中。
那如何选择m和k的个数呢？由前文的原理可知，当m变大时，失误率在逐渐减少的；当k值变大时，由于一开始每个字段的信息够多，所以失误率在逐渐降低，但当k值到达一个阈值时，k值变大会导致每个字段所描黑的位置更多导致失误率反而上升了。

由此我们可以得出计算合适k值与m值的三个公式

一致性哈希

一致性哈希原理

在一致性哈希中，哈希函数的输出（通常是整数）被想象成一个固定大小的圆环，这个圆环被称为哈希环。哈希值在这个环上均匀分布，每个服务器（或缓存节点）在这个环上都有一个或多个位置（即哈希值）。数据（如缓存项或请求）通过哈希函数映射到环上的某个位置，然后按照顺时针方向被路由到第一个遇到的服务器。

一致性哈希应用

在实际应用中，为了提高哈希环的利用率和负载均衡，通常会在哈希环上为每个服务器分配多个虚拟节点（或称为虚拟服务器）。这些虚拟节点均匀分布在哈希环上，数据项首先映射到这些虚拟节点，然后再由虚拟节点路由到实际的物理服务器。
例如，如果有三个服务器，可以在哈希环上为每个服务器分配三个虚拟节点，这样总共有9个虚拟节点分布在环上。当一个数据项通过哈希函数映射到环上时，它会被路由到顺时针方向遇到的第一个虚拟节点，该虚拟节点对应的物理服务器就负责处理这个数据项。
通过这种方式，即使服务器数量发生变化，也只需要调整部分虚拟节点的位置，从而减少了数据迁移的需要，提高了系统的稳定性和扩展性。