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)+"]");
}
}