大家好，又见面了，我是全栈君。
在上章节中已经介绍了通过红黑树实现键值对数组的查询操作，复杂度是logN。
有没有性能更好的算法呢？答案是有。
基本想法就是计算keyword的哈希值，再通过哈希值直接获取相应的键值。
这样的方法的须要解决的问题是：
- 怎样计算哈希值
- 怎样解决哈系冲突
哈希函数
目标
依据对象中的成员变量的值，依照一定的规则计算出一个整数。这个整数就是哈希值。
哈希值最重要的两个属性是：
- 假设a.equals(b)，那么a.hashCode() == b.hashCode()
- 理想状况下。假设!a.equals(b)，那么a.hashCode() != b.hashCode()
Java中的hash
Java中的Object对象中已经包括了hashCode函数，因为全部的对象都继承自Object，因此全部的对象都有hashCode函数。该函数能返回一个整数。代表这个实例的哈希值。
Java中Integer类型的hashCode代码例如以下：
代码语言：javascript复制public int hashCode() {
return value;
}Double类型的hashCode代码例如以下：
public int hashCode() {
long bits = doubleToLongBits(value);
return (int)(bits ^ (bits >>> 32));
}String类型的hashCode代码例如以下：
代码语言：javascript复制public int hashCode() {
int off = offset;
char val[] = value;
int len = count;
int h = 0;
for(int i = 0; i < len; i ) {
h = 31*h val[off ];
}
return h;
}这样的计算哈系的办法称之为Hornor哈希法。这样的方法是一种很简单的哈系算法。构造哈系冲突是很easy的。在2011年11月，有人发现Java的HashMap存在漏洞easy让黑客实现Dos攻击，它的原理就是构造大量的哈系冲突让HashMap的复杂度从1变为N，占用大量的CPU资源，BUG的具体信息戳这里：https://bugzilla.redhat.com/show_bug.cgi?
id=CVE-2012-2739
因为String是不可变的类型，因此能够对hashCode进行缓存。
自己定义类型的hash计算
代码语言：javascript复制public class Student { private int number; private String name; private String classname; public int hashCode() { int hash = 17; hash = hash*31 name.hashCode(); classname = hash*31 classname.hashCode(); }}其原理就是依照Hornor哈系法将各个成员变量的哈希值连接在一起。
哈希的取模操作
取模操作就是希望让哈系值能在0 ~ M-1范围内，便于通过它来訪问数组。
第一种方法的代码例如以下：
代码语言：javascript复制private int hash(Key key) { return key.hashCode() % M;}这段代码是错的。
这样的方法使用了取余数的操作，对于负数就会产生错误。
另外一种方法的代码例如以下：
代码语言：javascript复制private int hash(Key key) { return Math.abs(key.hashCode()) % M;}这段代码中有BUG。这样的方法在hashCode为负的0x80000000时会错误发生。由于它不能取相反数。
第三种方法的代码例如以下：
代码语言：javascript复制private int hash(Key key) { return (key.hashCode() & 0x7fffffff) % M;}这样的方法才是正确的。
发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/116054.html原文链接：https://javaforall.cn
