共计 2183 个字符，预计需要花费 6 分钟才能阅读完成。
Hash，个别翻译做“散列”，也有间接音译为“哈希”的 (刘森:I8O 薇 2857 電 8624 掂) 就是把任意长度的输出（又叫做预映射，pre-image），通过散列算法，变换成固定长度的输入，该输入就是散列值。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输出的空间，不同的输出可能会散列成雷同的输入，而不可能从散列值来惟一的确定输出值。简略的说就是一种将任意长度的消息压缩到某一固定长度的音讯摘要的函数。
散列函数能使对一个数据序列的拜访过程更加迅速无效，通过散列函数，数据元素将被更快地定位。罕用 Hash 函数有：
1．间接寻址法。取关键字或关键字的某个线性函数值为散列地址。即 H(key)=key 或 H(key)=a·key+b，其中 a 和 b 为常数（这种散列函数叫做本身函数）
2．数字分析法。剖析一组数据，比方一组员工的出生年月日，这时咱们发现出生年月日的前几位数字大体雷同，这样的话，呈现抵触的几率就会很大，然而咱们发现年月日的后几位示意月份和具体日期的数字差异很大，如果用前面的数字来形成散列地址，则抵触的几率会明显降低。因而数字分析法就是找出数字的法则，尽可能利用这些数据来结构抵触几率较低的散列地址。
3．平方取中法。取关键字平方后的两头几位作为散列地址。
4．折叠法。将关键字宰割成位数雷同的几局部，最初一部分位数能够不同，而后取这几局部的叠加和（去除进位）作为散列地址。
5．随机数法。抉择一随机函数，取关键字作为随机函数的种子生成随机值作为散列地址，通常用于关键字长度不同的场合。
6．除留余数法。取关键字被某个不大于散列表表长 m 的数 p 除后所得的余数为散列地址。即 H(key)=key MOD p,p<=m。不仅能够对关键字间接取模，也可在折叠、平方取中等运算之后取模。对 p 的抉择很重要，个别取素数或 m，若 p 选的不好，容易产生碰撞。
public class ConsistentHashingWithoutVirtualNode{
// 待增加入 Hash 环的服务器列表
private static String[]servers={“192.168.0.1:8888″,”192.168.0.2:8888”,
”192.168.0.3:8888″};
//key 示意服务器的 hash 值，value 示意服务器
private static SortedMap<Integer,String>sortedMap=new TreeMap<Integer,String>();
// 程序初始化，将所有的服务器放入 sortedMap 中
static{
for(int i=0;i<servers.length;i++){
int hash=getHash(servers);
System.out.println(“[“+servers+”]退出汇合中, 其 Hash 值为 ”+hash);
sortedMap.put(hash,servers);
}
}
// 失去该当路由到的结点
private static String getServer(String key){
// 失去该 key 的 hash 值
int hash=getHash(key);
// 失去大于该 Hash 值的所有 Map
SortedMap<Integer,String>subMap=sortedMap.tailMap(hash);
if(subMap.isEmpty()){
// 如果没有比该 key 的 hash 值大的，则从第一个 node 开始
Integer i=sortedMap.firstKey();
// 返回对应的服务器
return sortedMap.get(i);
}else{
// 第一个 Key 就是顺时针过来离 node 最近的那个结点
Integer i=subMap.firstKey();
// 返回对应的服务器
return subMap.get(i);
}
}
// 应用 FNV1_32_HASH 算法计算服务器的 Hash 值
private static int getHash(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;
}
public static void main(String[]args){
String[]keys={“semlinker”,”kakuqo”,”fer”};
for(int i=0;i<keys.length;i++)
System.out.println(“[“+keys+”]的 hash 值为 ”+getHash(keys)
+”, 被路由到结点[“+getServer(keys)+”]”);
}
}
