經(jīng)常在論壇上面看到覆寫hashCode函數(shù)的問題，很多情況下是一些開發(fā)者不了解hash code，或者和equals一起用的時(shí)候不太清楚為啥一定要復(fù)寫hashCode。
對(duì)于hash code的理論我不想多說，這個(gè)話題太大。我只想說用hash code的原因只有一個(gè)：效率。理論的說法它的復(fù)雜度只有O(1)。試想我們把元素放在線性表里面，每次要找一個(gè)元素必須從頭一個(gè)一個(gè)的找它的復(fù)雜度有O(n)。如果放在平衡二叉樹，復(fù)雜度也有O(log n)。
為啥很多地方說“覆寫equals的時(shí)候一定要覆寫hashCode”。說到這里我知道很多人知道有個(gè)原則：如果a.equals(b)那么要確保a.hashCode()==b.hashCode()。為什么？hashCode和我寫的程序的業(yè)務(wù)邏輯毫無關(guān)系，為啥我要override? 要我說如果你的class永遠(yuǎn)不可能放在hash code為基礎(chǔ)的容器內(nèi)，不必勞神，您真的不必override hashCode() :)
說得準(zhǔn)確一點(diǎn)放在HashMap和Hashtable里面如果是作為value而不是作為key的話也是不必override
hashCode了。至于HashSet，實(shí)際上它只是忽略value的HashMap,每次HashSet.add(o)其實(shí)就是
HashMap.put(o, dummyObject)。
那為什么放到Hash容器里面要overide hashCode呢？因?yàn)槊看蝕et的時(shí)候HashMap既要看equals是不是true也要看hash code是不是一致，put的時(shí)候也是要看equals和hash code。
如果說到這里您還是不太明白，咱就舉個(gè)例子：
譬如把一個(gè)自己定義的class
Foo{...}放到HashMap。實(shí)際上HashMap也是把數(shù)據(jù)存在一個(gè)數(shù)組里面，所以在put函數(shù)里面，HashMap會(huì)調(diào)
Foo.hashCode()算出作為這個(gè)元素在數(shù)組里面的下標(biāo)，然后把key和value封裝成一個(gè)對(duì)象放到數(shù)組。等一下，萬一2個(gè)對(duì)象算出來的
hash
code一樣怎么辦？會(huì)不會(huì)沖掉？先回答第2個(gè)問題，會(huì)不會(huì)沖掉就要看Foo.equals()了，如果equals()也是true那就要沖掉了。萬一
是false,就是所謂的collision了。當(dāng)2個(gè)元素hashCode一樣但是equals為false的時(shí)候，那個(gè)HashMap里面的數(shù)組的這
個(gè)元素就變成了鏈表。也就是hash code一樣的元素在一個(gè)鏈表里面，鏈表的頭在那個(gè)數(shù)組里面。
回過來說get的時(shí)候，HashMap也先調(diào)key.hashCode()算出數(shù)組下標(biāo)，然后看equals是不是true，所以就涉及了equals。
反觀假設(shè)如果a.equals(b)但是a.hashCode()!=b.hashCode()的話，在put元素a之后，我們又用一個(gè)
a.equals(b)但是b.hashCode()!=a.hashCode()的b元素作為key來get的時(shí)候就找不到a了。如果
a.hashCode()==b.hashCode()但是!a.equals(b)倒是不要緊，這2個(gè)元素會(huì)collision然后被放到鏈表，只是效
率變差。
這里有個(gè)非常簡(jiǎn)化版的HashMap實(shí)現(xiàn)幫助大家理解。
- /*
- * Just to demonstrate hash map mechanism,
- * Please do not use it in your commercial product.
- *
- * @author Shengyuan Lu 盧聲遠(yuǎn) <michaellufhl@yahoo.com.cn>
- */
- public class SimpleHashMap {
- ArrayList<LinkedList<Entry>> entries = new ArrayList<LinkedList<Entry>>();
-
- /**
- * Each key-value is encapsulated by Entry.
- */
- static class Entry {
- Object key;
- Object value;
- public Entry(Object key, Object value) {
- this.key = key;
- this.value = value;
- }
- }
- void put(Object key, Object value) {
- LinkedList<Entry> e = entries.get(key.hashCode());
- if (e != null) {
- for (Entry entry : e) {
- if (entry.key.equals(key)) {
- entry.value = value;// Match in lined list
- return;
- }
- }
- e.addFirst(new Entry(key, value));// Add the entry to the list
- } else {
- // Put the new entry in array
- LinkedList<Entry> newEntry = new LinkedList<Entry>();
- newEntry.add(new Entry(key, value));
- entries.add(key.hashCode(), newEntry);
- }
- }
- Object get(Object key) {
- LinkedList<Entry> e = entries.get(key.hashCode());
- if (e != null) {
- for (Entry entry : e) {
- if (entry.key.equals(key)) {
- return entry.value;
- }
- }
- }
- return null;
- }
-
- /**
- * Do we need to override equals() and hashCode() for SimpleHashMap itself?
- * I don't know either:)
- */
- }
這個(gè)問題的權(quán)威闡釋可以參考Bloch的<Effective Java>的 Item 9: Always override hashCode when you override equals