什么是hashcode （轉）
http://www.iteye.com/topic/838030
分析HashMap之前先介紹下什么Hashcode(散列碼)。它是一個int，每個對象都會有一個hashcode，它在內存的存放位置是放在對象的 頭部（對象頭部存放的信息有hashcode，指向Class的引用，和一些有關垃圾回收信息）。具體如何生成hashcode，這個相當復雜，由于我們 的主題是“淺析”，所以不深入探討。有個問題需要講的是，如果在你的類中覆蓋了Object的equals(Object)方法，那么你必須覆蓋 hashCode方法，不然，當你使用HashMap，HashSet，HashTable時會出現問題。具體原因下文會詳細描述。
String類的hashcode String類重寫了Object類中的equals和hashCode方法，原因很簡單，Object中的equals方法是指比較兩個對象是不是指向 同一個引用對象，而String類指需要比較內容相不相等就可以了。所以String覆蓋了equals方法，同時覆蓋了hashCode方法。這里需要 提一下Object規范里規定：如果兩個對象根據equals(Object)方式是相等的，那么這兩個對象的hashCode一定要相等。
String中的hashcode算法很簡單如下：
Java代碼
- for (int i = 0; i < len; i++) {
- h = 31*h + val[off++];
- }
Val是一個char[]，存放的是字符串的各個字符；Len是字符串長度；off從0開始；h從0開始。比如一個字符串“abc”(a的ascii碼是97)，它的hashcode算法是：
h = 31 * 0 + 97 ==> h = 97;
h = 31 * 97 + 98 ==> h = 3105;
h = 31 * 3105 + 99 ==> h = 96354;
所以“abc”的hashCode就是96354
存儲方式 列表的存儲方式是基于數組，如下圖：
鏈表的存儲方式是基于指針，如下圖：（單向鏈表）
HashMap的存儲方式是上面兩種的結合，如下圖：
HashMap的存取 HashMap的功能是通過“鍵(key)”能夠快速的找到“值”。下面我們分析下HashMap存數據的基本流程：
1、 當調用put(key,value)時，首先獲取key的hashcode，int hash = key.hashCode();
2、 再把hash通過一下運算得到一個int h.
hash ^= (hash >>> 20) ^ (hash >>> 12);
int h = hash ^ (hash >>> 7) ^ (hash >>> 4);
為什么要經過這樣的運算呢？這就是HashMap的高明之處。先看個例子，一個十進制數32768(二進制1000 0000 0000 0000)，經過上述公式運算之后的結果是35080(二進制1000 1001 0000 1000)。看出來了嗎？或許這樣還看不出什么，再舉個數字61440(二進制1111 0000 0000 0000)，運算結果是65263(二進制1111 1110 1110 1111)，現在應該很明顯了，它的目的是讓“1”變的均勻一點，散列的本意就是要盡量均勻分布。那這樣有什么意義呢？看第3步。
3、 得到h之后，把h與HashMap的承載量（HashMap的默認承載量length是16，可以自動變長。在構造HashMap的時候也可以指定一個長 度。這個承載量就是上圖所描述的數組的長度。）進行邏輯與運算，即 h & (length-1)，這樣得到的結果就是一個比length小的正數，我們把這個值叫做index。其實這個index就是索引將要插入的值在數組中的 位置。第2步那個算法的意義就是希望能夠得出均勻的index，這是HashTable的改進，HashTable中的算法只是把key的 hashcode與length相除取余，即hash % length，這樣有可能會造成index分布不均勻。還有一點需要說明，HashMap的鍵可以為null，它的值是放在數組的第一個位置。
4、 我們用table[index]表示已經找到的元素需要存儲的位置。先判斷該位置上有沒有元素（這個元素是HashMap內部定義的一個類Entity， 基本結構它包含三個類，key，value和指向下一個Entity的next）,沒有的話就創建一個Entity<K,V>對象，在 table[index]位置上插入，這樣插入結束；如果有的話，通過鏈表的遍歷方式去逐個遍歷，看看有沒有已經存在的key，有的話用新的value替 換老的value；如果沒有，則在table[index]插入該Entity，把原來在table[index]位置上的Entity賦值給新的 Entity的next，這樣插入結束。
再回頭看看前面提到的為什么覆蓋了equals方法之后一定要覆蓋hashCode方法，很簡單，比如，String a = new String(“abc”);String b = new String(“abc”);如果不覆蓋hashCode的話，那么a和b的hashCode就會不同，把這兩個類當做key存到HashMap中的話就 會出現問題，就會和key的唯一性相矛盾。
HashMap取的過程也類似。太累了，不寫了。趕緊結束。
文中可能會有錯誤的地方請指出，謝謝！