散列演算法與散列碼

一、引入

看這個結果，問題就來了，map中明明存在Groudhog{number=3},為什麼結果顯示的是Key not find呢？？問題出在哪裡呢？原來是Groudhog類沒有重寫hashCode()方法，所以這裡是使用Object的hashCode()方法生成散列碼，而他默認是使用對象的地址計算散列碼。因此，由Groudhog(3)生成的第一個實例的散列碼與Groudhog(3)生成的散列碼是不同的，所以無法查找到 key。但是僅僅重寫hashCode()還是不夠的，除非你重寫equals()方法。原因在於不同的對象可能計算出同樣的hashCode的值，hashCode 的值並不是唯一的，當hashCode的值一樣時，就會使用equals()判斷當前的「鍵」是否與表中的存在的鍵「相同」，即「

如果兩個對象相同，那麼他們的hashCode值一定相同。

如果兩個對象的hashCode值相同，他們不一定相同。

正確的equals()方法必須滿足下列5個條件:

1、自反性: x.equals(x) 一定成立。

2、對稱性: 如果x.equals(y)成立，那麼y.equals(x)也一定成立。

3、傳遞性：如果x.equals(y)=true ,y.equals(z)=true,那麼x.equals(z)=true也成立。

4、一致性：無論調用x.equal(y)多少次，返回的結果應該保持一致。

5、對任何不是null的x，x.equals(null)一定返回false。

二、理解hashCode()

散列的價值就是速度：散列使得快速執行查詢成為可能。由於速度瓶頸是「鍵」的查詢，而存儲一組元素的最快數據結構是一個數組，所以用它來表示鍵的信息。並通過「鍵」對象來生成一個數字，作為數組的下標索引。這個數字是由對象中定義的hashCode（）生成（或散列轉換）的散列碼。同時，不同的「鍵」可以產生相同的下標，以解決陣列固定能力的問題。對於數值來說呢？如何在同一個下標索引中保存多個值？ ？原始數組不直接保存「值」，而是記錄「值」列表。然後對列表的「值」使用equals（）方法進行線性查詢。查詢的這一部分自然會變慢，但是如果你有一個很好的散列函數，每個索引只會保存少量的值，只有對少量的元素比較，會快很多。

不知道大家有沒有理解我上面在說什麼。不過沒關係，下面會有一個例子幫助大家理解。不過我之前一直被一個問題糾結：為什麼一個hashCode的下標存的會有多個值？因為hashMap裡面只能有唯一的key啊，所以只能有唯一的value在那個下標才對啊。這裡就要提出一個新的概念哈希衝突的問題，借用網上的一個例子：

比如：數組的長度是5。這時有一個數據是6。那麼如何把這個6存放到長度只有5的數組中呢。按照取模法，計算6％5，結果是1，那麼就把6放到數組下標是1的位置。那麼，7就應該放到2這個位置。到此位置，哈希衝突還沒有出現。這時，有個數據是11，按照取模法，11％5＝1，也等於1。那麼原來數組下標是1的地方已經有數了，是6。這時又計算出1這個位置，那麼數組1這個位置，就必須儲存兩個數了。這時，就叫哈希衝突。衝突之後就要按照順序來存放了。所以這裡Java中用的解決方法就是在這個hashCode上存一個List，當遇到相同的hashCode時，就往這個List里add元素就可以了。這才是hash原理的精髓所在啊！哈哈、糾結我一天。

三、HashMap的性能因子

容量(Capacity):散列表中的數量。

初始化容量(Initial capacity):創建散列表時桶的數量。HashMap 和 HashSet都允許你在構造器中制定初始化容量。

尺寸(Size):當前散列表中記錄的數量。

負載因子(Load factor):等於"size/capacity"。負載因子為0，表示空的散列表，0.5表示半滿的散列表，依次類推。輕負載的散列表具有衝突少、適宜插入與適宜查詢的特點(但是使用迭代器遍歷會變慢)。HashMap和hashSet的構造器允許你制定負載因子。這意味著，當負載達到制定值時，容器會自動成倍的增加容量，並將原有的對象重新分配，存入新的容器內(這稱為「重散列」rehashing)。HashMap默認的負載因子為0.75，這很好的權衡了時間和空間的成本。

備註：為使散列分佈均衡，Java的散列函數都使用2的整數次方來作為散列表的理想容量。對現代的處理器來說，除法和求余是最慢的動作。使用2的整數次方的散列表，可用掩碼代替除法。因為get()是使用最多的操作，求餘數的%操作是其開銷的大部分，而使用2的整數次方可以消除此開銷(也可能對hashCode()有些影響)

四、怎麼重寫hashCode()

現在的IDE工具中，一般都能自動的幫我們重寫了hashCode()和equals()方法，但那或許並不是最優的，重寫hashCode()有兩個原則:

• 必須速度快，並且必須有意義。也就是說，它必須基於對象的內容生成散列碼。

• 應該產生分佈均勻的散列碼。如果散列碼都集中在一塊，那麼在某些區域的負載就會變得很重。

下面是怎麼寫出一份像樣的hashCode()的基本指導：

1、給int變數result 賦予某個非零值常量，例如 17。

2、為每個對象內每個有意義的屬性f (即每個可以做equals()的屬性)計算出一個 int 散列碼c:

3、合併計算得到的散列值：result=37*result+c；

4、返回 result；

5、檢查hashCode()最後生成的結果，確保相同的對象有相同的散列碼。

五、自定義HashMap

下面我們將自己寫一個hashMap，便於了解底層的原理，大家如果看的懂下面的代碼，也就很好的理解了hashCode的原理了。