hashmap可以說是java中最常用的集合類架構之一，是java語言中非常典型的資料結構，我們總會在不經意間用到它，很大程度上友善了我們日常
開發。在很多java的筆試題中也會被問到，最常見的，“hashmap和hashtable有什麼差別？”，這也不是三言兩語能說清楚的，這種筆試題就
是考察你來筆試之前有沒有複習功課，随便來個快餐式的複習就能給出簡單的答案。
hashmap計劃寫兩篇文章，一篇是hashmap工作原理，也就是本文，另一篇是多線程下的hashmap會引發的問題。這一年文章寫的有點少，工
作上很忙，自己業餘時間也做點東西，就把部落格的時間占用了，以前是力保一周一篇文章，有點給自己任務的意思，搞的自己很累，文章品質也不高，有時候寫技術
文章也是需要靈感的，為了舉一個例子可能要絞盡腦汁，為了一段代碼可能要驗證好多次，現在想通了，有靈感再寫，需要一定的積累，才能把自己了解的知識點總
結歸納成文章。
言歸正傳，了解hashmap之前，我們需要知道object類的兩個方法hashcode和equals，我們先來看一下這兩個方法的預設實作：
/** jni，調用底層其它語言實作 */
public native int hashcode();
/** 預設同==，直接比較對象 */
public boolean equals(object obj) {
return (this == obj);
}
equals方法我們太熟悉了，我們經常用于字元串比較，string類中重寫了equals方法，比較的是字元串值，看一下源碼實作：
public boolean equals(object anobject) {
if (this == anobject) {
return true;
}
if (anobject instanceof string) {
string anotherstring = (string) anobject;
int n = value.length;
if (n == anotherstring.value.length) {
char v1[] = value;
char v2[] = anotherstring.value;
int i = 0;
// 逐個判斷字元是否相等
while (n-- != 0) {
if (v1[i] != v2[i])
return false;
i++;
}
return true;
}
return false;
重寫equals要滿足幾個條件：
自反性：對于任何非空引用值 x，x.equals(x) 都應傳回 true。
對稱性：對于任何非空引用值 x 和 y，當且僅當 y.equals(x) 傳回 true 時，x.equals(y) 才應傳回 true。
傳遞性：對于任何非空引用值 x、y 和 z，如果 x.equals(y) 傳回 true，并且 y.equals(z) 傳回 true，那麼 x.equals(z) 應傳回 true。
一緻性：對于任何非空引用值 x 和 y，多次調用 x.equals(y) 始終傳回 true 或始終傳回 false，前提是對象上 equals 比較中所用的資訊沒有被修改。
對于任何非空引用值 x，x.equals(null) 都應傳回 false。
object 類的 equals 方法實作對象上差别可能性最大的相等關系；即，對于任何非空引用值 x 和 y，當且僅當 x
和 y 引用同一個對象時，此方法才傳回 true（x == y 具有值 true）。 當此方法被重寫時，通常有必要重寫 hashcode
方法，以維護 hashcode 方法的正常協定，該協定聲明相等對象必須具有相等的哈希碼。
下面來說說hashcode方法，這個方法我們平時通常是用不到的，它是為哈希家族的集合類架構(hashmap、hashset、hashtable)提供服務，hashcode 的正常協定是：
在 java 應用程式執行期間，在同一對象上多次調用 hashcode 方法時，必須一緻地傳回相同的整數，前提是對象上 equals 比較中所用的資訊沒有被修改。從某一應用程式的一次執行到同一應用程式的另一次執行，該整數無需保持一緻。
如果根據 equals(object) 方法，兩個對象是相等的，那麼在兩個對象中的每個對象上調用 hashcode 方法都必須生成相同的整數結果。
以
下情況不 是必需的：如果根據 equals(java.lang.object) 方法，兩個對象不相等，那麼在兩個對象中的任一對象上調用
hashcode 方法必定會生成不同的整數結果。但是，程式員應該知道，為不相等的對象生成不同整數結果可以提高哈希表的性能。
當我們看到實作這兩個方法有這麼多要求時，立刻淩亂了，幸好有ide來幫助我們，eclipse中可以通過快捷鍵alt+shift+s調出快捷菜單，
選擇generate hashcode() and
equals()，根據業務需求，勾選需要生成的屬性，确定之後，這兩個方法就生成好了，我們通常需要在javabean對象中重寫這兩個方法。
好了，這兩個方法介紹完之後，我們回到hashmap。hashmap是最常用的集合類架構之一，它實作了map接口，是以存儲的元素也是鍵值對映射的
結構，并允許使用null值和null鍵，其内元素是無序的，如果要保證有序，可以使用linkedhashmap。hashmap是線程不安全的，下篇
文章會讨論。hashmap的類結構如下：
<dl></dl>
<dt></dt>
所有已實作的接口：
<dd></dd>
直接已知子類：
hashmap中我們最長用的就是put(k, v)和get(k)。我們都知道，hashmap的k值是唯一的，那如何保證唯一性呢？我們首先想到的是用equals比較，沒錯，這樣可以實作，但随着内部元素的增多，put和get的效率将越來越低，這裡的時間複雜度是o(n)，假如有1000個元素，put時需要比較1000次。實際上，hashmap很少會用到equals方法，因為其内通過一個哈希表管理所有元素，哈希是通過hash單詞音譯過來的，也可以稱為散清單，雜湊演算法可以快速的存取元素，當我們調用put存值時，hashmap首先會調用k的hashcode方法，擷取哈希碼，通過哈希碼快速找到某個存放位置，這個位置可以被稱之為bucketindex，通過上面所述hashcode的協定可以知道，如果hashcode不同，equals一定為false，如果hashcode相同，equals不一定為true。是以理論上，hashcode可能存在沖突的情況，有個專業名詞叫碰撞，當碰撞發生時，計算出的bucketindex也是相同的，這時會取到bucketindex位置已存儲的元素，最終通過equals來比較，equals方法就是哈希碼碰撞時才會執行的方法，是以前面說hashmap很少會用到equals。hashmap通過hashcode和equals最終判斷出k是否已存在，如果已存在，則使用新v值替換舊v值，并傳回舊v值，如果不存在
，則存放新的鍵值對<k, v>到bucketindex位置。文字描述有些亂，通過下面的流程圖來梳理一下整個put過程。
現在我們知道，執行put方法後，最終hashmap的存儲結構會有這三種情況，情形3是最少發生的，哈希碼發生碰撞屬于小機率事件。到目前為止，我們了解了兩件事：
hashmap通過鍵的hashcode來快速的存取元素。
當不同的對象hashcode發生碰撞時，hashmap通過單連結清單來解決，将新元素加傳入連結表表頭，通過next指向原有的元素。單連結清單在java中的實作就是對象的引用(複合)。
來鑒賞一下hashmap中put方法源碼：
public v put(k key, v value) {
// 處理key為null，hashmap允許key和value為null
if (key == null)
return putfornullkey(value);
// 得到key的哈希碼
int hash = hash(key);
// 通過哈希碼計算出bucketindex
int i = indexfor(hash, table.length);
// 取出bucketindex位置上的元素，并循環單連結清單，判斷key是否已存在
for (entry<k,v> e = table[i]; e != null; e = e.next) {
object k;
// 哈希碼相同并且對象相同時
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
// 新值替換舊值，并傳回舊值
v oldvalue = e.value;
e.value = value;
e.recordaccess(this);
return oldvalue;
// key不存在時，加入新元素
modcount++;
addentry(hash, key, value, i);
return null;
到這裡，我們了解了hashmap工作原理的一部分，那還有另一部分，如，加載因子及rehash，hashmap通常的使用規則，多線程并發時hashmap存在的問題等等，這些會留在下一章說明。