布隆过滤器、一致性哈希和并查集

一致性哈希

工程师常使用服务器集群来设计和实现数据缓存，以下是常见的策略：

1. 无论是添加、查询还是删除数据，都先将数据的id通过哈希函数转换成一个哈希值，记为key。
2. 如果目前有N台机器，则计算key%N的值，这个值就是该数据所属的机器编号。

请分析这种缓存策略可能带来的问题，并提出改进。

问题：如果增加或删除机器时（N变化）代价会很高，所有的收据都不得不根据id重新计算一遍哈希值，并将哈希值对新的机器数进行取模操作，然后进行大规模的数据迁移。

解决：假设数据的id通过哈希函数转换成的哈希值范围是2^32,我们可以将这些数字头尾相连，想象成一个闭合的环形，那么一个数据id在计算出哈希值之后认为对应到环中的一个位置上，然后顺时针寻离这个位置最近的机器，就是该数据归属的机器。

机器负载不均时的处理：引入虚拟节点机制，即对每一台机器通过不同的哈希函数计算出多个哈希值，对多个位置都放置一个服务节点，称为虚拟节点。具体做法可以在机器ip或主机名的后面增加编号或端口号来实现。以下图为例，可以为每台机器计算出两个虚拟节点，分别计算m1 - 1, m2 - 1， m1 - 2, m2 - 2的哈希值，于是形成四个虚拟节点，此时，数据定位算法不变，只是多了一步虚拟节点到实际节点的映射。

虚拟节点	对应的实际节点
m1 - 1	m1
m1 - 2	m1
m2 - 1	m2
m2 - 2	m2

布隆过滤器

不安全网页的黑名单包含100亿个黑名单网页，每个网页的URL最多占用64B, 现在想要实现一种网页过滤系统，可以根据网页的URL判断该网页是否在黑名单上，请设计该系统。

【要求】该系统有万分之一以下的失误率。使用的额外空间不要超过30GB。

假设有一个长度为m的bit类型数组，即数组中的每一个位置只占一个bit，如我们所知，每一个bit只有0和1两种状态，在假设一共有k个哈希函数，这些函数的输出域S都大于或等于m，并且这些哈希函数都足够优秀，那么对同一个输入对象，经过k个哈希函数算出来的结果也是独立的，对算出来的每一个结果都对m取余（%m）,然后在bit array上把相应的位置设1（涂黑）。

在检查阶段，假设一个对象为a，想检查它是否是之前的输入对象，就把a通过k个哈希函数算出k个值，然后k个值取余（%m）,就得到[0,m-1]范围上的k个值。接下来在bitMap上看这些位置是不是都为黑，如果有一个不为黑，说明a一定不在这个集合里，如果都为黑，说明a在这个集合里。（这个集合就叫布隆过滤器）

并查集

public class UnionFindSet {
	public static class Node {

	}

	public HashMap<Node, Node> fatherMap;
	public HashMap<Node, Integer> sizeMap;

	public UnionFindSet() {
		fatherMap = new HashMap<>();
		sizeMap = new HashMap<>();
	}

	public void makeSets(List<Node> nodes) {
		fatherMap.clear();
		sizeMap.clear();
		for (Node node : nodes) {
			fatherMap.put(node, node);
			sizeMap.put(node, 1);
		}
	}

	public Node findHead(Node node) {
		if (node == null) {
			return null;
		}
		Node father = fatherMap.get(node);
		while (father != node) {
			father = findHead(father);
		}
		fatherMap.put(node, father);
		return father;
	}

	public boolean isSameSet(Node a, Node b) {
		return findHead(a) == findHead(b);
	}

	public void union(Node a, Node b) {
		if (a == null || b == null) {
			return;
		}
		Node aHead = fatherMap.get(a);
		Node bHead = fatherMap.get(b);
		if (aHead != bHead) {
			int aSetSize = sizeMap.get(aHead);
			int bSetSize = sizeMap.get(bHead);
			if (aSetSize <= bSetSize) {
				fatherMap.put(aHead, bHead);
				sizeMap.put(bHead, aSetSize + bSetSize);
			} else {
				fatherMap.put(bHead, aHead);
				sizeMap.put(aHead, aSetSize + bSetSize);
			}
		}
	}
}