8 篇博文 含有标签「算法」

前言​

判断某个元素是否在一个集合中在日常开发工作中十分常见，如判断用户是否重复注册、避免伪造不存在的记录导致缓存穿透、判断用户是否参加过某活动等。最直观的做法是使用HashSet，底层使用哈希表，但是哈希表在元素数量很大时需要占用非常大的空间。

布隆过滤器（Bloom Filter）是 1970 年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于判断一个元素一定不在某个集合中，以及一个元素可能在某个集合中，对于存在性它有一定的误判率。它的优点是空间效率和查询时间都远远超过一般的算法。

工作原理​

前言​

一致性哈希是一种特殊的哈希算法，它的核心思想是在解决分布式环境下，Hash表在动态扩缩容时节点重新映射与大量数据迁移的问题。主要的应用场景是：对于有状态服务等场景，需要根据特定的key路由到相同的目标服务机器上进行处理的场景。

一般情况下我们会使用Hash表的方式，以key-value的方式来做数据的存储。但是，当数据量比较大的情况下，我们会把数据存储到多个节点上，然后通过哈希取模的方式来决定把当前的key存储到哪个节点。但是这种方式有个很明显的问题，就是当存储的节点增加或者减少的时候，原本的映射关系就会发生变化，也就是对于所有的数据需要按照新的节点数量再重新映射一遍，这样就涉及了大量的数据迁移和重新映射的问题，它的代价很大。而一致性哈希算法，就是用来优化这样的动态变化的场景的一种算法。

一致性哈希算法的评判指标：

• 平衡性：不同key的哈希结果分布均衡，尽可能的均衡地分布到各节点上。
• 单调性：当有新的节点上线后，系统中原有的key要么还是映射到原来的节点上，要么映射到新加入的节点上，不会出现从一个老节点重新映射到另一个老节点。
• 分散性：当上游的机器看到不同的下游列表时（在上线时及不稳定的网络中比较常见）, 同一个请求尽量映射到少量的节点中。
• 服务器负载均衡：负载主要是从服务器的角度来看，指各服务器的负载应该尽量均衡。 一致性哈希算法的关键特征在于： 不要导致全局重新映射， 而是要做增量的重新映射。

二分法的思路比较简单，但往往不容易写对，比如要不要加等号、死循环等问题。实际上，二分法就是一个逐步缩小范围的过程，每次缩小一半。

经典应用​

最经典的二分法的应用是：一个有序数组arr（例如升序），数组元素不同，从数组中找数target的索引，如果不存在返回-1。代码比较简单：

int binarySearch(int[] arr, int target) {
    int left = 0;
    int right = arr.length - 1;
    while (left <= right) {
        int mid = left + right >> 1;
        if (arr[mid] == target) return mid;
        if (arr[mid] > target) right = mid - 1;
        else left = mid + 1;
    }
    return -1;
}

计算a的b次方模m：

$a^b \% m$

暴力的做法是将a乘b次，最后对m取模。不过，这样可能导致溢出，时间复杂度也很高。

现在考虑，求3的10次方，最少需要做几次乘法运算。

引言​

有若干节点，并将其中一些节点对进行连接，要判断任意两个节点是否连通（有路径到达，而不要求直接连接），连通后就不会断开连通关系，此时就可以使用并查集。并查集擅长动态维护许多具有传递性的关系，能在无向图中维护节点之间的连通性。

要判断两个节点是否连通，可以把连通的节点加入到各自的集合里，也就是，同一个集合里的节点都是连通的，不同集合里的节点是不连通的。