Java Hash算法
何忆清风 人气:01. 实现原理
将key映射到 2^32 - 1 的空间中,将这个数字的首尾相连,形成一个环
- 计算节点(使用节点名称、编号、IP地址)的hash值,放置在环上
- 计算key的hash值,放置在环上,顺时针寻找到的第一个节点,就是应选取的节点
例如:p2、p4、p6三个节点,key11、key2、key27按照顺序映射到p2、p4、p6上面,假设新增一个节点p8在p6节点之后,这个时候只需要将key27从p6调整到p8就可以了;也就是说,每次新增删除节点时,只需要重新定位该节点附近的一小部分数据
2. 解决数据倾斜的问题
2.1 什么是数据倾斜?
如果服务器的节点过少,容易引起key的倾斜。例如上面的例子中p2、p4、p6分布在环的上半部分,下半部分是空的。那么映射到下半部分的key都会被分配给p2,key过度倾斜到了p2缓存间节点负载不均衡。
2.2 解决
为了解决这个问题,引入了虚拟节点的概念,一个真实的节点对应多个虚拟的节点,假设1个真实的节点对应3个虚拟节点,那么p1对应的就是p1-1、p1-2、p1-3
- 计算虚拟节点的Hash值,放置在环上
- 计算key的Hash值,在环上顺时针寻找到对应选取的虚拟节点,例如:p2-1,对应真实的节点p2
虚拟节点扩充了节点的数量,解决了节点较少的情况下数据倾斜的问题,而且代价非常小,只需要新增一个字典(Map)维护真实的节点与虚拟节点的映射关系就可以了
3. 代码实现
3.1 ConsistentHash
这里使用了泛型的方式来保存数据,可以根据不同的类型,获取到不同的节点存储
public class ConsistentHash<T> { //自定义hash方法 private Hash<Object> hashMethod; //创建hash映射,虚拟节点映射真实节点 private final Map<Integer, T> hashMap = new ConcurrentHashMap<>(); //将所有的hash保存起来 private List<Integer> keys = new ArrayList<>(); //默认虚拟节点数量 private final int replicas; public ConsistentHash() { this(3, Utils::rehash); } public ConsistentHash(int replicas, Hash<Object> hashMethod) { this.replicas = replicas; this.hashMethod = hashMethod; } @SafeVarargs public final void add(T... keys) { for (T key : keys) { //根据虚拟节点个数来计算虚拟节点 for (int i = 0; i < this.replicas; i++) { //根据函数获取到对应的hash值 int hash = this.hashMethod.hash(i + ":" + key.toString()); this.keys.add(hash); this.hashMap.put(hash, key); } } //排序,因为是一个环状结构 Collections.sort(this.keys); } /** * 根据对应的key来获取到节点信息 * * @param key * @return */ public T get(Object key) { Objects.requireNonNull(key, "key不能为空"); int hash = this.hashMethod.hash(key); //获取到对应的节点信息 int idx = Utils.search(this.keys.size(), h -> this.keys.get(h) >= hash); //如果idx == this.keys.size() ,就代表需要取 this.keys.get(0); 因为是环状,所以需要使用 % 来进行处理 return this.hashMap.get(this.keys.get(idx % this.keys.size())); } }
3.2 Hash
这里定义了一个函数结构,用于自定计算hash值
@FunctionalInterface public static interface Hash<T> { /** * 计算hash值 * * @param t * @return int类型 */ int hash(T t); }
3.3 Utils
由于hashcode采用的int类型进行存储,那么就需要考虑,hash是否超过了int最大存储,如果超过了那么存储的数字就是负数,会对获取节点造成影响,所以这里在取hash值时,采用了hashmap中获取到hashcode之后对其进行与操作,可以减少hash冲突,也可以避免负数的产生
public static class Utils { // int类型的最大数据 static final int HASH_BITS = 0x7fffffff; /** * 通过二分查找法,定义数组索引位置 * * @param len * @param f * @return */ public static int search(int len, Function<Integer, Boolean> f) { int i = 0, j = len; //通过二分查找发来定为索引位置 while (i < j) { //长度除于2 int h = (i + j) >> 1; //调用函数,判断当前的索引值是否大于 if (f.apply(h)) { //向低半段进行遍历 j = h; } else { //向高半段进行遍历 i = h + 1; } } return i; } /** * 将返回的hash能够平均的计算在 int类型之间 * * @param o * @return */ public static int rehash(Object o) { int h = o.hashCode(); return (h ^ (h >>> 16)) & HASH_BITS; } }
3.4 main
下面是main方法进行测试,在后面新增了一个节点之后,只会调整 zs 数据到 109 节点,而且其他两个key的获取不会受到影响
public static void main(String[] args) { ConsistentHash<String> consistentHash = new ConsistentHash<>(); consistentHash.add("192.168.2.106", "192.168.2.107", "192.168.2.108"); Map<String, Object> map = new HashMap<>(); map.put("zs", "192.168.2.108"); map.put("999999", "192.168.2.106"); map.put("233333", "192.168.2.106"); map.forEach((k, v) -> { String node = consistentHash.get(k); if (!v.equals(node)) { throw new IllegalArgumentException("节点获取错误,key:" + k + ",获取到的节点值为:" + node); } }); consistentHash.add("192.168.2.109"); map.put("zs", "192.168.2.109"); map.forEach((k, v) -> { String node = consistentHash.get(k); if (!v.equals(node)) { throw new IllegalArgumentException("节点获取错误,key:" + k + ",获取到的节点值为:" + node); } }); }
加载全部内容