brief introduction
What should we do if an entity class overrides the hashCode method, and the hashCode returns a fixed value and needs to use the entity key? HashMap can't be used, because HashMap uses the key hashCode high and low to get the remainder of the array length and locate the position. The result of using HashMap is that no matter how many entity objects are put, only one key value pair is actually stored. In fact, the JDK provides a Map specifically to solve such problems. Yes, it is IdentityHashMap. When looking at the source code of IdentityHashMap, we should first make it clear that its key and value are in the same array. table[i] stores the key, and table[i+1] stores the value corresponding to the key.
IdentityHashMap class
public class IdentityHashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, java.io.Serializable, Cloneable
Inherit AbstractMap like HashMap (confirm again that only HashTable in the Map family is a traitor, so it does not inherit AbstractMap)
IdentityHashMap attribute
// Default length private static final int DEFAULT_CAPACITY = 32; // Minimum length private static final int MINIMUM_CAPACITY = 4; // Maximum length private static final int MAXIMUM_CAPACITY = 1 << 29; // Element array transient Object[] table; // Number of elements int size; // Modification times transient int modCount; // null key static final Object NULL_KEY = new Object();
IdentityHashMap constructor
public IdentityHashMap() {
init(DEFAULT_CAPACITY);
}
public IdentityHashMap(int expectedMaxSize) {
// Throw exception when length is less than 0
if (expectedMaxSize < 0)
throw new IllegalArgumentException("expectedMaxSize is negative: "
+ expectedMaxSize);
init(capacity(expectedMaxSize));
}
public IdentityHashMap(Map<? extends K, ? extends V> m) {
this((int) ((1 + m.size()) * 1.1));
putAll(m);
}Constructor delegate to init method initialization
private void init(int initCapacity) {
table = new Object[2 * initCapacity];
}The initialization length is twice as long as the original one (direct * 2. What posture is this? I've gained insight)
private static int capacity(int expectedMaxSize) {
return
(expectedMaxSize > MAXIMUM_CAPACITY / 3) ? MAXIMUM_CAPACITY :
(expectedMaxSize <= 2 * MINIMUM_CAPACITY / 3) ? MINIMUM_CAPACITY :
Integer.highestOneBit(expectedMaxSize + (expectedMaxSize << 1));
}It looks a little windy. expectedMaxSize > maximum_ Capability / 3 if expectedMaxSize is greater than one third of the default maximum value, take the default maximum value. Otherwise, follow the logic later, expectedMaxSize < = 2 * minimum_ Capability / 3 if expectedMaxSize is less than or equal to 4 * 2 / 3 (2), take the default minimum value; otherwise, take integer Highestonebit (expectedMaxSize + (expectedMaxSize < < 1)), interpretation of expectedMaxSize + (expectedMaxSize < < 1) is actually three times of expectedMaxSize, integer The function highestonebit is used to take the highest bit on the leftmost side of the binary form, fill all zeros after the high bit, and finally return the result of int type. It shows that all other bits except the high bit are 0, which means that the number must be the nth power of 2. Have you found that the length of nonparametric constructor array is 32 * 2 and the length of parametric constructor is maximum_ Capability, 3 times the original length, take the high or minimum_ Capability, its length is still the n-th power of 2.
After reading the previous HashMap article, we have become very powerful [covering our faces], so here we will no longer analyze one method by one, but only pick a few important methods...
IdentityHashMap cardinality method
Note: if table[i] stores the key, then table[i+1] stores the value corresponding to the key
public int hashCode() {
int result = 0;
Object[] tab = table;
// Traverse the array (i+2 must all be key s)
for (int i = 0; i < tab.length; i +=2) {
Object key = tab[i];
if (key != null) {
Object k = unmaskNull(key);
// All keys tab[i] and values tab[i + 1] identityHashCode take XOR
result += System.identityHashCode(k) ^
System.identityHashCode(tab[i + 1]);
}
}
// Return total value
return result;
}hashCode method is to add all key values after XOR
public boolean equals(Object o) {
// Same memory address
if (o == this) {
return true;
} else if (o instanceof IdentityHashMap) {
// All are IdentityHashMap instances
IdentityHashMap<?,?> m = (IdentityHashMap<?,?>) o;
// Is the length consistent
if (m.size() != size)
return false;
// Traverse whether all key values are consistent
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 determines where the key is located
private static int hash(Object x, int length) {
// Use system Identityhashcode (x) calculates the hash value
int h = System.identityHashCode(x);
// &(length - 1) it's no stranger to the remainder taking process. If you don't know, see the derivation in HashMap
return ((h << 1) - (h << 8)) & (length - 1);
}There is a question (H < < 1) - (H < < 8) why can't it be negative? Exploring
Location of the next key of IdentityHashMap
private static int nextKeyIndex(int i, int len) {
return (i + 2 < len ? i + 2 : 0);
}The current position plus 2 is the next available position, and plus 1 is the value corresponding to the current key
IdentityHashMap add
public V put(K key, V value) {
// Convert null key to Object(NULL_KEY)
final Object k = maskNull(key);
// retryAfterResize: is the tag usage in java
retryAfterResize: for (;;) {
final Object[] tab = table;
final int len = tab.length;
// Similarly, the array subscript position is calculated first
int i = hash(k, len);
// First find out whether there is the same key in the array, and replace it if found
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;
}
}
// If it is not found, the insertion is executed, and the number of key value pairs stored first is + 1
final int s = size + 1;
// If the number of elements * 3 is greater than the length of the array, the capacity will be expanded, and the size after expansion will be twice the original length
if (s + (s << 1) > len && resize(len))
continue retryAfterResize;
// Number of modifications plus 1
modCount++;
// tab[i] save key, tab[i+1] save value
tab[i] = k;
tab[i + 1] = value;
size = s;
return null;
}
}IdentityHashMap capacity expansion
private boolean resize(int newCapacity) {
// The new length is twice as long as the original
int newLength = newCapacity * 2;
Object[] oldTable = table;
int oldLength = oldTable.length;
// If the maximum capacity has been reached, the expansion fails
if (oldLength == 2 * MAXIMUM_CAPACITY) {
// If the maximum capacity has been reached, (leave one for null, otherwise the loop cannot be exited)
if (size == MAXIMUM_CAPACITY - 1)
throw new IllegalStateException("Capacity exhausted.");
return false;
}
if (oldLength >= newLength)
return false;
//The following is to loop the old table and insert the value into the new one
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;
}IdentityHashMap value
public V get(Object key) {
Object k = maskNull(key);
Object[] tab = table;
int len = tab.length;
int i = hash(k, len);
// Dead loop traversal table array
while (true) {
Object item = tab[i];
// If the same key is hit, the value of table[i+1] is returned
if (item == k)
return (V) tab[i + 1];
// If the traversal array has not been hit, it returns null
if (item == null)
return null;
i = nextKeyIndex(i, len);
}
}IdentityHashMap deletion
public V remove(Object key) {
Object k = maskNull(key);
Object[] tab = table;
int len = tab.length;
// Determine location
int i = hash(k, len);
while (true) {
// Get key
Object item = tab[i];
if (item == k) {
modCount++;
size--;
// Get original value
V oldValue = (V) tab[i + 1];
// Clear the location of the original value
tab[i + 1] = null;
// Clear key location
tab[i] = null;
closeDeletion(i);
// Return original value
return oldValue;
}
if (item == null)
return null;
// Index plus 2 not found
i = nextKeyIndex(i, len);
}
}IdentityHashMap empty
public void clear() {
modCount++;
Object[] tab = table;
// Clear the tab here. Each element is equivalent to the key and value will be cleared
for (int i = 0; i < tab.length; i++)
tab[i] = null;
size = 0;
}