0.前言談到數(shù)據(jù)結構，用的最多的，也是最基本的兩種，就是數(shù)組和鏈表。為什么我們講HashMap之前，要先講一下數(shù)組和鏈表呢？這要從他們兩個的特點說起。首先簡單地說一下數(shù)組，它的特點有很多：只能用來存儲同一類型的東西；長度是固定的，一旦聲明了長度屬性，就不能修改（數(shù)組的長度不等于數(shù)組內存儲的元素的個數(shù)）；數(shù)組在內存中的存儲是連續(xù)的；數(shù)組內的元素通過下標（索引）來引用。所以，我們可以得到這樣的結論：數(shù)組的查找和修改速度很快，因為可以直接通過下標來引用，但是增加和刪除上不是很方便，因為數(shù)組的長度不能修改。很多時候，當要存儲的元素超出數(shù)組的長度時，只能通過新建一個更長的新數(shù)組來代替原來的數(shù)組的方法。而鏈表作為和數(shù)組齊名的兩種最基本的數(shù)據(jù)結構之一，它在很多方面與數(shù)組類似，主要的區(qū)別是，鏈表是鏈式結構，元素在鏈表中的存儲是不連續(xù)的，它們之間通過指針依次連接。所以，鏈表的查找和刪除很慢，要從根節(jié)點開始依次查找，但是增加和刪除很方便，只需要改變指針指向的元素就可以了。基于它們兩個各有優(yōu)缺，我們的主角終于可以出場了，兼具數(shù)組與鏈表的優(yōu)點又巧妙地避開缺點的HashMap。1.正文在應用層面，HashMap就具有很大的優(yōu)點。它不像數(shù)組那樣只能用連續(xù)的整形數(shù)字作為索引，而是可以使用任意類型的對象。這些用作索引的對象稱為“鍵”（Key），每個“鍵”在表中對應一個“值”（Value），組成一個“鍵值對”（”Associates the specified value with the specified keyin this map.” ---源碼中的描述），可以更直觀的儲存所有類型的元素。在存儲時，HashMap里面的元素不是連續(xù)的，元素順序也和存放順序無關。而是根據(jù)要存儲的Key，先進行一步hash計算（” Computeskey.hashCode() and sPReads (XORs) higher bits of hashto lower. ”---源碼中描述的具體的hash計算過程），得到他在HashMap中的索引（散列）位置，然后將Key和Value的值存儲在該位置。簡單來說，HashMap是通過鍵的映射找到表中的某一個位置進行存儲的。因此，根據(jù)這個關系，在進行查找操作時，可以不用遍歷的方法直接通過計算得到索引位置（“Returnsthe value to which the specified key is mapped”---源碼中對get()方法的描述），彌補了數(shù)組和鏈表在時間上的缺陷。附：hash計算源碼：

static final int hash(Object key) {        int h;        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);}附：存儲元素的put方法源碼：
/**     * Associates the specified value with the specified key in this map.     * If the map previously contained a mapping for the key, the old     * value is replaced.     *     *...     */    public V put(K key, V value) {        return putVal(hash(key), key, value, false, true);//putVal()是具體進行存儲的方法，這里只是理解它首先進行了hash計算，具體的源碼在下面會講到。 }
附：取出元素的get方法源碼：
public Vget(Object key) {	Node<K,V> e;	return (e = getNode(hash(key), key)) == null ? null :e.value;// 取出元素時同樣先進行了hash計算}再深入一點，元素在HashMap中到底是如何存儲的？繼續(xù)參考源碼，我們找到上面出現(xiàn)過的putVal()方法。
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,                   boolean evict) {        Node<K,V>[] tab; Node<K,V> p; int n, i;        if ((tab = table) == null || (n = tab.length) == 0)            n = (tab = resize()).length;// 數(shù)組為空或者長度為零，增加數(shù)組的長度          if ((p = tab[i = (n - 1) & hash]) == null)            tab[i] = newNode(hash, key, value, null);//索引位置為空時，將新節(jié)點存到數(shù)組的該位置          else {            Node<K,V> e; K k;            if (p.hash == hash &&                ((k = p.key) == key || (key != null && key.equals(k))))                e = p;            else if (p instanceof TreeNode)                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);            else {                for (int binCount = 0; ; ++binCount) {                    if ((e = p.next) == null) {                        p.next = newNode(hash, key, value, null);                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st                            treeifyBin(tab, hash);                        break;                    }                    if (e.hash == hash &&                        ((k = e.key) == key || (key != null && key.equals(k))))                        break;                    p = e;                }            }            if (e != null) { // existing mapping for key                V oldValue = e.value;                if (!onlyIfAbsent || oldValue == null)                    e.value = value;                afterNodeaccess(e);                return oldValue;            }        }        ++modCount;        if (++size > threshold)            resize();//節(jié)點超出限度，調用resize()方法增加數(shù)組長度          afterNodeInsertion(evict);        return null; }這段代碼比較重要，所以我完整的拷貝了上來。我們可以發(fā)現(xiàn)，所有元素都會以節(jié)點形式進行存儲，其中包含了Key-Value等相關信息。當我們要存儲一個新的節(jié)點時，系統(tǒng)首先會檢查一個叫做table的對象，然后我們看到table的聲明和部分描述是這樣的：
 /**     * The table, initialized on first use, and resized as     * necessary. When allocated, length is always a power of two.     * (We also tolerate length zero in some Operations to allow     * bootstrapping mechanics that are currently not needed.)     */    transient Node<K,V>[] table;很明顯，這是一個用來存儲節(jié)點類型元素的數(shù)組。也就是說，在我們的HashMap里面，也用到了數(shù)組，而且會首先考慮將數(shù)據(jù)存儲在數(shù)組里面。我們經過hash計算得到了一個索引位置后，會檢查數(shù)組中該位置是否為空。如果該位置為空，會直接將新節(jié)點存儲在該位置；如果不為空，首先判斷索引位置處的舊節(jié)點與新節(jié)點的Key是否相同。如果相同，替換舊節(jié)點；如果不同，在該索引位置的基礎上，建立一個鏈表，將新節(jié)點存儲為這個鏈表的最后一個節(jié)點，在這之前也要保證原來鏈表中不存在相同Key的節(jié)點。可以參照下面的圖片進行理解。
（圖片來自·百度百科）由此可見，HashMap原則上是可以不斷存儲新的節(jié)點，但是隨著節(jié)點的增加，同一索引位置的節(jié)點太多，就不能發(fā)揮HashMap的優(yōu)勢。因此，HashMap必須解決的一個問題就是“哈希沖突”：在不斷的存儲過程中，對于兩個不同的Key，進過計算，對應同一個索引（散列）位置的現(xiàn)象，我們就叫做“哈希沖突（碰撞）”。這個問題在系統(tǒng)的HashMap中已經有了一些特定的解決方法，比如事先定義一個限度（threshold），每次添加新的節(jié)點之后，計算一下已存儲的節(jié)點數(shù)，如果超出這個限度，就調用一次resize()方法，增加數(shù)組的長度，并將原來的節(jié)點進行一次rehash()，重新進行存儲，來減小哈希沖突的影響。2.實現(xiàn)
最好的學習方法就是動手！為了加深理解，建議自己手寫一個簡單實現(xiàn)的HashMap，最好再與系統(tǒng)的比較一下，對比源碼進行修改。下面是我簡單實現(xiàn)的一個HashMap代碼，包括了存放元素、獲取元素、獲取元素個數(shù)、刪除元素最基本的幾項功能。 
public class myHashMap<K, V> {	int num = 0;// 存儲的元素的個數(shù)	Object[] data;// 初始化一個長度為6的數(shù)組	float rate = 0.75f;// 因子	public myHashMap() {		data = new Object[6];	}	public myHashMap(int size) {		Object[] data = new Object[size];	}	/**	 * 存放元素	 */	public void put(K key, V value) {		// 計算Hash值(索引)		int index = Hash(key);		// 創(chuàng)建節(jié)點		Node<K, V> node = new Node<K, V>(key, value);		// 判斷索引位置是否為空		if (data[index] == null) {			data[index] = node;			num++;		} else {			node.next = (Node<K, V>) data[index];			data[index] = node;			// 判斷是否為重復的鍵			// 若不重復 元素個數(shù)+1 ；			// 若重復 元素個數(shù)不變 （重復的沒有被覆蓋，只是排在了后面，不會被get到）			if (!node.key.equals(node.next.key))				num++;		}	}	/**	 * 哈希計算	 */	public int Hash(K key) {		int index = key.hashCode() % data.length;		// System.out.println(index);		return index;	}	/**	 * 獲取元素	 */	public V get(K key) {		// 計算Hash值(索引)		int index = Hash(key);		// 得到索引位置的節(jié)點		Node<K, V> node;		if (data[index] != null) {// 判斷索引位置是否存在節(jié)點			node = (Node<K, V>) data[index];// 若存在 找到key相等的節(jié)點并返回			while (!key.equals(node.key)) {				if (node.next != null)					node = node.next;				else{					return null;				} 			}		} else {// 若不存在 輸出一條語句 返回一個null			return null;		}		return node.value;	}	/**	 * 獲取元素個數(shù)	 */	public int size() {		return num;	}	/**	 * 刪除元素	 */	public void remove(K key) {		// 計算Hash值(索引)		int index = Hash(key);		// 得到索引位置的節(jié)點		Node<K, V> node = (Node<K, V>) data[index];		// 判斷索引位置是否存在節(jié)點		if (node != null) {// 若存在 判斷是不是第一個節(jié)點			if (key.equals(node.key)) {// 若是第一個節(jié)點 判斷是否只有根節(jié)點				if (node.next == null) {// 如果只有根節(jié)點 直接將根節(jié)點設為空					data[index] = null;					num--;				} else { // 如果有其他節(jié)點 直接將數(shù)組的索引位置指向第二個節(jié)點					data[index] = node.next;					num--;				}			} else {// 若不是第一個節(jié)點 判斷索引位置是否只有根節(jié)點				if (node.next == null)// 若索引位置只有根節(jié)點 且根節(jié)點的key不是要刪除的key 輸出一條提示語句					System.out.println("key不存在");				else {// 若索引位置有其他節(jié)點 則需要找到對應key的節(jié)點的上一個結點					while (node.next != null && !key.equals(node.next.key)) {						node = node.next;					}// 然后判斷對應key的節(jié)點是不是最后一個節(jié)點					if (node.next.next == null) {// 若是最后一個結點，將它的前一個結點的下一個節(jié)點指向null						node.next = null;						num--;					} else {// 若不是 將他的前一個節(jié)點指向他的后一個節(jié)點						node.next = node.next.next;						num--;					}				}			}		} else {// 若不存在 輸出一條提示語句			System.out.println("key不存在");		}	}} public class Node<K,V> {	K key;	V value;	Node<K,V> next;		public Node(K key, V value) {		super();		this.key = key;		this.value = value;	}} 3.總結這篇文章從初學者角度，簡單地介紹了一下HashMap的應用場景，存儲原理，以及簡單的源碼分析和實現(xiàn)的示范。在此基礎上，我們還可以進一步地分析系統(tǒng)的HashMap及與之相似的 HashTable, HashSet源代碼，了解一致性哈希、布隆過濾，尋找更有效的散列算法、rehash算法......通過拓展不斷加深理解。