為什麼HashCode對于對象如此的重要

Hash表資料結構常識：

1. 哈希表基于數組。
2. 缺點：基于數組的，數組建立後難以擴充。某些哈希表被基本填滿時，性能下降得非常嚴重。
3. 沒有一種簡便得方法可以以任何一種順序周遊表中資料項。
4. 如果不需要有序周遊資料，并且可以提前預測資料量的大小，那麼哈希表在速度和易用性方面是無與倫比的。

為什麼HashCode對于對象是如此的重要：

一個對象的HashCode就是一個簡單的Hash算法的實作，雖然它和那些真正的複雜的Hash算法相比還不能叫真正的算法，它如何實作它，不僅僅是程式員的程式設計水準問題，

而是關系到你的對象在存取是性能的非常重要的關系.有可能，不同的HashCode可能會使你的對象存取産生，成百上千倍的性能差别.

先來看一下，在JAVA中兩個重要的資料結構:HashMap和Hashtable，雖然它們有很大的差別，如繼承關系不同，對value的限制條件(是否允許null)不同，以及線程安全性等有着特定的差別，但從實作原理上來說，它們是一緻的.是以，我們隻以Hashtable來說明：

在java中，存取資料的性能，一般來說當然是首推數組，但是在資料量稍大的容器選擇中，Hashtable将有比資料性能更高的查詢速度.具體原因看下面的内容.

Hashtable在存儲資料時，一般先将該對象的HashCode和0x7FFFFFFF做與操作，因為一個對象的HashCode可以為負數，這樣操作後可以保證它為一個正整數.然後以Hashtable的長度取模，得到該對象在Hashtable中的索引.

index = (o.hashCode() & 0x7FFFFFFF)%hs.length;

這個對象就會直接放在Hashtable的每index位置，對于寫入，這和資料一樣，把一個對象放在其中的第index位置，但如果是查詢，經過同樣的算法，Hashtable可以直接從第index取得這個對象，而數組卻要做循環比較.是以對于資料量稍大時，Hashtable的查詢比資料具有更高的性能.

既然一個對象可以根據HashCode直接定位它在Hashtable中的位置，那麼為什麼Hashtable還要用key來做映射呢?這就是關系Hashtable性能問題的最重要的問題：Hash沖突.

常見的Hash沖突是不同對象最終産生了相同的索引，而一種非常甚至絕對少見的Hash沖突是，如果一組對象的個數大過了int範圍，而HashCode的長度隻能在int範圍中，是以肯定要有同一組的元素有相同的HashCode，這樣無論如何他們都會有相同的索引.當然這種極端的情況是極少見的，可以暫不考慮，但是對于同的HashCode經過取模，則會産中相同的索引，或者不同的對象卻具有相同的HashCode，當然具有相同的索引.

是以對于索引相同的對象，在該index位置存放了多個值，這些值要想能正确區分，就要依靠key來識别.

事實上一個設計各好的HashTable，一般來說會比較平均地分布每個元素，因為Hashtable的長度總是比實際元素的個數按一定比例進行自增(裝填因子一般為0.75)左右，這樣大多數的索引位置隻有一個對象，而很少的位置會有幾個元素.是以Hashtable中的每個位置存放的是一個連結清單，對于隻有一個對象是位置，連結清單隻有一個首節點(Entry)，Entry的next為null.然後有hashCode，key，value屬性儲存了該位置的對象的HashCode，key和value(對象本身)，如果有相同索引的對象進來則會進傳入連結表的下一個節點.如果同一個索引中有多個對象，根據HashCode和key可以在該連結清單中找到一個和查詢的key相比對的對象.

從上面我看可以看到，對于HashMap和Hashtable的存取性能有重大影響的首先是應該使該資料結構中的元素盡量大可能具有不同的HashCode，雖然這并不能保證不同的HashCode産生不同的index，但相同的HashCode一定産生相同的index，進而影響産生Hash沖突.

對于一個對象，如果具有很多屬性，把所有屬性都參與散列，顯然是一種笨拙的設計.因為對象的HashCode()方法幾乎無所不在地被自動調用，如equals比較，如果太多的對象參與了散列.

那麼需要的操作常數時間将會增加很大.是以，挑選哪些屬性參與散列絕對是一個程式設計水準的問題.

從實作來說，一般的HashCode方法會這樣:

return Attribute1.HashCode() Attribute1.HashCode()…[ super.HashCode()]，我們知道，每次調用這個方法，都要重新對方法内的參與散列的對象重新計算一次它們的HashCode的運算，如果一個對象的屬性沒有改變，仍然要每次都進行計算，是以如果設定一個标記來緩存目前的散列碼，隻要當參與散列的對象改變時才重新計算，否則調用緩存的hashCode，這可以從很大程度上提高性能.

預設的實作是将對象内部位址轉化為整數作為HashCode，這當然能保證每個對象具有不同的HasCode，因為不同的對象内部位址肯定不同(廢話)，但java語言并不能讓程式員擷取對象内部位址，是以，讓每個對象産生不同的HashCode有着很多可研究的技術.

如果從多個屬性中采樣出能具有平均分布的hashCode的屬性，這是一個性能和多樣性相沖突的地方，如果所有屬性都參與散列，當然hashCode的多樣性将大大提高，但犧牲了性能，而如果隻能少量的屬性采樣散列，極端情況會産生大量的散列沖突，如對"人"的屬性中，如果用性别而不是姓名或出生日期，那将隻有兩個或幾個可選的hashcode值，将産生一半以上的散列沖突.是以如果可能的條件下，專門産生一個序列用來生成HashCode将是一個好的選擇(當然産生序列的性能要比所有屬性參與散列的性能高的情況下才行，否則還不如直接用所有屬性散列).

如何對HashCode的性能和多樣性求得一個平衡，可以參考相關算法設計的書，其實并不一定要求非常的優秀，隻要能盡最大可能減少散列值的聚集.重要的是我們應該記得HashCode對于我們的程式性能有着重要的影響，在程式設計時應該時時加以注意.

請記住：如果你想有效的使用HashMap，你就必須重寫在其的HashCode()。

還有兩條重寫HashCode()的原則：

1. 不必對每個不同的對象都産生一個唯一的hashcode，隻要你的HashCode方法使get()能夠得到put()放進去的内容就可以了。即“不為一原則”。
2. 生成hashcode的算法盡量使hashcode的值分散一些， 不要很多hashcode都集中在一個範圍内，這樣有利于提高HashMap的性能。即“分散原則”。