在上章节中已经介绍了通过红黑树实现键值对数组的查询操作，复杂度是logN。有没有性能更好的算法呢？答案是有。

基本想法就是计算关键字的哈希值，再通过哈希值直接获取对应的键值。

这种方法的需要解决的问题是：

• 如何计算哈希值

• 如何解决哈系冲突

  
  

  哈希函数
  

  
  

  目标

  根据对象中的成员变量的值，按照一定的规则计算出一个整数，这个整数就是哈希值。

  
  

  哈希值最重要的两个属性是：
  

  • 如果a.equals(b)，那么a.hashCode() == b.hashCode()

  • 理想状况下，如果!a.equals(b)，那么a.hashCode() != b.hashCode()

    
    

    Java中的hash

    
    

    Java中的Object对象中已经包含了hashCode函数，由于所有的对象都继承自Object，因此所有的对象都有hashCode函数。该函数能返回一个整数，代表这个实例的哈希值。

    
    

    Java中Integer类型的hashCode代码如下：

    public int hashCode() {
        return value;
    }

    
    

    
    

    Double类型的hashCode代码如下：
    

    public int hashCode() {
        long bits = doubleToLongBits(value);
        return (int)(bits ^ (bits >>> 32));
    }

    
    

    
    

    String类型的hashCode代码如下：

    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哈希法。这种方法是一种非常简单的哈系算法，构造哈系冲突是非常容易的。在2011年11月，有人发现Java的HashMap存在漏洞容易让黑客实现Dos攻击，它的原理就是构造大量的哈系冲突让HashMap的复杂度从1变为N，占用大量的CPU资源，BUG的详细信息戳这里：https://bugzilla.redhat.com/show_bug.cgi?id=CVE-2012-2739

    
    

    由于String是不可变的类型，因此可以对hashCode进行缓存。

    
    

    自定义类型的hash计算
    

    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范围内，便于通过它来访问数组。
    

    
    

    第一种方法的代码如下：

    private int hash(Key key) {
        return key.hashCode() % M;
    }

    
    
    这段代码是错的。这种方法使用了取余数的操作，对于负数就会产生错误。
    

    第二种方法的代码如下：

    private int hash(Key key) {
        return Math.abs(key.hashCode()) % M;
    }

    
    
    这段代码中有BUG。这种方法在hashCode为负的0x80000000时会发生错误，因为它不能取相反数。

    第三种方法的代码如下：

    private int hash(Key key) {
        return (key.hashCode() & 0x7fffffff) % M;
    }

    
    
    这种方法才是正确的。