image frame

无论走到哪里,
都应该记住,
过去都是假的,
回忆是一条没有尽头的路。
一切以往的春天都不复存在,
就连那最坚韧而又狂乱的爱情,
归根结底也不过是转瞬即逝的现实,
唯有孤独永恒。

——加西亚·马尔克斯

IdentityHashMap 源码

概述

  • IdentityHashMap 使用 hash 表存储数据,实现了 Map 接口。
  • 与 HashMap 不同的是,IdentityHashMap 使用 引用相等 替换 对象相等

    也就是说,IdentityHashMap 判断两个 key 相等的方式是 (k1==k2)
    而 HashMap 判断两个 key 相等的方式是 (k1==null ? k2==null : k1.equals(k2))

继承结构

IdentityHashMap继承结构

  • 实现了 Map 接口,拥有 Map 特性;

源码实现

属性

View Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
/**
* The initial capacity used by the no-args constructor.
* MUST be a power of two. The value 32 corresponds to the
* (specified) expected maximum size of 21, given a load factor
* of 2/3.
*/
private static final int DEFAULT_CAPACITY = 32;

/**
* The minimum capacity, used if a lower value is implicitly specified
* by either of the constructors with arguments. The value 4 corresponds
* to an expected maximum size of 2, given a load factor of 2/3.
* MUST be a power of two.
*/
private static final int MINIMUM_CAPACITY = 4;

/**
* The maximum capacity, used if a higher value is implicitly specified
* by either of the constructors with arguments.
* MUST be a power of two <= 1<<29.
*
* In fact, the map can hold no more than MAXIMUM_CAPACITY-1 items
* because it has to have at least one slot with the key == null
* in order to avoid infinite loops in get(), put(), remove()
*/
private static final int MAXIMUM_CAPACITY = 1 << 29;

/**
* The table, resized as necessary. Length MUST always be a power of two.
*/
transient Object[] table; // non-private to simplify nested class access

/**
* The number of key-value mappings contained in this identity hash map.
*
* @serial
*/
int size;

/**
* The number of modifications, to support fast-fail iterators
*/
transient int modCount;

/**
* Value representing null keys inside tables.
*/
static final Object NULL_KEY = new Object();

/**
* Use NULL_KEY for key if it is null.
*/
private static Object maskNull(Object key) {
return (key == null ? NULL_KEY : key);
}

/**
* Returns internal representation of null key back to caller as null.
*/
static final Object unmaskNull(Object key) {
return (key == NULL_KEY ? null : key);
}
  • 默认容量:32
  • 最小容量:4
  • 最大容量为:1 << 29

    这里小于 MAXIMUM_CAPACITY-1,是因为它必须有一个 key 等于 null 的位置,
    为了避免 get,put,remove 方法进入无限循环

构造方法

View Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
/**
* Constructs a new, empty identity hash map with a default expected
* maximum size (21).
*/
public IdentityHashMap() {
init(DEFAULT_CAPACITY);
}

/**
* Constructs a new, empty map with the specified expected maximum size.
* Putting more than the expected number of key-value mappings into
* the map may cause the internal data structure to grow, which may be
* somewhat time-consuming.
*
* @param expectedMaxSize the expected maximum size of the map
* @throws IllegalArgumentException if <tt>expectedMaxSize</tt> is negative
*/
public IdentityHashMap(int expectedMaxSize) {
if (expectedMaxSize < 0)
throw new IllegalArgumentException("expectedMaxSize is negative: "
+ expectedMaxSize);
init(capacity(expectedMaxSize));
}

/**
* Returns the appropriate capacity for the given expected maximum size.
* Returns the smallest power of two between MINIMUM_CAPACITY and
* MAXIMUM_CAPACITY, inclusive, that is greater than (3 *
* expectedMaxSize)/2, if such a number exists. Otherwise returns
* MAXIMUM_CAPACITY.
*/
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));
}

/**
* Constructs a new identity hash map containing the keys-value mappings
* in the specified map.
*
* @param m the map whose mappings are to be placed into this map
* @throws NullPointerException if the specified map is null
*/
public IdentityHashMap(Map<? extends K, ? extends V> m) {
// Allow for a bit of growth
this((int) ((1 + m.size()) * 1.1));
putAll(m);
}
  • 没有指定初始容量,则使用默认的初始容量:32;
  • 指定期望的初始容量,使用大于期望容量最小 2 的 n 次幂;

put(K key, V value)

View Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
/**
* Associates the specified value with the specified key in this identity
* hash map. If the map previously contained a mapping for the key, the
* old value is replaced.
*
* @param key the key with which the specified value is to be associated
* @param value the value to be associated with the specified key
* @return the previous value associated with <tt>key</tt>, or
* <tt>null</tt> if there was no mapping for <tt>key</tt>.
* (A <tt>null</tt> return can also indicate that the map
* previously associated <tt>null</tt> with <tt>key</tt>.)
* @see Object#equals(Object)
* @see #get(Object)
* @see #containsKey(Object)
*/
public V put(K key, V value) {
final Object k = maskNull(key);

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)) {
if (item == k) {
@SuppressWarnings("unchecked")
V oldValue = (V) tab[i + 1];
tab[i + 1] = value;
return oldValue;
}
}

final int s = size + 1;
// Use optimized form of 3 * s.
// Next capacity is len, 2 * current capacity.
// 如果3*size 大于数组的length,则进行扩容
if (s + (s << 1) > len && resize(len))
continue retryAfterResize;

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

/**
* Returns index for Object 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);
}
  • put 的时候先通过引用是否相等判断key是不是已经在表中存在,如果存在更新 oldValue 为新的 value,如果元素个数达到阈值,扩容处理,然后再找合适的位置放置 key 和 value;
  • 在数组的i索引处存key,而紧挨着 i 的 i+1 处存 value,并且由于 hash 方法的原因,key 所对应的 index 全是偶数,自然 i+1 就是奇数了。这也说明了另一点,数组初始化的时候,数组的长度被定义为默认容量的 2 倍,因为数组元素的每次保存是都占了数组的两个位置。
  • put 的扩容条件是当存放的数组达到数组长度的 1/3 的时候,就需要扩容。
  • System.identityHashCode(x) 是取地址值进行计算;

get(Object key)

View Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
/**
* Returns the value to which the specified key is mapped,
* or {@code null} if this map contains no mapping for the key.
*
* <p>More formally, if this map contains a mapping from a key
* {@code k} to a value {@code v} such that {@code (key == k)},
* then this method returns {@code v}; otherwise it returns
* {@code null}. (There can be at most one such mapping.)
*
* <p>A return value of {@code null} does not <i>necessarily</i>
* indicate that the map contains no mapping for the key; it's also
* possible that the map explicitly maps the key to {@code null}.
* The {@link #containsKey containsKey} operation may be used to
* distinguish these two cases.
*
* @see #put(Object, Object)
*/
@SuppressWarnings("unchecked")
public V get(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)
return (V) tab[i + 1];
if (item == null)
return null;
// hash 冲突,移位遍历
i = nextKeyIndex(i, len);
}
}

/**
* Circularly traverses table of size len.
*/
private static int nextKeyIndex(int i, int len) {
return (i + 2 < len ? i + 2 : 0);
}
  • 如果 i 处找到 key,说明 i+1 处就是索引对应的 value;
  • 如果 i 处找到的 key 值和传入的 key 不相等,说明 hash 冲突,移动 2 个位置继续查找;

remove(Object key)

View Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/**
* Removes the mapping for this key from this map if present.
*
* @param key key whose mapping is to be removed from the map
* @return the previous value associated with <tt>key</tt>, or
* <tt>null</tt> if there was no mapping for <tt>key</tt>.
* (A <tt>null</tt> return can also indicate that the map
* previously associated <tt>null</tt> with <tt>key</tt>.)
*/
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--;
@SuppressWarnings("unchecked")
V oldValue = (V) tab[i + 1];
tab[i + 1] = null;
tab[i] = null;
closeDeletion(i);
return oldValue;
}
if (item == null)
return null;
i = nextKeyIndex(i, len);
}
}
  • 删除方法与查找方法类似,找到则置空,释放空间;

resize(int newCapacity)

View Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/**
* Resizes the table if necessary to hold given capacity.
*
* @param newCapacity the new capacity, must be a power of two.
* @return whether a resize did in fact take place
*/
private boolean resize(int newCapacity) {
// assert (newCapacity & -newCapacity) == newCapacity; // power of 2
int newLength = newCapacity * 2;

Object[] oldTable = table;
int oldLength = oldTable.length;
if (oldLength == 2 * MAXIMUM_CAPACITY) { // can't expand any further
if (size == MAXIMUM_CAPACITY - 1)
throw new IllegalStateException("Capacity exhausted.");
return false;
}
if (oldLength >= newLength)
return false;

Object[] newTable = new Object[newLength];

for (int j = 0; j < oldLength; j += 2) {
Object key = oldTable[j];
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;
}
}
table = newTable;
return true;
}
  • 扩容的数组是原来的两倍;

hashCode() & equals(Object o)

View Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
/**
* Returns the hash code value for this map. The hash code of a map is
* defined to be the sum of the hash codes of each entry in the map's
* <tt>entrySet()</tt> view. This ensures that <tt>m1.equals(m2)</tt>
* implies that <tt>m1.hashCode()==m2.hashCode()</tt> for any two
* <tt>IdentityHashMap</tt> instances <tt>m1</tt> and <tt>m2</tt>, as
* required by the general contract of {@link Object#hashCode}.
*
* <p><b>Owing to the reference-equality-based semantics of the
* <tt>Map.Entry</tt> instances in the set returned by this map's
* <tt>entrySet</tt> method, it is possible that the contractual
* requirement of <tt>Object.hashCode</tt> mentioned in the previous
* paragraph will be violated if one of the two objects being compared is
* an <tt>IdentityHashMap</tt> instance and the other is a normal map.</b>
*
* @return the hash code value for this map
* @see Object#equals(Object)
* @see #equals(Object)
*/
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);
result += System.identityHashCode(k) ^
System.identityHashCode(tab[i + 1]);
}
}
return result;
}

/**
* Compares the specified object with this map for equality. Returns
* <tt>true</tt> if the given object is also a map and the two maps
* represent identical object-reference mappings. More formally, this
* map is equal to another map <tt>m</tt> if and only if
* <tt>this.entrySet().equals(m.entrySet())</tt>.
*
* <p><b>Owing to the reference-equality-based semantics of this map it is
* possible that the symmetry and transitivity requirements of the
* <tt>Object.equals</tt> contract may be violated if this map is compared
* to a normal map. However, the <tt>Object.equals</tt> contract is
* guaranteed to hold among <tt>IdentityHashMap</tt> instances.</b>
*
* @param o object to be compared for equality with this map
* @return <tt>true</tt> if the specified object is equal to this map
* @see Object#equals(Object)
*/
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
}
}
  • IdentityHashMap 重写了 equals 和 hashcode 方法,通过 System.identityHashCode 方法来实现的 hashCode ,确保使用地址值来判断;
  • 通过重写 equals 方法,判定只有 key 值全等情况下才会判断 value 值相等;

总结

  • IdentityHashMap 的实现不同于 HashMap,虽然也是数组,不过 IdentityHashMap 中没有用到链表,解决冲突的方式是计算下一个有效索引,并且将数据 key 和 value 紧挨着存在map中,即 table[i]=key,那么 table[i+1]=value。
  • IdentityHashMap 的 hash 的计算没有使用 Object 的 hashCode 方法,而是使用的 System.identityHashCode 方法,这是根据对象的内存地址来计算散列码。
  • © 2015-2020 Andrew
  • Powered by Hexo Theme Ayer
  • PV: UV:

请我喝杯咖啡吧~

支付宝
微信