一致性 hash 算法( consistent hashing )介绍:
http://blog.csdn.net/sparkliang/archive/2010/02/02/5279393.aspx
一致性 hash 算法简单实现:
hashcode产生接口
package consistentHash;
/**
* @author zhengtian
*
* @date 2012-4-20 下午02:51:39
*/
@SuppressWarnings("all")
public interface HashFunction {
public int hash(Object key);
}
一致性 hash循环圈
package consistentHash;
import java.util.Collection;
import java.util.SortedMap;
import java.util.TreeMap;
/**
* @author zhengtian
*
* @date 2012-4-20 下午02:50:26
*/
@SuppressWarnings("all")
public class ConsistentHash<T> {
// hashcode生成接口
private final HashFunction hashFunction;
// 需要复制的虚拟节点个数
private final int numberOfReplicas;
// hashcode循环圈
private final SortedMap<Integer, T> circle = new TreeMap<Integer, T>();
/**
* 构造函数
*
* @param hashFunction
* @param numberOfReplicas
* @param nodes
* 真实节点数
*/
public ConsistentHash(HashFunction hashFunction, int numberOfReplicas, Collection<T> nodes) {
this.hashFunction = hashFunction;
this.numberOfReplicas = numberOfReplicas;
for (T node : nodes) {
add(node);
}
}
/**
* 增加节点
*
* @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));
}
}
/**
* 根据对象的key得到顺时针方向的第一个node
*
* @param key
* @return
*/
public T get(Object key) {
if (circle.isEmpty()) {
return null;
}
int hash = hashFunction.hash(key);
if (!circle.containsKey(hash)) {
// 得到circle中hashcode值大于等于hash的部分映射
SortedMap<Integer, T> tailMap = circle.tailMap(hash);
hash = tailMap.isEmpty() ? circle.firstKey() : tailMap.firstKey();
}
return circle.get(hash);
}
public static void main(String[] args) {
SortedMap<Integer, String> tailMap = new TreeMap<Integer, String>();
tailMap.put(1, "111");
tailMap.put(3, "333");
tailMap.put(4, "444");
tailMap.put(2, "222");
System.out.println(tailMap.firstKey());
System.out.println(tailMap.get(tailMap.firstKey()));
}
}
分享到:
相关推荐
一致性hash应用于负载均衡算法,本实现由C++语言开发。 一致性hash算法提出了在动态变化的Cache环境中,判定哈希算法好坏的四个定义: 1、平衡性(Balance)2、单调性(Monotonicity) 3、分散性(Spread)4、负载(Load)
Ketama算法是一致性hash算法的一个优秀实现。增删节点后数据命中率及均分率都很高。
一致性 hash 算法介绍
一致性Hash算法的原理及实现
算法之一致性hash(csdn)————程序
IT面试常见的题目,对于分布式存储系统中常碰到的故障问题,如何解决,就是采用一致性hash算法
一致性hash算法简介加C++实现
一致性hash算法
简单模拟实现一致性Hash,透过虚拟节点映射至实际结点,解决一致性Hash的单调性和平衡性问题。
一致性hash算法实现有两个关键问题需要解决,一个是用于结点存储和查找的数据结构的选择,另一个是结点hash算法的选择。 首先来谈一下一致性hash算法中用于存储结点的数据结构。通过了解一致性hash的原理,我们...
一致性哈希算法,广泛应用于分布式计算,C版实现,属于分布式服务器管理的核心算法。
别人写的一个一致性hash的java实现,分享下
一致性hash算法简介
Hash函数集合,包含主流的hash函数: nginx_hash算法,OpenSSL_hash算法,RSHash,JSHash,PJWHash,ELFHash,BKDRHash,DJBHash,DEKHash,APHash等等!
C语言实现hash算法源码,实现了sha256,sha384,sha512三种哈希算法,项目中用到的,提取出来测试使用的。
摘要视图订阅登录 | 注册算法艺术(8)1004760次第1338名90篇16篇4篇595条一致性hash算法 - consistent hashing - s
yxy版c++教程 Hash 浅谈哈希算法(csdn)————程序
hash算法中的sha1算法的讲解与实现,c++代码,可以直接运行,注释清晰,直接使用。
采用java实现的常用hash算法归总。