為什么HashCode對于對象是如此的重要?
一個對象的HashCode就是一個簡單的Hash算法的實現(xiàn)，雖然它和那些真正的復(fù)雜的Hash算法相比還不能叫真正的算法，它如何實現(xiàn)它，不僅僅是程序員的編程水平問題，而是關(guān)系到你的對象在存取是性能的非常重要的關(guān)系.有可能，不同的HashCode可能會使你的對象存取產(chǎn)生，成百上千倍的性能差別。
我們先來看一下，在JAVA中兩個重要的數(shù)據(jù)結(jié)構(gòu):HashMap和Hashtable，雖然它們有很大的區(qū)別，如繼承關(guān)系不同，對 value的約束條件(是否允許null)不同，以及線程安全性等有著特定的區(qū)別，但從實現(xiàn)原理上來說，它們是一致的.所以，我們只以Hashtable 來說明:
在java中，存取數(shù)據(jù)的性能，一般來說當(dāng)然是首推數(shù)組，但是在數(shù)據(jù)量稍大的容器選擇中，Hashtable將有比數(shù)組性能更高的查詢速度.具體原因看下面的內(nèi)容。
Hashtable在存儲數(shù)據(jù)時，一般先將作為key的對象的HashCode和0x7FFFFFFF做與操作，因為一個對象的 HashCode可以為負(fù)數(shù)，這樣操作后可以保證它為一個正整數(shù).然后以Hashtable的長度取模，得到值對象在Hashtable中的索引。
index = (o.hashCode() & 0x7FFFFFFF)%hs.length;這個值對象就會直接放在Hashtable的第index位置，對于寫入，這和數(shù)組一樣，把一個對象放在其中的第index位置，但如果是查詢，經(jīng)過同樣的算法，Hashtable可以直接通過key得到index，從第index取得這個值對象，而數(shù)組卻要做循環(huán)比較.所以對于數(shù)據(jù)量稍大時，Hashtable的查詢比數(shù)據(jù)具有更高的性能。
雖然不同對象有不同的hashcode，但不同的hashCode經(jīng)過與長度的取余，就很可能產(chǎn)生相同的index。
極端情況下會有大量的對象產(chǎn)生一個相同的索引.這就是關(guān)系Hashtable性能問題的最重要的問題:
Hash沖突。
常見的Hash沖突是不同key對象最終產(chǎn)生了相同的索引，而一種非常甚至絕對少見的Hash沖突是，如果一組對象的個數(shù)大過了int 范圍，而HashCode的長度只能在int范圍中，所以肯定要有同一組的元素有相同的HashCode，這樣無論如何他們都會有相同的索引.當(dāng)然這種極端的情況是極少見的，可以暫不考慮，但是對于同的HashCode經(jīng)過取模，則會產(chǎn)中相同的索引，或者不同的對象卻具有相同的HashCode，當(dāng)然具有相同的索引。
事實上一個設(shè)計各好的HashTable，一般來說會比較平均地分布每個元素，因為Hashtable的長度總是比實際元素的個數(shù)按一定比例進(jìn)行自增(裝填因子一般為0.75)左右，這樣大多數(shù)的索引位置只有一個對象，而很少的位置會有幾個元素.所以Hashtable中的每個位置存放的是一個鏈表，對于只有一個對象是位置，鏈表只有一個首節(jié)點(Entry)，Entry的next為null.然后有 hashCode，key， value屬性保存了該位置的對象的HashCode，key和value(對象本身)，如果有相同索引的對象進(jìn)來則會進(jìn)入鏈表的下一個節(jié)點.如果同一個索引中有多個對象，根據(jù)HashCode和key可以在該鏈表中找到一個和查詢的key相匹配的對象。
從上面我看可以看到，對于 HashMap和Hashtable的存取性能有重大影響的首先是應(yīng)該使該數(shù)據(jù)結(jié)構(gòu)中的元素盡量大可能具有不同的HashCode，雖然這并不能保證不同的HashCode產(chǎn)生不同的index，但相同的HashCode一定產(chǎn)生相同的index，從而影響產(chǎn)生Hash沖突。
對于一個象，如果具有很多屬性，把所有屬性都參與散列，顯然是一種笨拙的設(shè)計.因為對象的HashCode()方法幾乎無所不在地被自動調(diào)用，如equals比較，如果太多的對象參與了散列.那么需要的操作常數(shù)時間將會增加很大.所以，挑選哪些屬性參與散列絕對是一個編程水平的問題。
從實現(xiàn)來說，一般的HashCode方法會這樣:
return Attribute1.HashCode() + Attribute1.HashCode()..[+super.HashCode()]。
我們知道，每次調(diào)用這個方法，都要重新對方法內(nèi)的參與散列的對象重新計算一次它們的HashCode的運算，如果一個對象的屬性沒有改變，仍然要每次都進(jìn)行計算，所以如果設(shè)置一個標(biāo)記來緩存當(dāng)前的散列碼，只要當(dāng)參與散列的對象改變時才重新計算，否則調(diào)用緩存的hashCode，這可以從很大程度上提高性能。
默認(rèn)的實現(xiàn)是將對象內(nèi)部地址轉(zhuǎn)化為整數(shù)作為HashCode，這當(dāng)然能保證每個對象具有不同的HasCode，因為不同的對象內(nèi)部地址肯定不同(廢話)，但java語言并不能讓程序員獲取對象內(nèi)部地址，所以，讓每個對象產(chǎn)生不同的HashCode有著很多可研究的技術(shù)。
如果從多個屬性中采樣出能具有平均分布的hashCode的屬性，這是一個性能和多樣性相矛盾的地方，如果所有屬性都參與散列，當(dāng)然 hashCode的多樣性將大大提高，但犧牲了性能，而如果只能少量的屬性采樣散列，極端情況會產(chǎn)生大量的散列沖突，如對"人"的屬性中，如果用性別而不是姓名或出生日期，那將只有兩個或幾個可選的hashcode值，將產(chǎn)生一半以上的散列沖突.所以如果可能的條件下，專門產(chǎn)生一個序列用來生成 HashCode將是一個好的選擇(當(dāng)然產(chǎn)生序列的性能要比所有屬性參與散列的性能高的情況下才行，否則還不如直接用所有屬性散列)。
如何對HashCode的性能和多樣性求得一個平衡，可以參考相關(guān)算法設(shè)計的書，其實并不一定要求非常的優(yōu)秀，只要能盡最大可能減少散列值的聚集.重要的是我們應(yīng)該記得HashCode對于我們的程序性能有著生要的影響，在程序設(shè)計時應(yīng)該時時加以注意。
原文地址：http://xy-z487.javaeye.com/blog/238074
本博客為學(xué)習(xí)交流用，凡未注明引用的均為本人作品，轉(zhuǎn)載請注明出處，如有版權(quán)問題請及時通知。由于博客時間倉促，錯誤之處敬請諒解，有任何意見可給我留言，愿共同學(xué)習(xí)進(jìn)步。