HashMap源碼分析——實作簡易的hashmap

HashMap源碼分析

• jdk1.7 HashMap源碼分析
• • HashMap底層是怎樣實作的
  • 關于如何轉換資料結構的形态
  • 圖檔解釋
  • 根據思路實作源碼

jdk1.7 HashMap源碼分析

HashMap底層是怎樣實作的

HashMap 的底層是如何實作的？

jdk1.7以前是數組和連結清單 實作的

jdk1.8以後是 數組、連結清單、紅黑樹 實作的

一句話概括:

put的時候 會先通過雜湊演算法 算出 put進去的值的位置 再将值 以數組或連結清單或紅黑數的結構 設定到對應的位置。

僞代碼表示為

put(key,value)
{
  	  hash(key)
  	  index=hash&(n-1)
 }

例如  put進來一個 值  "a"   會先取值 "a" 的hashCode 然後 %15  這個時候可以算出一個索引位置 如 2
假設此時的資料結構是數組形式的 ， HashMap 會将 "a" 放入 element[2] 的位置
           

關于如何轉換資料結構的形态

有同學可能會問了 :不是說數組,連結清單。紅黑樹麼。 怎麼光有數組?
           

資料結構什麼時候從數組轉變成連結清單呢?

答案是: 當 發生hash碰撞的時候

即 現在有兩個key 他們的哈希值算出來的值 的 index位置都在 3 這個位置上 則代表此時發生了 哈希碰撞

此時 數組 3位置上 的資料将變為連結清單形式。 最開始存進去的值的 next 會指向 另一個key

圖檔解釋

以上圖檔為jdk7 hashMap的 put 與get 的實作方式

根據思路實作源碼

先定義一個Map接口

public interface Map<K,V> {
	
	V put(K k,V v); //定義一個 put方法
	V get(K k); //定義一個 get方法
	int size();  
	
	//定義一個 entry接口 友善周遊， java 裡面隻要是list 基本都實作了 entry接口
	interface Entry<K,V>{
		K getKey(); //傳回key
		V getValue(); //傳回value
		
	}
	
}
           

再定義實作類

public class HashMap<K, V>  implements Map<K, V>{
	
	private Entry<K,V>[] table=null;
	
	
	int size=0;
	
	
	public HashMap() {
		 table = new Entry[16];  //這裡是jdk1.7 的實作，  jdk1.8裡 是 懶漢式的。 隻有put的時候 才會真正的初始化
	}
	
	/***
	 * @see 通過key 進行hash
	 * 取模 16
	 * 放到數組中去 
	 * 判斷目前數組下标：
	 * 	沒有值  則直接存入
	 *  有值，  則 用連結清單 存入 next
	 * 
	 */
	@Override
	public V put(K k, V v) {
		int index=hash(k);
		Entry<K,V> entry=table[index];
		
		if(null==entry) {
			table[index]=new Entry<>(k, v, k.hashCode(), null); 
		}else {
			table[index]=new Entry<>(k, v, k.hashCode(), entry); 
		}
		
		size++;
		
		return v;
	}

	private int hash(K k) {
		int i=k.hashCode()%16;
		return Math.abs(i);
	}

	@Override
	public V get(K k) {
		if(size==0) return null;
		
		int index=hash(k);
		
		if(null==table[index]) return null;
		
		Entry<K,V> entry=findValue(k, table[index]);
		
		
		return entry==null?null:entry.getValue();
	}
	
	/***
	 * @see 遞歸擷取連結清單内的值，  
	 * @param k
	 * @param entry
	 * @return
	 */
	private  Entry<K, V> findValue(K k, Entry<K, V> entry) {
		if(entry.getKey().equals(k)||entry.getKey()==k) {
			return entry;
		}else {
			//判斷next是否為空
			if(entry.next!=null) {
				return findValue(k, entry.next);
			}
		}
		return null;
		
	}

	@Override
	public int size() {
		return size;
	}
	
	class Entry<K, V> implements Map.Entry<K, V>{
		K k;
		V v;
		int hash;
		Entry<K,V> next;
		
		
		
		
		public Entry(K k, V v, int hash,  Entry<K, V> next) {
			super();
			this.k = k;
			this.v = v;
			this.hash = hash;
			this.next = next; 
		}

		@Override
		public K getKey() {
			return k;
		}

		@Override
		public V getValue() {
			return v;
		}
		
	}

}