欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

一致性哈希java实现算法

程序员文章站 2024-03-19 21:40:22
...

hash算法

package com.cn.cmbc.function; 

import java.security.MessageDigest; 
import java.security.NoSuchAlgorithmException; 

public class HashFunction { 
private MessageDigest md5 = null; 

/** 
* 实现一致性哈希算法中使用的哈希函数,使用MD5算法来保证一致性哈希的平衡性 
* @param key 
* @return 
*/ 
/*public long hash(String key) { 
if (md5 == null) { 
try { 
md5 = MessageDigest.getInstance("MD5"); 
} catch (NoSuchAlgorithmException e) { 
throw new IllegalStateException("no md5 algrithm found"); 
} 
} 

md5.reset(); 
md5.update(key.getBytes()); 
byte[] bKey = md5.digest(); 
// 具体的哈希函数实现细节--每个字节 & 0xFF 再移位 
long result = ((long) (bKey[3] & 0xFF) << 4) 
| ((long) (bKey[2] & 0xFF) << 6 | ((long) (bKey[1] & 0xFF) << 8) | (long) (bKey[0] & 0xFF)); 
return result & 0xffffffffL; 
}*/ 

/** 
* 使用FNV1_32_HASH算法计算服务器的Hash值,这里不使用重写hashCode的方法,最终效果没区别 
* @param str 
* @return 
*/ 
public long hash(String str) { 
final int p = 16777619; 
int hash = (int) 2166136261L; 
for (int i = 0; i < str.length(); i++) 
hash = (hash ^ str.charAt(i)) * p; 
hash += hash << 13; 
hash ^= hash >> 7; 
hash += hash << 3; 
hash ^= hash >> 17; 
hash += hash << 5; 

// 如果算出来的值为负数则取其绝对值 
if (hash < 0) 
hash = Math.abs(hash); 
return hash; 
} 

} 

真正实现:

package com.cn.cmbc.function; 

import java.util.Collection; 
import java.util.HashSet; 
import java.util.Iterator; 
import java.util.Set; 
import java.util.SortedMap; 
import java.util.SortedSet; 
import java.util.TreeMap; 
import java.util.TreeSet; 

public class ConsistentHash<T> { 

private final HashFunction hashFunction; 
/** 
* 节点的复制因子,实际节点个数 * numberOfReplicas = 虚拟节点个数 
*/ 
private final int numberOfReplicas; 
/** 
* 存储虚拟节点的hash值到真实节点的映射 
*/ 
private final SortedMap<Long, T> circle = new TreeMap<Long, T>(); 

public ConsistentHash(HashFunction hashFunction, int numberOfReplicas, Collection<T> nodes) { 
this.hashFunction = hashFunction; 
this.numberOfReplicas = numberOfReplicas; 
for (T node : nodes) 
add(node); 
} 

public void add(T node) { 
for (int i = 0; i < numberOfReplicas; i++) 
// 对于一个实际机器节点 node, 对应 numberOfReplicas 个虚拟节点 
/* 
* 不同的虚拟节点(i不同)有不同的hash值,但都对应同一个实际机器node 
* 虚拟node一般是均衡分布在环上的,数据存储在顺时针方向的虚拟node上 
*/ 
circle.put(hashFunction.hash(node.toString() + i), node); 
} 

public void remove(T node) { 
for (int i = 0; i < numberOfReplicas; i++) 
circle.remove(hashFunction.hash(node.toString() + i)); 
} 

/* 
* 获得一个最近的顺时针节点,根据给定的key 取Hash 然后再取得顺时针方向上最近的一个虚拟节点对应的实际节点 再从实际节点中取得 数据 
*/ 
public T get(Object key) { 
if (circle.isEmpty()) 
return null; 
long hash = hashFunction.hash(String.valueOf(key));// node 
// 用String来表示,获得node在哈希环中的hashCode 
if (!circle.containsKey(hash)) {// 数据映射在两台虚拟机器所在环之间,就需要按顺时针方向寻找机器 
SortedMap<Long, T> tailMap = circle.tailMap(hash); 
hash = tailMap.isEmpty() ? circle.firstKey() : tailMap.firstKey(); 
} 
return circle.get(hash); 
} 

public long getSize() { 
return circle.size(); 
} 

/* 
* 查看MD算法生成的hashCode值---表示整个哈希环中各个虚拟节点位置 
*/ 
public void testBalance() { 
Set<Long> sets = circle.keySet();// 获得TreeMap中所有的Key 
SortedSet<Long> sortedSets = new TreeSet<Long>(sets);// 将获得的Key集合排序 
for (Long hashCode : sortedSets) { 
System.out.println(hashCode); 
} 

System.out.println("----each location 's distance are follows: ----"); 
/* 
* 查看用MD算法生成的long hashCode 相邻两个hashCode的差值 
*/ 
Iterator<Long> it = sortedSets.iterator(); 
Iterator<Long> it2 = sortedSets.iterator(); 
if (it2.hasNext()) 
it2.next(); 
long keyPre, keyAfter; 
while (it.hasNext() && it2.hasNext()) { 
keyPre = it.next(); 
keyAfter = it2.next(); 
System.out.println(keyAfter - keyPre); 
} 
} 

public static void main(String[] args) { 
Set<String> nodes = new HashSet<String>(); 
nodes.add("table_01"); 
nodes.add("table_02"); 
nodes.add("table_03"); 
nodes.add("table_04"); 
nodes.add("table_05"); 
nodes.add("table_06"); 
nodes.add("table_07"); 
nodes.add("table_08"); 
nodes.add("table_09"); 
nodes.add("table_00"); 

ConsistentHash<String> consistentHash = new ConsistentHash<String>(new HashFunction(), 100, nodes); 

System.out.println("hash circle size: " + consistentHash.getSize()); 
System.out.println("location of each node are follows: "); 
// consistentHash.testBalance(); 

int table_01 = 0; 
int table_02 = 0; 
int table_03 = 0; 
int table_04 = 0; 
int table_05 = 0; 
int table_06 = 0; 
int table_07 = 0; 
int table_08 = 0; 
int table_09 = 0; 
int table_00 = 0; 

for (int i = 0; i < 1000; i++) { 

String res = consistentHash.get(i); 
switch (res) { 

case "table_01": 
table_01++; 
break; 
case "table_02": 
table_02++; 
break; 
case "table_03": 
table_03++; 
break; 
case "table_04": 
table_04++; 
break; 
case "table_05": 
table_05++; 
break; 
case "table_06": 
table_06++; 
break; 
case "table_07": 
table_07++; 
break; 
case "table_08": 
table_08++; 
break; 
case "table_09": 
table_09++; 
break; 
case "table_00": 
table_00++; 
break; 
default: 
break; 

} 

} 

System.out.println("table_01:" + table_01); 
System.out.println("table_02:" + table_02); 
System.out.println("table_03:" + table_03); 
System.out.println("table_04:" + table_04); 
System.out.println("table_05:" + table_05); 
System.out.println("table_06:" + table_06); 
System.out.println("table_07:" + table_07); 
System.out.println("table_08:" + table_08); 
System.out.println("table_09:" + table_09); 
System.out.println("table_00:" + table_00); 

} 

}