package com.test; import java.util.Collection; import java.util.HashMap; import java.util.HashSet; import java.util.Map; import java.util.Map.Entry; import java.util.SortedMap; import java.util.TreeMap; public class ConsistentHash<T> { private final HashFunction hashFunction;/** Hash计算对象,用于自定义hash算法 */ private final int numberOfReplicas;/** 复制的节点个数 */ private final SortedMap<Integer, T> circle = new TreeMap<Integer, T>();/** 一致性Hash环 */ public ConsistentHash(HashFunction hashFunction, int numberOfReplicas,Collection<T> nodes) { this.hashFunction = hashFunction; this.numberOfReplicas = numberOfReplicas; for (T node : nodes) { add(node); } } /** * 增加节点<br> * 每增加一个节点,就会在闭环上增加给定复制节点数<br> * 例如复制节点数是2,则每调用此方法一次,增加两个虚拟节点,这两个节点指向同一Node * 由于hash算法会调用node的toString方法,故按照toString去重 * @param node 节点对象 */ public void add(T node) { for (int i = 0; i < numberOfReplicas; i++) { circle.put(hashFunction.hash(node.toString() + i), node); } } /** * 移除节点的同时移除相应的虚拟节点 * @param node 节点对象 */ public void remove(T node) { for (int i = 0; i < numberOfReplicas; i++) { circle.remove(hashFunction.hash(node.toString() + i)); } } /** * 获得一个最近的顺时针节点 * @param key 为给定键取Hash,取得顺时针方向上最近的一个虚拟节点对应的实际节点 * @return 节点对象 */ public T get(Object key) { if (circle.isEmpty()) { return null; } int hash = hashFunction.hash(key); // System.out.println("hash---: " + hash); if (!circle.containsKey(hash)) { //返回此映射的部分视图,其键大于等于 hash SortedMap<Integer, T> tailMap = circle.tailMap(hash); hash = tailMap.isEmpty() ? circle.firstKey() : tailMap.firstKey(); } // System.out.println("hash---: " + hash); return circle.get(hash); } /*** * 自定义HASH算法 * */ static class HashFunction { int hash(Object key) { // md5加密后,hashcode return MD5Encrypt.encode(key.toString()).hashCode(); } } public static void main(String[] args) { HashSet<String> set = new HashSet<String>(); set.add("A"); set.add("B"); set.add("C"); set.add("D"); Map<String, Integer> map = new HashMap<String, Integer>(); ConsistentHash<String> consistentHash = new ConsistentHash<String>(new HashFunction(), 1000, set); int count = 10000; for (int i = 0; i < count; i++) { String key = consistentHash.get(i); if (map.containsKey(key)) { map.put(consistentHash.get(i), map.get(key) + 1); } else { map.put(consistentHash.get(i), 1); } // System.out.println(key); } showServer(map); map.clear(); consistentHash.remove("A"); System.out.println("------- remove A"); for (int i = 0; i < count; i++) { String key = consistentHash.get(i); if (map.containsKey(key)) { map.put(consistentHash.get(i), map.get(key) + 1); } else { map.put(consistentHash.get(i), 1); } // System.out.println(key); } showServer(map); map.clear(); consistentHash.add("E"); System.out.println("------- add E"); for (int i = 0; i < count; i++) { String key = consistentHash.get(i); if (map.containsKey(key)) { map.put(consistentHash.get(i), map.get(key) + 1); } else { map.put(consistentHash.get(i), 1); } // System.out.println(key); } showServer(map); map.clear(); consistentHash.add("F"); System.out.println("------- add F服务器 业务量加倍"); count = count * 2; for (int i = 0; i < count; i++) { String key = consistentHash.get(i); if (map.containsKey(key)) { map.put(consistentHash.get(i), map.get(key) + 1); } else { map.put(consistentHash.get(i), 1); } // System.out.println(key); } showServer(map); } public static void showServer(Map<String, Integer> map) { for (Entry<String, Integer> m : map.entrySet()) { System.out.println("服务器 " + m.getKey() + "----" + m.getValue() + "个"); } } }
相关推荐
一致性 hash 算法介绍
Ketama算法是一致性hash算法的一个优秀实现。增删节点后数据命中率及均分率都很高。
一致性hash应用于负载均衡算法,本实现由C++语言开发。 一致性hash算法提出了在动态变化的Cache环境中,判定哈希算法好坏的四个定义: 1、平衡性(Balance)2、单调性(Monotonicity) 3、分散性(Spread)4、负载(Load)
IT面试常见的题目,对于分布式存储系统中常碰到的故障问题,如何解决,就是采用一致性hash算法
一致性hash算法
一致性Hash算法的原理及实现
一致性hash算法简介
一致性hash算法简介加C++实现
摘要视图订阅登录 | 注册算法艺术(8)1004760次第1338名90篇16篇4篇595条一致性hash算法 - consistent hashing - s
一致性hash算法实现有两个关键问题需要解决,一个是用于结点存储和查找的数据结构的选择,另一个是结点hash算法的选择。 首先来谈一下一致性hash算法中用于存储结点的数据结构。通过了解一致性hash的原理,我们...
基于go语言实现的分布式缓存系统源码+项目说明(以键值对的形式存储数据,一致性hash算法选择存储节点,Protobuf通信协议编解码。用户输入查询请求后,会优先在缓存系统查询,查不到则使用回调函数去源数据库查询,...
一致性Hash算法,易于扩容;添加了 单元测试,使用Spring提供的RestTemplate调用RestFul风格的API接口;整合了 quartz 定时任务框架 ,并进行了封装,只需在构建完定时任务Job类后,在 application-quartz....
主要介绍了PHP实现的一致性Hash算法,结合实例形式详细分析了php一致性Hash算法的概念、原理及相关实现与使用技巧,需要的朋友可以参考下
随着虚拟节点的增加,数据量分配就比较平均了,但是并不是虚拟节点数量越多就越好,因为要考虑这些虚拟节点带来的性能开销以及算法的复杂性;
如果没有找到,则取整个环的第个节点。测试结果测试代码是整理的,主体法没有变分布平均性测试:测试随机成的众多key是否会平均分布到各个结点上测试结果如下:最上是参
c++实现的一致性hash算法库,可以直接编译成静态库、动态库,包含demo程序。
比如你有 N 个 cache 服务器(后面简称 cache ),那么如何将一个对象 object 映射到 N 个 cache 上呢,你很可能会采用类似下面的通用方法计算 object 的 hash 值,然后均匀的映射到到 N 个 cache ; hash(object)%N
引入“虚拟节点”后,映射关系就从{对象->节点}转换到了{对象->虚拟节点}。查询物体所在 cache时的映射关系如图 7 所示。图 7 查询对象所在 cach