天天看點
傳回

Java源碼閱讀之IdentityHashMap類定義類屬性構造函數方法相等性比較HashCode

Java源碼閱讀之IdentityHashMap

  • 類定義
  • 類屬性
  • 構造函數
  • 方法
  • 相等性比較
  • HashCode

在java中，IdentityHashMap是唯一允許出現相等鍵的map，因為在IdentityHashMap中判斷鍵相等是判斷引用相等，而在其他map中判斷鍵相等是根據值相等來進行判斷；

類定義

類屬性 

// 預設的容量大小，當采用裝載因子2/3時，map的最大size為21
private static final int DEFAULT_CAPACITY = 32;

// 最小的初始容量
private static final int MINIMUN_CAPACITY = 4;

// 最大的map容量
private static final int MAXIMUM_CAPACITY = 1 << 29;

// 用于存儲鍵值對的數組
transient Object[] table;

// map中的鍵值對數量
int size;

transient int modCount;

static final Object NULL_KEY = new Object();

構造函數 

// 用預設初始容量32，和預設裝載因子2/3建立map
public IdentityHashMap(){
	init(DEFAULT_CAPACITY);
}

// 使用期望能夠裝填的鍵值對的數量來進行map的建立
// 這裡的expectedMaxSize就相當于HashMap中的threshold
// IdentityHashMap的預設裝載因子為2/3
public IdentityHashMap(int expectedMaxSize){
	if(expectedMaxSize < 0){
		throw new IllegalArgumentException("expectedMaxSize is negative : " + expectedMaxSize);
	}
	// 用能滿足expecedMaxSize的最小容量初始化map，容量必須為2的幂次
	init(capacity(expectedMaxSize));
}

public IdentityHashMap(Map<? extends K, ? extends V> m){
	this((int)((1 + m.size()) * 1.1));
	putAll(m);
}

方法 

// 使用期望的能存儲的最大數量的鍵值對數，和預設的裝載因子2/3計算出能滿足的最小的2的幂次的容量
private static int capacity(int expectedMaxSize){
	return (exceptedMaxSize > MAXIMUM_CAPACITY/3 ? MAXIMUN_CAPACITY:
			(exceptedMaxSize <= 2 * MINIMUM_CAPACITY/3) ? MINIMUM_CAPACITY :
			Integer.highestOneBit(expectedMaxSize + (expectedMaxSize << 1)));
}

// 對identityHashmap進行初始化
private void init(int initCapacity){
	table = new Object[initCapacity * 2];
}

// 傳回指定鍵的索引位置
private static int hash(Object x, int length){
	int h = System.identityHashCode(x);
	return ((h << 1) - (h << 8)) & (length - 1);
}

// 查找下一個key的索引，IdentityHashMap采用的線性探測法解決沖突
private static int nextKeyIndex(int i, int len){
	return (i + 2 < len ? i + 2 : 0);
}

// 向map中插入元素
public V put(Objcet key, Object value){
	final Object k = maskNull(key);

	retryAfterResize:for(;;){
		final Object[] tab = table;
		final int len = tab.length;
		int i = hash(key, len);
		// 如果鍵已經存在，則替換舊值
		for(Object item; (item = tab[i]) != null; i = nextKeyIndex(i, len)){
			if(item == k){
				V oldValue = (V) tab[i+1];
				tab[i+1] = value;
				return oldValue;
			}
		}
		final int s = size + 1;
		// 當容量達到門檻值，則進行擴容
		if((s + (s << 1)) > len && resize(len)){
			continue retryAfterResize;
		}

		modCount++;
		tab[i] = k;
		tab[i+1] = value;
		size = s;
		return null;
	}
}

public V get(Object key){
	Object k = maskUnll(key);
	Object[] tab = table;
	int len = tab.length;
	int i = hash(k, len);
	
	while(true){
		Object item = tab[i];
		if(item == k){
			return (V) tab[i+1];
		}
		if(item == null){
			return null;
		}
		i = nextKeyIndex(i, len);
	}
}

// 查找map中是否有指定的鍵
public boolean containsKey(Object key){
	Object k = maskUnll(key);
	Object[] tab = table;
	int len = tab.length;
	int i = hash(k, len);
	while(true){
		Object item = tab[i];
		if(item == key){
			return true;
		}
		if(item == null){
			return false;
		}
		i = nextKeyIndex(i, len);
	}
}

// 查找map中是否有指定的值
public boolean containsValue(Object value){
	// 按照存儲結構，值隻能從索引位置為1的地方開始存儲
	// 周遊一遍map查詢是否有指定的值存在
	for(int i = 1; i < table.length; i+=2){
		// 查找到指定的值且有對應的鍵關聯
		if(table[i] == value && table[i-1] != null){
			return true;
		}
	}
	return false;
}

// 查找map中是否存在指定的鍵值對
private boolean containsMapping(Object key, Object value){
	final Object k = maskNull(key);
	Object[] tab = table;
	int len = tab.length;
	int i = hash(k, len);
	while(true){
		Object item = tab[i];
		if(item == k){
			return value == tab[i+1]
		}
		if(item == null){
			return false;
		}
		i = nextKeyIndex(i, len);
	}
}

// 使用新容量對容器進行擴容
public boolean resize(int newCapacity){
	int newLength = 2 * newCapacity;

	Object[] oldTable = table;
	int oldLength = oldTable.length;
	if(oldLength == 2 * MAXIMUM_CAPACITY){
		// 已經達到最大容量，不能再繼續擴容了
		if(size == MAXIMUM_CAPACITY - 1){
			// 記憶體耗盡
			throw new IllegalStateException("Capacity exhausted.");
		}
		return false;
	}
	if(oldLength >= newLength){
		return false;
	}
	Object[] newTable = new Object[newLength];
	for(int i = 0; i < oldLength; i += 2){
		Object key = oldTable[i];
		if(key != null){
			Objcet value = oldTable[i + 1];
			oldTable[i] = null;
			oldTable[i + 1] = null;
			int j = hash(key, newLength);
			while(newTable[j] != null)
				j = nextKeyIndex(j, newLength);
			newTable[j] = key;
			newTable[j + 1] = value;
		}
	}
	table = newTable;
	return true;
}

// 将給定map中的所有鍵值對添加到目前map中，如果有重複的鍵，則用給定的map中的鍵值對替換目前map中的鍵值對
public void putAll(Map<? extends K, ? extends V> m){
	int n = m.size();
	if(n == 0){
		return;
	}
	if(n > size){
		resize(capacity(n));
	}
	for(Map.Entry<K,V> entry : m.entrySet()){
		put(entry.getKey(), entry.getValue());
	}
}

// 根據指定的鍵來删除鍵值對
// 如果鍵key存在則删除鍵值對，并傳回關聯的值
// 如果鍵key不存在則傳回null
public V remove(Object key){
	Object k = maskNull(key);
	Object[] tab = table;
	int len = tab.length;
	int i = hash(k, len);

	while(true){
		Object item = tab[i];
		if(item == k){
			modCount ++;
			size --;
			V oldValue = (V) tab[i + 1];
			tab[i] = null;
			tab[i + 1] = null;
			closeDeletion(i);
			return oldValue;
		}
		if(item == null){
			// 沒有查找到指定的值
			return null;
		}
		i = nextKeyIndex(i, len);
	}
}

// 删除之後，需要将具有相同hash值的後續鍵值對向前移動
private void closeDeletion(int d){
	Object[] tab = table;
	int len = tab.length;
	
	Object item;
	for(int i = nextKeyIndex(d, len); (item = tab[i]) != null; i = nextKeyIndex(i, len)){
		// 計算後續鍵值對的hash值
		int r = hash(item, len);
		if((i < r && (r <= d || d <= i)) || (r <= d && d <= i)){
			tab[d] = tab[i];
			tab[d + 1] = tab[i + 1];
			tab[i] = null;
			tab[i + 1] = null;
			d = i;
		}	
	}
}

// 清空map
public void clear(){
	modCount ++;
	Object[] tab = table;
	for(int i = 0; i < tab.length; i ++){
		tab[i] = null;
	}
	size = 0;
}

相等性比較 

public boolean equals(Object o){
	if(o == this){
		return true;
	}else if(o instanceof IdentityHashMap){
		IdentityHashMap<?,?> m = (IdentityHashMap<?,?>)o;
		if(m.size() != size){
			return false;
		}

		Object[] tab = m.table;
		for(int i = 0; i < tab.length; i += 2){
			Objcet k = tab[i];
			if(k != null && !containsMapping(k, tab[i + 1])){
				return false;
			}
		}
		return true;
	}else if(o instanceof Map){
		Map<?,?> m = (Map<?,?>)o;
		return entrySet().equals(o.entrySet());
	}else{
		return false;
	}
}

HashCode 

public int hashCode(){
	int result = 0;
	Object[] tab = table;
	for(int i = 0; i < tab.length; i ++){
		Object key = tab[i];
		if(key != null){
			Object k = unmaskNull(key);
			result += System.identityHashCode(k) ^ System.identityHashCode(tab[i+1]);
		}
	}
	return result;
}
Java API源碼閱讀 java api 源碼 IdentityHashMap
上一篇: Java源碼閱讀之StringBuffer類定義類屬性構造函數方法
下一篇: HashMap源碼閱讀021、前言2、解答3、提問4、測試與分析5、結論

繼續閱讀