preface
The analysis of hashMap in this paper is based on JDK1.8. Compared with JDK1.7, hashMap in JDK1.8 is quite different. The biggest change is that the underlying data structure is changed byArray + linked listModified toArray + linked list + red-black treeSince red-black tree-related operations require some prior knowledge, an article will be written to explain them in detail
HashMap source code parsing
Important member variables and methods
// Default initialization length
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
// Maximum capacity
static final int MAXIMUM_CAPACITY = 1 << 30;
// Default load factor
static final float DEFAULT_LOAD_FACTOR = 0.75 f;
// List to red black tree threshold: 8
static final int TREEIFY_THRESHOLD = 8;
// Red black tree spinner threshold: 6
static final int UNTREEIFY_THRESHOLD = 6;
// The list can be turned into a red-black tree only if the array length is 64
static final int MIN_TREEIFY_CAPACITY = 64;
Copy the code static final int hash(Object key) {
int h;
// If the table is small, h >>> 16 can make full use of the high and low bits of the hash, not just the last bits of the hash
return (key == null)?0 : (h = key.hashCode()) ^ (h >>> 16);
}
Copy the code static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0)?1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
Copy the codeThis function is a very clever design, so let’s just take an example,
0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 | operation -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- 0000 0111 0000 0000 0000 0000 0000 0000 0000 0001 1100 Moves to the right 2 0000 0000 0000 0000 0000 0000 0111 1100 0000 0000 0000 0000 0000 | operation -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- 0000 0111 1100 0000 0000 0000 0000 0000 0000 0000 0111 1100 0000 0000 0000 0000 moves to the right 4 0000 0111 1111 1100 0000 0000 0000 0000 | operation -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- 0000 0111 1111 1100 0000 0000 0000 0000 0000 0000 0000 0111 1111 1100 0000 0000 moves to the right of 8, 0000, 0111, 1111, 1111, 1111, 1100, 0000 0000 | operation -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- 0000 0111 1111 1111 1111 1100 0000 0000 0000 0000 0000 0000 0000 0111 1111 1111 moves to the right of 16, 0000, 0111, 1111 1111 1111 1111 1111 1111 | operation / / you can see the right several times and | operators, will be able to get a low is the value of 1, Plus one becomes a power of two, 0000 0110 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0111 1111 1111 1111 1111 1111 1111 Final 0000 1000 0000 0000 0000 0000 0000 0000 0000 return value n+1Copy the codePut method
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// The table is not initialized yet
if ((tab = table) == null || (n = tab.length) == 0)
// Initialize the container
n = (tab = resize()).length;
// N = 1; // N = 1; // N = 1;
// If you add and to any number, the result is always 2 to the power of 2 minus 1, which is exactly the range of array markers
// If n = 32,100000 -> 011111 & any number in the range from 0 to 31
// If there is no element at the index of the array, it is stored directly
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
// The code goes here to indicate that there are elements in the array at that index
// e is for temporary storage of nodes
Node<K,V> e; K k;
/ / key repeat
if(p.hash == hash && ((k = p.key) == key || (key ! =null && key.equals(k))))
// use e to hold p node
e = p;
// If p is a red-black tree node, go through the process of adding a red-black tree node
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
// Go through the process of adding a list node
for (int binCount = 0; ; ++binCount) {
// the next node of p is empty
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// If the list can be converted to a red-black tree, then the tree,
// Note that binCount starts at 0 and treeify_threshold-1 is 7
// The length of the list (plus the elements in the array) is >=9
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
// Duplicate node keys in the linked list
if(e.hash == hash && ((k = e.key) == key || (key ! =null && key.equals(k))))
break; p = e; }}// If e is not empty, a data matching the inserted element key has been found and can be updated
if(e ! =null) { // existing mapping for key
V oldValue = e.value;
// Determine whether an update can be made
// onlyIfAbsent: Indicates whether the key can be updated if it is repeated
if(! onlyIfAbsent || oldValue ==null)
e.value = value;
afterNodeAccess(e);
returnoldValue; }}// Count the number of times the hashMap is changed
++modCount;
// Check whether the number of hashMap elements +1 exceeds the threshold. If the number exceeds the threshold, expand the capacity
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
Copy the codeThe resize method
Before we get to the resize () method, we need to keep two questions in mind
-
When will the capacity be expanded?
Elements are added first, and the capacity is expanded when the threshold is reached
-
How to expand capacity?
The following code explains this in detail
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
// oldCap: array capacity before expansion
int oldCap = (oldTab == null)?0 : oldTab.length;
// oldThr: specifies the threshold before capacity expansion
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
// If the capacity of the old array has reached the upper limit, the threshold is updated to the maximum value of type Integer and is returned immediately without expansion
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// oldCap << 1 moves one bit to the left to double the array capacity
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
// The threshold capacity is also doubled
newThr = oldThr << 1; // double threshold
}
// oldCap is 0, oldThr > 0 because the threshold was set when the old array was initialized
// public HashMap() {this.loadFactor = DEFAULT_LOAD_FACTOR; } For example, this empty constructor
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
// oldCap is 0, oldThr is also 0
else { // zero initial threshold signifies using defaults
// Set the size of the new array to the default size
newCap = DEFAULT_INITIAL_CAPACITY;
// The threshold for the new array is set to the default size *0.75
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
// The new threshold is the new array capacity * load factor (in case the new threshold is less than 1 << 30)
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
// Set a new threshold
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
// Create new array
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if(oldTab ! =null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if((e = oldTab[j]) ! =null) {
oldTab[j] = null;
// There is only one element in this position
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
// There are multiple elements at this position in the array, tree-like
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
// There are multiple elements at this position in the array. It is a linked list
else { // preserve order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
elsehiTail.next = e; hiTail = e; }}while((e = next) ! =null);
if(loTail ! =null) {
loTail.next = null;
newTab[j] = loHead;
}
if(hiTail ! =null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
Copy the codeResize code: resize code Array capacity is 2 powers has a benefit, expansion, the need to reposition elements index, expansion is the array of capacity expansion for two times, then enlarged, array capacity or the power to the power of 2, the original in a new array of the elements in an array, or in the original indexes, either in the original index + expansion value position, avoid to hash the efficiency problem
// If the size of the array is 8, The positions with the index value of 2 are 2, 6, 10, 14, 22 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0001 0000 // After the expansion becomes 16 0000 0000 0000 0000 0000 0000 0001 0000 Expansion after the original index values in an array of two numerical index again -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- 0000 0000 0000 0000 0000 0000 0000 1000 0000 0000 0000 0000 0000 0000 0000 0010 0000 0000 0000 0000 0000 0000 0000 0000 with 2 & to 0 -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- 0000 0000 0000 0000 0000 0000 0000 1000 0000 0000 0000 0000 0000 0000 0000 0110 0000 0000 0000 0000 0000 0000 0000 0000 and 6 & 0 -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 With 10 & 1 -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- 0000 0000 0000 0000 0000 0000 0000 1000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 and 14& is 1 -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- 0000 0000 0000 0000 0000 0000 0000 1000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000Copy the code// The original array capacity and 2& is 0
if ((e.hash & oldCap) == 0) {
// loTail starts with null
if (loTail == null)
// loHead points to e
loHead = e;
else
loTail.next = e;
// loTail also points to e
loTail = e;
}
Copy the code
// The original array capacity and 6& is 0
if ((e.hash & oldCap) == 0) {
// loTail is no longer null
if (loTail == null)
loHead = e;
else
// loTail points to 6
loTail.next = e;
// loTail also points to 6
loTail = e;
}
Copy the code
// The size of the original array is 10¬ 0
else {
/ / hiTail is null
if (hiTail == null)
// hiHead points to 10
hiHead = e;
else
hiTail.next = e;
// hiTail points to 10
hiTail = e;
}
Copy the code
// loTail is not null
if(loTail ! =null) {
// loTail = null, if two lists are still connected, break the list in two
loTail.next = null;
// Place it at the same index value in the new array
newTab[j] = loHead;
}
if(hiTail ! =null) {
// Similarly, disconnected lists
hiTail.next = null;
// Place it at the expanded index in the new array
newTab[j + oldCap] = hiHead;
}
Copy the code
The get method
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
if((tab = table) ! =null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) ! =null) {
// There is only one element in this position
if (first.hash == hash && // always check first node((k = first.key) == key || (key ! =null && key.equals(k))))
return first;
// There is more than one element in this position
if((e = first.next) ! =null) {
// The location is treed, look in the red black tree
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
// Start at the head of the list and work down
if(e.hash == hash && ((k = e.key) == key || (key ! =null && key.equals(k))))
return e;
} while((e = e.next) ! =null); }}return null;
}
Copy the codeThe remove method
final Node<K,V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
Node<K,V>[] tab; Node<K,V> p; int n, index;
if((tab = table) ! =null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) ! =null) {
// node is used to temporarily store the node to be deleted
Node<K,V> node = null, e; K k; V v;
// There is only one element in this position
if(p.hash == hash && ((k = p.key) == key || (key ! =null && key.equals(k))))
node = p;
// There is more than one element in this position
else if((e = p.next) ! =null) {
if (p instanceof TreeNode)
// The location is treed, look in the red black tree
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
else {
do {
// Find the list, then jump out of the loop
if(e.hash == hash && ((k = e.key) == key || (key ! =null && key.equals(k)))) {
node = e;
break;
}
p = e;
} while((e = e.next) ! =null); }}// If node is not empty, the data to be deleted is found
if(node ! =null&& (! matchValue || (v = node.value) == value || (value ! =null && value.equals(v)))) {
// Node is a red-black tree node. Delete the node from the red-black tree
if (node instanceof TreeNode)
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
// The element at that position in the array is the result of the search, and the next element of that element is placed at that position
else if (node == p)
tab[index] = node.next;
else
// The result is in the middle of the list. The node is after the p node
// point p to the next node of the node
p.next = node.next;
++modCount;
// Maintain the number of nodes in the hashMap
--size;
afterNodeRemoval(node);
returnnode; }}return null;
}
Copy the codeCircular linked lists in JDK1.7
Because the circular list in jdk1.7 is a common interview question, it is mentioned here in passing
// Key code
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
for (Entry<K,V> e : table) {
while(null! = e) { Entry<K,V> next = e.next;if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
inti = indexFor(e.hash, newCapacity); e.next = newTable[i]; newTable[i] = e; e = next; }}}Copy the code