一. 概述
??IdentityHashMap利用Hash表來(lái)實(shí)現(xiàn)Map接口席揽，比較鍵（和值）時(shí)使用引用相等性代替對(duì)象相等性谓厘，也就是說(shuō)使用 == 而不是使用 equals幌羞。
- 比如對(duì)于要保存的key，k1和k2竟稳，當(dāng)且僅當(dāng)k1== k2的時(shí)候属桦，IdentityHashMap才會(huì)相等熊痴，而對(duì)于HashMap來(lái)說(shuō)，相等的條件則是：(k1==null ? k2==null : k1.equals(k2))聂宾。
- IdentityHashMap不是Map的通用實(shí)現(xiàn)果善，它有意違反了Map的常規(guī)協(xié)定。并且IdentityHashMap允許key和value都為null系谐。
- 同HashMap巾陕，IdentityHashMap也是無(wú)序的，并且該類(lèi)不是線(xiàn)程安全的蔚鸥，如果要使之線(xiàn)程安全惜论，可以調(diào)用Collections.synchronizedMap(new IdentityHashMap(...))方法來(lái)實(shí)現(xiàn)许赃。
我們?cè)偻ㄟ^(guò)一個(gè)例子來(lái)幫我們進(jìn)行分析：
public static void main(String[] args) {
IdentityHashMap<String ,Integer> identityHashMap = new IdentityHashMap<>();
identityHashMap.put(new String("A"), 1);
identityHashMap.put(new String("B"), 2);
identityHashMap.put(new String("A"), 3);
System.out.println(identityHashMap);
}
打又古纭：
{B=2, A=1, A=3}
1. 屬性
public class IdentityHashMap<K,V>
extends AbstractMap<K,V>
implements Map<K,V>, java.io.Serializable, Cloneable
{
/**
* 默認(rèn)容量大小
*/
private static final int DEFAULT_CAPACITY = 32;
/**
* 最小容量
*/
private static final int MINIMUM_CAPACITY = 4;
/**
* 最大容量
* 事實(shí)上，該Map最多只能有MAXIMUM_CAPACITY-1個(gè)元素混聊，因?yàn)樗仨氂幸粋€(gè)key等于null的位置弹谁，
* 這是為了避免get,put,remove方法的無(wú)限循環(huán)
*/
private static final int MAXIMUM_CAPACITY = 1 << 29;
/**
* 用于存儲(chǔ)實(shí)際元素的數(shù)組
*/
transient Object[] table; // non-private to simplify nested class access
/**
* map的大小
*/
int size;
/**
* 結(jié)構(gòu)性修改
*/
transient int modCount;
/**
* key為null的處理
*/
static final Object NULL_KEY = new Object();
}
可以看到，IdentityHashMap底層是使用了一個(gè)數(shù)組來(lái)保存數(shù)據(jù)句喜。
2. 方法
put方法
- put的時(shí)候先通過(guò)引用是否相等判斷key是不是已經(jīng)在表中存在预愤，如果存在更新oldValue為新的value，如果元素個(gè)數(shù)達(dá)到閾值咳胃，擴(kuò)容處理植康，然后再找合適的位置放置key和value。
- put比較有意思的一點(diǎn)就是展懈，在數(shù)組的i索引處存key销睁，而緊挨著i的i+1處存value，并且由于hash方法的原因存崖，key所對(duì)應(yīng)的index全是偶數(shù)冻记，自然i+1就是奇數(shù)了。這也說(shuō)明了另一點(diǎn)来惧，數(shù)組初始化的時(shí)候冗栗，數(shù)組的長(zhǎng)度被定義為默認(rèn)容量的2倍，因?yàn)閿?shù)組元素的每次保存是都占了數(shù)組的兩個(gè)位置供搀。
- put的擴(kuò)容條件是當(dāng)存放的數(shù)組達(dá)到數(shù)組長(zhǎng)度的1/3的時(shí)候隅居，就需要擴(kuò)容。
public V put(K key, V value) {
// key為null處理
final Object k = maskNull(key);
// 使用了jdk原先的這種標(biāo)簽來(lái)進(jìn)行循環(huán)跳轉(zhuǎn)
retryAfterResize: for (;;) {
final Object[] tab = table;
final int len = tab.length;
int i = hash(k, len);
for (Object item; (item = tab[i]) != null;
i = nextKeyIndex(i, len)) {
// 如果key與數(shù)組原有的key相等葛虐，使用新的value代替舊的value胎源，并返回舊的value
if (item == k) {
@SuppressWarnings("unchecked")
V oldValue = (V) tab[i + 1];
tab[i + 1] = value;
return oldValue;
}
}
// size加1
final int s = size + 1;
// Use optimized form of 3 * s.
// Next capacity is len, 2 * current capacity.
// 如果3*size 大于數(shù)組的length，則進(jìn)行擴(kuò)容挡闰，這里計(jì)算要注意乒融，+的優(yōu)先級(jí)是高于>號(hào)的掰盘，所以先算乘以3，再進(jìn)行比較赞季。
if (s + (s << 1) > len && resize(len))
// 擴(kuò)容后重新計(jì)算元素的值愧捕，尋找合適的位置進(jìn)行存放
continue retryAfterResize;
modCount++;
tab[i] = k;
tab[i + 1] = value;
// 更新size
size = s;
return null;
}
}
get方法
??get方法則比較簡(jiǎn)單，根據(jù)key獲取數(shù)組的索引申钩，然后對(duì)象比較引用次绘，基本類(lèi)型比較數(shù)據(jù)是否相等即可。如果i處找到對(duì)象撒遣，說(shuō)明i+1處就是索引對(duì)應(yīng)的value邮偎，這也解釋了初始化數(shù)組的時(shí)候2倍長(zhǎng)度的原因了。
public V get(Object key) {
Object k = maskNull(key);
Object[] tab = table;
int len = tab.length;
// 獲取元素的index
int i = hash(k, len);
while (true) {
Object item = tab[i];
// 判斷是否相等义黎，引用是否相等
if (item == k)
// 獲取下一個(gè)索引位置的value
return (V) tab[i + 1];
// 獲取不到禾进，返回null
if (item == null)
return null;
// 遍歷下一個(gè)key的索引，這里解決散列沖突的辦法是若沖突廉涕，則往后尋找空閑區(qū)域
i = nextKeyIndex(i, len);
}
}
nextKeyIndex方法
??該方法用于解決hash沖突時(shí)泻云，取下一個(gè)位置進(jìn)行判斷，put的時(shí)候也是同樣的做法狐蜕。至于往后移2個(gè)單位宠纯，也是因?yàn)閜ut的時(shí)候一個(gè)元素的key和value各占一個(gè)位置嘍。
private static int nextKeyIndex(int i, int len) {
// 往后移兩個(gè)單位
return (i + 2 < len ? i + 2 : 0);
}
containsValue方法
從循環(huán)遍歷來(lái)看层释，也能得出數(shù)組偶數(shù)索引處存的全是元素的key婆瓜，而奇數(shù)位置存的是元素的value。
public boolean containsValue(Object value) {
Object[] tab = table;
for (int i = 1; i < tab.length; i += 2)
if (tab[i] == value && tab[i - 1] != null)
return true;
return false;
}
capacity方法
/**
* 該值計(jì)算的是最小的大于expectedMaxSize的二次冪的值贡羔，
* 比如expectedMaxSize是5廉白，返回的就是8
*/
private static int capacity(int expectedMaxSize) {
// assert expectedMaxSize >= 0;
return
(expectedMaxSize > MAXIMUM_CAPACITY / 3) ? MAXIMUM_CAPACITY :
(expectedMaxSize <= 2 * MINIMUM_CAPACITY / 3) ? MINIMUM_CAPACITY :
Integer.highestOneBit(expectedMaxSize + (expectedMaxSize << 1));
}
remove方法
public V remove(Object key) {
Object k = maskNull(key);
Object[] tab = table;
int len = tab.length;
// 計(jì)算hash
int i = hash(k, len);
while (true) {
Object item = tab[i];
// 查找引用相等的
if (item == k) {
modCount++;
size--;
@SuppressWarnings("unchecked")
V oldValue = (V) tab[i + 1];
tab[i + 1] = null;
tab[i] = null;
// 刪除該元素后，需要把原來(lái)有沖突往后移的元素移到前面來(lái)
closeDeletion(i);
return oldValue;
}
if (item == null)
return null;
i = nextKeyIndex(i, len);
}
}
resize方法
private boolean resize(int newCapacity) {
// assert (newCapacity & -newCapacity) == newCapacity; // power of 2
int newLength = newCapacity * 2;
// 舊的數(shù)組
Object[] oldTable = table;
int oldLength = oldTable.length;
// 舊數(shù)組的長(zhǎng)度如果是最大值的2倍
if (oldLength == 2 * MAXIMUM_CAPACITY) { // can't expand any further
// 并且如果原先元素的個(gè)數(shù)是最大容量-1治力，無(wú)法擴(kuò)容蒙秒，拋異常
if (size == MAXIMUM_CAPACITY - 1)
throw new IllegalStateException("Capacity exhausted.");
return false;
}
// 如果舊的數(shù)組容量大于新數(shù)組容量
if (oldLength >= newLength)
return false;
// 新數(shù)組
Object[] newTable = new Object[newLength];
// 遍歷舊數(shù)組
for (int j = 0; j < oldLength; j += 2) {
Object key = oldTable[j];
// 舊數(shù)組的key不為null，重新獲取index后放到新的數(shù)組里
if (key != null) {
Object value = oldTable[j+1];
oldTable[j] = null;
oldTable[j+1] = null;
int i = hash(key, newLength);
while (newTable[i] != null)
i = nextKeyIndex(i, newLength);
newTable[i] = key;
newTable[i + 1] = value;
}
}
// 將新數(shù)組重新指向table
table = newTable;
return true;
}
equals和hashCode方法
- IdentityHashMap重寫(xiě)了equals和hashcode方法宵统，不過(guò)需要注意的是hashCode方法并不是借助Object的hashCode來(lái)實(shí)現(xiàn)的践磅，而是通過(guò)System.identityHashCode方法來(lái)實(shí)現(xiàn)的鸠项。
- 并且，hashCode的生成是與key和value都有關(guān)系的，這就間接保證了key和value這對(duì)數(shù)據(jù)具備了唯一的hash值蝌借。同時(shí)通過(guò)重寫(xiě)equals方法羽资，判定只有key值全等情況下才會(huì)判斷key值相等角撞。這就是IdentityHashMap與普通HashMap不同的關(guān)鍵所在哲鸳。
public int hashCode() {
int result = 0;
Object[] tab = table;
for (int i = 0; i < tab.length; i +=2) {
Object key = tab[i];
if (key != null) {
Object k = unmaskNull(key);
// 最終hashCode的生成與key和value都有關(guān)系
result += System.identityHashCode(k) ^
System.identityHashCode(tab[i + 1]);
}
}
return result;
}
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) {
Object 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(m.entrySet());
} else {
return false; // o is not a Map
}
}
二、總結(jié)
- IdentityHashMap的實(shí)現(xiàn)不同于HashMap涤伐，雖然也是數(shù)組馒胆，不過(guò)IdentityHashMap中沒(méi)有用到鏈表缨称，解決沖突的方式是計(jì)算下一個(gè)有效索引，并且將數(shù)據(jù)key和value緊挨著存在map中祝迂，即table[i]=key睦尽，那么table[i+1]=value。
- IdentityHashMap的hash的計(jì)算沒(méi)有使用Object的hashCode方法型雳，而是使用的System.identityHashCode方法当凡，這是Object.hashCode方法根據(jù)對(duì)象的內(nèi)存地址來(lái)計(jì)算散列碼時(shí)所使用的方式。
- 其實(shí)有的時(shí)候我們常說(shuō)的IdentityHashMap能保存重復(fù)的key是一種不太恰當(dāng)?shù)恼f(shuō)法纠俭，因?yàn)镮dentityHashMap的==操作是比較的內(nèi)存地址沿量，如果不是指向同一塊內(nèi)存，那這時(shí)候才可以保存相同的數(shù)據(jù)冤荆。
// 像這種情況朴则，就不能保存相同的key
IdentityHashMap<String, Integer> map = new IdentityHashMap<>();
map.put("A", 1);
map.put("A", 3);
System.out.println(map);
三、問(wèn)題
1）有一個(gè)問(wèn)題沒(méi)想清楚匙赞，就是計(jì)算index的時(shí)候佛掖，返回的結(jié)果一定是偶數(shù)么妖碉？有時(shí)間了再仔細(xì)想想 (代碼如下)：
private static int hash(Object x, int length) {
int h = System.identityHashCode(x);
// Multiply by -127, and left-shift to use least bit as part of hash
return ((h << 1) - (h << 8)) & (length - 1);
}
2）還有一個(gè)問(wèn)題涌庭，就是說(shuō) Object.hashCode和System.identityHashCode方法都是native方法，底層的實(shí)現(xiàn)有什么區(qū)別么欧宜？這個(gè)等以后慢慢再想坐榆。
參考自：
Java-IdentityHashMap實(shí)現(xiàn)
JDK1.8源碼分析之IdentityHashMap
