哈希表就是 依据关键字可以根据一定的算法（哈希函数）映射到表中的特定位置 的思想建立的表。因此哈希表最大的特点就是可以根据f(K)函数得到其在数组中的索引。
java官方说明中，Object的：
- equals方法具有自反性、对称性、传递性、一致性，如果两个对象执行equals方法结果为true，则两对象的哈希码应该是相等的。 如果重写equals方法，则一定要重写hashcode方法。
- hashcode方法是 返回对象的经过处理后的内存地址，由于每个对象的内存地址都不一样，所以哈希码也不一样。此方法为native方法，取决于JVM的内部设计，一般是某种C地址的偏移。
- 文档中还给出了三条规定：
- 在对象没有被修改的前提下，执行多次调用，该hashCode方法必须始终返回相同的整数。
- 如果两个对象执行equals方法结果为true，则分别调用hashCode方法产生的整数结果是相等的。
- 非必要要求：两个对象执行equals方法结果为false，则分别调用hashCode方法产生的整数结果是不相等的。
第三个要求虽然为非必需，但如果实现，则可以提高散列表的性能。
Object的hash方法
Object类的hashCode. 返回对象的经过处理后的内存地址，由于每个对象的内存地址都不一样，所以哈希码也不一样。这个是native方法，取决于JVM的内部设计，一般是某种C地址的偏移。
String的equals和hashCode方法
public int hashCode() {
int h = hash;
if (h == 0 && value.length > 0) {
char val[] = value;
for (int i = 0; i < value.length; i++) {
h = 31 * h + val[i];
}
hash = h;
}
return h;
}
该函数很简单，以31为权，每一位为字符的ASCII值进行运算，用自然溢出来等效取模，达到了目的——只要字符串的内容相同，返回的哈希码也相同。
- 选31作为乘子, 它可以被JVM优化：31 * i = (i << 5) - i，并且是一个奇质数
- unicode编码（万国码,原有的Ascii编码从单字节变成双字节,高位填0）固定占用两个字节，所以，java中char类型的变量也是占用两个字节。
public boolean equals(Object anObject) {
if (this == anObject) {
return true;
}
if (anObject instanceof String) {
String anotherString = (String)anObject;
int n = value.length;
if (n == anotherString.value.length) {
char v1[] = value;
char v2[] = anotherString.value;
int i = 0;
while (n-- != 0) {
if (v1[i] != v2[i])
return false;
i++;
}
return true;
}
}
return false;
}
此equals方法包含了"=="，双等号比较的是地址，存储地址相同，内容则相同。当地址不同的时候，先验证了比较对象是否为String，接着比较了两个字符串的长度，最后才循环比较每个字符是否相等。
Integer的equals和hashCode方法
@Override
public int hashCode() {
return Integer.hashCode(value);
}
//就是返回Integer对象里包含的那个整数的值
public static int hashCode(int value) {
return value;
}
public boolean equals(Object obj) {
if (obj instanceof Integer) {
return value == ((Integer)obj).intValue();
}
return false;
}
重写一个对象的hashcode
- 如果是boolean值，则计算 f ? 1:0；
- 如果是byte\char\short\int,则计算 (int)f；
- 如果是long值，则计算 (int)(f ^ (f >>> 32))；
- 如果是float值，则计算 Float.floatToIntBits(f)；
- 如果是double值，则计算 Double.doubleToLongBits(f)，然后返回的结果是long,再用规则(3)去处理long,得到int；
- 如果是对象应用，如果equals方法中采取递归调用的比较方式，那么hashCode中同样采取递归调用hashCode的方式。否则需要为这个域计算一个范式，比如当这个域的值为null的时候，那么hashCode 值为0；
- 如果是数组，那么需要为每个元素当做单独的域来处理。java.util.Arrays.hashCode 方法包含了8种基本类型数组和引用数组的hashCode计算，算法同上。
最后再将每个域的散列码相加
哈希碰撞（hash冲突）
- 再哈希法，就是出现冲突后采用其他的哈希函数计算，直到不再冲突为止。
- 链接地址法，是在出现冲突的地方存储一个链表，所有的同义词记录都存在其中。形象点说就行像是在出现冲突的地方直接把后续的值摞上去。例如HashMap结构。
这很容易理解，因为作为一种可用的散列算法，其位数一定是有限的，也就是说它能记录的文件是有限的——而文件数量是无限的，两个文件指纹发生碰撞的概率永远不会是零。
哈希算法
- 求模（%） 但单纯使用求模算法计算之后的结果带有明显的规律性，这种规律将导致算法将能难保证不可逆性。
- 异或（^） 再配合移位等运算
流行的hash算法包括 MD5（已被证明不具有强抗碰撞性）、SHA-1 和 SHA-256（碰撞时开销更大）
一个小例子，拍卖会一个人只能出一次价，大家都出好好，价高者得，避免数据提交后有人知道后作弊：最高价+1 这种情况发生，每个人只需要提交自己出价的hash值即可，等到公布后再拿出原价与hash值对应即可。
hash环（一致性hash算法）
先构造一个长度为232的整数环（这个环被称为一致性Hash环），根据节点名称的Hash值（其分布为[0, 232-1]）将服务器节点放置在这个Hash环上，然后根据数据的Key值计算得到其Hash值（其分布也为[0, 232-1]），接着在Hash环上顺时针查找距离这个Key值的Hash值最近的服务器节点，完成Key到服务器的映射查找。 ////这种算法解决了普通余数Hash算法伸缩性差的问题，可以保证在上线、下线服务器的情况下尽量有多的请求命中原来路由到的服务器。
图片.png
- list+排序
算出所有节点的hash值放入数组或集合（方便扩展）中，从小到大排列；之后，等待路由的一方，算出自己的hash，然后从list中找到第一hash值大于自己的节点即可，倘若没有，意味此hash值大于所有节点的hash值，那么选list(0)，即最小的那个即可。 - 遍历+list
- 服务器节点不排序，其Hash值全部直接放入一个List中
- 待路由的节点，算出其Hash值，由于指明了"顺时针"(指的list的顺时针)，因此遍历List，比待路由的节点Hash值大的，算出差值并记录，比待路由节点Hash值小的忽略。
- 算出所有的差值之后，最小的那个，就是最终需要路由过去的节点。
- 二叉查找树
当然我们不能简单地使用二叉查找树，因为可能出现不平衡的情况。平衡二叉查找树有AVL树、红黑树等，这里使用红黑树，选用红黑树的原因有两点：
- 红黑树主要的作用是用于存储有序的数据，这其实和第一种解决方案的思路又不谋而合了，但是它的效率非常高
- JDK里面提供了红黑树的代码实现TreeMap和TreeSet
另外，以TreeMap为例，TreeMap本身提供了一个tailMap(K fromKey)方法，支持从红黑树中查找比fromKey大的值的集合，但并不需要遍历整个数据结构。
使用红黑树，可以使得查找的时间复杂度降低为O(logN)，比上面两种解决方案，效率大大提升。
设置虚拟节点
String重写的hashCode()方法在一致性Hash算法中实用价值不大，因为有时服务器节点ip间差别很小，String的hash计算方式导致其值也差距小。得找个算法重新计算HashCode。这种重新计算Hash值的算法有很多，比如CRC32_HASH、FNV1_32_HASH（计算效率会高一些）、KETAMA_HASH（是默认的MemCache推荐的一致性Hash算法）。
/**
* 带虚拟节点的一致性Hash算法
* @author 五月的仓颉 http://www.cnblogs.com/xrq730/
*/
public class ConsistentHashingWithVirtualNode
{
/**
* 待添加入Hash环的服务器列表
*/
private static String[] servers = {"192.168.0.0:111", "192.168.0.1:111", "192.168.0.2:111",
"192.168.0.3:111", "192.168.0.4:111"};
/**
* 真实结点列表,考虑到服务器上线、下线的场景，即添加、删除的场景会比较频繁，这里使用LinkedList会更好
*/
private static List<String> realNodes = new LinkedList<String>();
/**
* 虚拟节点，key表示虚拟节点的hash值，value表示虚拟节点的名称
*/
private static SortedMap<Integer, String> virtualNodes =
new TreeMap<Integer, String>();
/**
* 虚拟节点的数目，这里写死，为了演示需要，一个真实结点对应5个虚拟节点
*/
private static final int VIRTUAL_NODES = 5;
static
{
// 先把原始的服务器添加到真实结点列表中
for (int i = 0; i < servers.length; i++)
realNodes.add(servers[i]);
// 再添加虚拟节点，遍历LinkedList使用foreach循环效率会比较高
for (String str : realNodes)
{
for (int i = 0; i < VIRTUAL_NODES; i++)
{
String virtualNodeName = str + "&&VN" + String.valueOf(i);
int hash = getHash(virtualNodeName);
System.out.println("虚拟节点[" + virtualNodeName + "]被添加, hash值为" + hash);
virtualNodes.put(hash, virtualNodeName);
}
}
System.out.println();
}
/**
* 使用FNV1_32_HASH算法计算服务器的Hash值,这里不使用重写hashCode的方法，最终效果没区别
*/
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;
}
/**
* 得到应当路由到的结点
*/
private static String getServer(String node)
{
// 得到带路由的结点的Hash值
int hash = getHash(node);
// 得到大于该Hash值的所有Map
SortedMap<Integer, String> subMap =
virtualNodes.tailMap(hash);
// 第一个Key就是顺时针过去离node最近的那个结点
Integer i = subMap.firstKey();
// 返回对应的虚拟节点名称，这里字符串稍微截取一下
String virtualNode = subMap.get(i);
return virtualNode.substring(0, virtualNode.indexOf("&&"));
}
public static void main(String[] args)
{
String[] nodes = {"127.0.0.1:1111", "221.226.0.1:2222", "10.211.0.1:3333"};
for (int i = 0; i < nodes.length; i++)
System.out.println("[" + nodes[i] + "]的hash值为" +
getHash(nodes[i]) + ", 被路由到结点[" + getServer(nodes[i]) + "]");
}
}
网友评论