在上章節中已經介紹了通過紅黑樹實現鍵值對數組的查詢操作，復雜度是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;
    }

    
    
    這種方法才是正確的。