HashMap的內(nèi)部說明以及解釋

package com.sun.HashMap;/** * 注意幾點(diǎn)： * 1.每次擴(kuò)容為原來的二倍 * 2.擴(kuò)容的時候需要重新hash，因?yàn)樵卦跀?shù)組中的位置為hash*(table.length()-1) * 3.最大容量為2^30 * 4.容量必須是2的次冪 * 5.閾值threshold為LoadFactory*Capacity 即負(fù)載因子*容量 * @author:孫創(chuàng) * @date:2017年2月17日 */import java.util.Map;//鏈表型數(shù)組public class MyHashMap<K, V> {	public static void main(String[] args) {		MyHashMap<Integer, String> h = new MyHashMap<Integer, String>(3);		String put = h.put(1, "1sunchaung");		System.out.PRintln(put);		String put2 = h.put(2, "2zhangle");		System.out.println(put2);		String put3 = h.put(3, "3fan");		System.out.println(put3);		String put4 = h.put(4, "4pwng");		System.out.println(put4);		String put5 = h.put(5, "5pwng");		String put6 = h.put(6, "6pwng");		int size2 = h.size;		System.out.println(size2);		String remove = h.remove(4);		System.out.println(remove);	}	// 系統(tǒng)默認(rèn)初始容量，必須是2的n次冪，這是處于優(yōu)化考慮的	final static int DEFAULT_INITIAL_CAPACITY = 16;	// 設(shè)置系統(tǒng)默認(rèn)最大容量	final int MAXIMUM_CAPACITY = 1 << 30;	// 系統(tǒng)默認(rèn)負(fù)載因子，可在構(gòu)造函數(shù)中指定	final static float DEFAULT_LOAD_FACTOR = 0.75f;	// 用于存儲的表，長度可以調(diào)整，且必須是2的n次冪	transient Entry<K, V>[] table;	// 當(dāng)前的Map的key——value映射數(shù)，也就是當(dāng)前的size	transient int size;	// 閾（yu）值	int threshold;	// 哈希表的負(fù)載因子	final float loadFactor;	// map結(jié)構(gòu)被改變的次數(shù)	transient volatile int modCount;	public MyHashMap(int initialCapacity, float loadFactor) {		if (initialCapacity < 0)			throw new IllegalArgumentException("Illegal initial capacity: "					+ initialCapacity);		if (initialCapacity > MAXIMUM_CAPACITY)			initialCapacity = MAXIMUM_CAPACITY;		if (loadFactor <= 0 || Float.isNaN(loadFactor))			throw new IllegalArgumentException("Illegal load factor: "					+ loadFactor);		// 尋找一個2的k次冪capacity恰好大于initialcapacity		int capacity = 1;		while (capacity < initialCapacity) {			capacity <<= 1;		}		// 設(shè)置加載因子		this.loadFactor = loadFactor;		// 設(shè)置閾值為capacity*loadFactor，實(shí)際當(dāng)HashMap當(dāng)前size達(dá)到這個閾值的時候，HashMap就需要擴(kuò)大一倍		threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);		table = new Entry[capacity];		init();	}	public MyHashMap(int initialCapacity) {		this(initialCapacity, DEFAULT_LOAD_FACTOR);	}	public MyHashMap() {		this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);	}	public V get(Object key) {		if (key == null)			return getForNullKey();		Entry<K, V> entry = getEntry(key);		return null == entry ? null : entry.getValue();	}	private V getForNullKey() {		for (Entry<K, V> e = table[0]; e != null; e = e.next) {			if (e.key == null)				return e.value;		}		return null;	}	// 下面這兩個方法是一套hash算法，用來計算數(shù)組值 　第一個方法，得到哈希值，第二個方法，根據(jù)哈希值計算元素在數(shù)組中的位置。	final int hash(Object k) {		int h = k.hashCode();		h ^= (h >>> 20) ^ (h >>> 12);		return h ^ (h >>> 7) ^ (h >>> 4);	}	// "h&(length-1)"其實(shí)這里有點(diǎn)小巧妙，為什么是做與運(yùn)算？	// 首先我們要確定，HashMap的數(shù)組長度永遠(yuǎn)是偶數(shù)，所以length-1一定是一個奇數(shù)，	// 假設(shè)現(xiàn)在的長度是16，length-1就是15，對應(yīng)的二進(jìn)制是：1111。	// 假設(shè)有兩個元素，一個哈希值是8，二進(jìn)制是1000，一個哈希值是9，二進(jìn)制是1001。和1111與運(yùn)算后，	// 分別還是1000和1001，他們被分配在了數(shù)組的不同位置，這樣，哈希的分布非常均勻。	// 那么如果數(shù)組的長度是奇數(shù)，減去1后就是偶數(shù)了，偶數(shù)對應(yīng)的二進(jìn)制最低位一定是0，例如14二進(jìn)制1110。	// 對上面兩個數(shù)字分別與運(yùn)算，得到1000和1000。這樣，哈希值8和9的元素會被存儲在數(shù)組同一個位置的鏈表中。	// 在操作的時候，鏈表中的元素越多，效率就會越低，因?yàn)橐煌５膶︽湵硌h(huán)比較。	// 所以這個方法降低了哈希沖突的概率	//計算出元素在數(shù)組中的下標(biāo)	static int indexFor(int h, int length) {		return h & (length - 1);	}	// 在找到元素在數(shù)組中的索引位置以后，會循環(huán)遍歷table[i]所在的鏈表，如果找到key值與傳入的key值相同的對象，	// 則替換并返回原對象；若找不到，則通過addEntry(hash,key,value,i)添加新的對象	public V put(K key, V value) {		if (key == null)			return putForNullKey(value);		int hash = hash(key);		int i = indexFor(hash, table.length);		//如果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;// 有就覆蓋				return oldValue;			}		}		// 沒有找到的話重新創(chuàng)建		addEntry(hash, key, value, i);		return null;	}	private V putForNullKey(V value) {		for (Entry<K, V> e = table[0]; e != null; e = e.next) {			if (e.key == null) {				V oldValue = e.value;				e.value = value;				return oldValue;			}		}		addEntry(0, null, value, 0);		return null;	}	// 以上過程就是新建一個Entry對象，并放在當(dāng)前位置的Entry鏈表的頭部。然后判斷size是否達(dá)到了需要擴(kuò)容的界限并讓size	// 增加1，如果達(dá)到了擴(kuò)容的界限則調(diào)用resize(int capacity)方法。	void addEntry(int hash, K key, V value, int bucketIndex) {		Entry<K, V> e = table[bucketIndex];// 該位置原來的鏈表		table[bucketIndex] = new Entry<K, V>(hash, key, value, e);// 新元素的next為原來的鏈表值		if (size++ >= threshold)// 如果容量>=（capacity * loadFactor）的話，擴(kuò)容			resize(2 * table.length);// 數(shù)組擴(kuò)容，為原來容量的二倍	}	// 擴(kuò)容并且將所有的元素重新哈希，因?yàn)槿萘吭龃?，每個元素的hash值和位置都發(fā)生改變	void resize(int newCapacity) {		Entry[] oldTable = table;		int oldCapacity = oldTable.length;		if (oldCapacity == MAXIMUM_CAPACITY) {			threshold = Integer.MAX_VALUE;			return;		}		Entry[] newTable = new Entry[newCapacity];		//將所有的元素重新hash		transfer(newTable);		table = newTable;		threshold = (int) Math.min(newCapacity * loadFactor,				MAXIMUM_CAPACITY + 1);	}	// tranfer方法將所有的元素重新哈希，因?yàn)樾碌娜萘孔兇螅悦總€元素的位置改變。	void transfer(Entry[] newTable) {		// 保留原數(shù)組的引用到src中，		Entry[] src = table;		// 新容量使新數(shù)組的長度		int newCapacity = newTable.length;		// 遍歷原數(shù)組		for (int j = 0; j < src.length; j++) {			// 獲取元素e			Entry<K, V> e = src[j];			if (e != null) {				// 將原數(shù)組中的元素置為null				src[j] = null;				// 遍歷原數(shù)組中j位置指向的鏈表				do {					Entry<K, V> next = e.next;					// 根據(jù)新的容量計算e在新數(shù)組中的位置					int i = indexFor(e.hash, newCapacity);					// 將e插入到newTable[i]指向的鏈表的頭部					e.next = newTable[i];					newTable[i] = e;					e = next;				} while (e != null);			}		}	}	private void init() {	}	final Entry<K, V> getEntry(Object key) {		int hash = (key == null) ? 0 : hash(key);		for (Entry<K, V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) {			Object k;			if (e.hash == hash					&& ((k = e.key) == key || (key != null && key.equals(k))))				return e;		}		return null;	}	public V remove(Object key) {		Entry<K, V> e = removeEntryForKey(key);		return (e == null ? null : e.value);	}	final Entry<K, V> removeEntryForKey(Object key) {		int hash = (key == null) ? 0 : hash(key);		int i = indexFor(hash, table.length);		Entry<K, V> prev = table[i];		Entry<K, V> e = prev;		while (e != null) {			Entry<K, V> next = e.next;			Object k;			// 如果找到			if (e.hash == hash					&& ((k = e.key) == key || (key != null && key.equals(k)))) {				size--;				if (prev == e)					table[i] = next;				else					prev.next = next;// 節(jié)點(diǎn)前一個的下一個等于節(jié)點(diǎn)的下一個				return e;			}			// 如果沒找到			prev = e;			e = next;		}		return e;	}	private static class Entry<K, V> implements Map.Entry<K, V> {		final K key;		V value;		Entry<K, V> next;		int hash;		Entry(int h, K k, V v, Entry<K, V> n) {			value = v;			key = k;			next = n;			hash = h;		}		@Override		public K getKey() {			return key;		}		@Override		public V getValue() {			return value;		}		@Override		public V setValue(V newvalue) {			V oldvalue = value;			value = newvalue;			return oldvalue;		}		public final boolean equals(Object o) {			if (!(o instanceof Map.Entry))				return false;			Map.Entry e = (Map.Entry) o;			Object k1 = getKey();			Object k2 = e.getKey();			if (k1 == k2 || (k1 != null && k1.equals(k2))) {				Object v1 = getValue();				Object v2 = e.getValue();				if (v1 == v2 || (v1 != null && v1.equals(v2)))					return true;			}			return false;		}		public final int hashCode() {			return (key == null ? 0 : key.hashCode())					^ (value == null ? 0 : value.hashCode());		}		public final String toString() {			return getKey() + "=" + getValue();		}	}}