preface
I used HashMap data structure frequently in my daily work, and I also encountered related interview questions in my last job application. Read the source code tonight to learn about the internal design of the data structure. JDK version 1.8.0 comes with _231
The body of the
Inheritance relationships
HashMap extends AbstractMap and implements the Map Cloneable Serializable interface.
MapInterfaces contain some common operationsCloneableIndicates that copy can be performedSerializableIndicates that serialization is implemented
A constructor
The HashMap class has four constructors
1.HashMap(int initialCapacity, float loadFactor)
/ * * *@paramInitialCapacity initialCapacity *@paramLoadFactor loadFactor default value: 0.75 */
public HashMap(int initialCapacity, float loadFactor) {
If the initial capacity is less than 0, an exception is thrown
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
// If the initial capacity is greater than the maximum value 1 << 30, set the maximum value to capacity
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
// The load factor is less than 0 or a non-numeric throw exception
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
// tableSizeFor method to obtain the threshold
this.threshold = tableSizeFor(initialCapacity);
}
Copy the codeHashMap(int initialCapacity)
// Call the constructor above to get the threshold
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
Copy the codeAt AlibabaJava Development ManualThe recommendations are as follows:
HashMap()
public HashMap(a) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
}
Copy the codeHashMap(Map<? extends K, ? extends V> m)
// Merge a map
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
Copy the codeAdd elements
Add data by calling the put() method,
The hash() method is used to get the hash value of the key
public V put(K key, V value) {
return putVal(hash(key), key, value, false.true);
}
Copy the code // If the key is null, return 0.
// If the key is not null, obtain the hashCode corresponding to the key and assign the value to the variable h, which is shifted 16 bits to the right; Perform xOR and return the result
static final int hash(Object key) {
int h;
return (key == null)?0 : (h = key.hashCode()) ^ (h >>> 16);
}
Copy the codeCall the putVal() method to add the element
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
HashMap.Node<K, V>[] tab;
HashMap.Node<K, V> p;
int n, i;
// Check whether the table contains data. If there is no data, perform the first expansion
if ((tab = table) == null || (n = tab.length) == 0)
// Call the resize() method to initialize
n = (tab = resize()).length;
// Modulo the hash code to obtain the location of the key. If p == null, it indicates a new element
if ((p = tab[i = (n - 1) & hash]) == null)
// Insert the new element into the ith position of the array
tab[i] = newNode(hash, key, value, null);
// Not a new element
else {
HashMap.Node<K, V> e;
K k;
// Check whether the element exists through equals() and replace it if it does
if(p.hash == hash && ((k = p.key) == key || (key ! =null && key.equals(k))))
e = p;
// It is a tree structure
else if (p instanceof TreeNode)
e = ((HashMap.TreeNode<K, V>) p).putTreeVal(this, tab, hash, key, value);
else {
// If this is a list structure, append the element to the end
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// Convert the list to a red-black tree if the list length is greater than or equal to 8
if (binCount >= TREEIFY_THRESHOLD - 1)
treeifyBin(tab, hash);
break;
}
if(e.hash == hash && ((k = e.key) == key || (key ! =null && key.equals(k))))
break; p = e; }}if(e ! =null) {
V oldValue = e.value;
if(! onlyIfAbsent || oldValue ==null)
e.value = value;
afterNodeAccess(e);
returnoldValue; }}// Number of times to modify records
++modCount;
// If the threshold is exceeded, expand the capacity
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
Copy the codeSingle-linked list structures are used to store data
static class Node<K.V> implements Map.Entry<K.V> {
// Hash value represented by key
final int hash;
/ / key
final K key;
/ / value
V value;
// Point to the next element (single linked list)
HashMap.Node<K, V> next;
Node(int hash, K key, V value, HashMap.Node<K, V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
public final K getKey(a) {
return key;
}
public final V getValue(a) {
return value;
}
public final String toString(a) {
return key + "=" + value;
}
public final int hashCode(a) {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
// Check whether two keys are equal using equals().
public final boolean equals(Object o) {
if (o == this)
return true;
if (o instanceofMap.Entry) { Map.Entry<? ,? > e = (Map.Entry<? ,? >) o;if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;
}
return false; }}Copy the codeExpansion method resize()
final HashMap.Node<K, V>[] resize() {
// table represents the array in which the data is stored. If the data is added for the first time, it is empty and if the data is added previously
HashMap.Node<K, V>[] oldTab = table;
//
int oldCap = (oldTab == null)?0 : oldTab.length;
// threshold Indicates the threshold
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
} else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1;
} else if (oldThr > 0)
newCap = oldThr;
else {
// If no capacity is specified when using hashMap and data is added for the first time, array initialization continues here; The capacity is 16 and the critical value is 12
// Default capacity 1 << 4 == 16
newCap = DEFAULT_INITIAL_CAPACITY;
// Critical value: 16 * 0.75
newThr = (int) (DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
float ft = (float) newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float) MAXIMUM_CAPACITY ?
(int) ft : Integer.MAX_VALUE);
}
// Assign the new threshold value to threshold
threshold = newThr;
@SuppressWarnings({"rawtypes", "unchecked"})
// Create a new array
HashMap.Node<K, V>[] newTab = (HashMap.Node<K, V>[]) new HashMap.Node[newCap];
table = newTab;
// Migrate data after capacity expansion
// If there is data in the old array, the data in the new array is assigned, and the values in the old array are set to NULL
if(oldTab ! =null) {
for (int j = 0; j < oldCap; ++j) {
HashMap.Node<K, V> e;
if((e = oldTab[j]) ! =null) {
oldTab[j] = null;
// e.next == null Statements have no hash conflicts
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
// A hash conflict occurred
// If it is a red-black tree
else if (e instanceof TreeNode)
((HashMap.TreeNode<K, V>) e).split(this, newTab, j, oldCap);
else {
// Migrate the original data
HashMap.Node<K, V> loHead = null, loTail = null;
HashMap.Node<K, V> hiHead = null, hiTail = null;
HashMap.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 codeLook for the element
Get the data in the HashMap using the get() method
// getNode() returns null if the value is not present
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
Copy the codeGetNode () uses the hash() method to obtain the hash value of the key before retrieving data
final HashMap.Node<K, V> getNode(int hash, Object key) {
HashMap.Node<K, V>[] tab;
HashMap.Node<K, V> first, e;
int n;
K k;
// Check whether the length of the TAB array is greater than 0 and whether the key position in the array is not null
if((tab = table) ! =null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) ! =null) {
// Determine if the element is a hash conflict
if(first.hash == hash && ((k = first.key) == key || (key ! =null && key.equals(k))))
return first;
// If a hash conflict occurs, elements will be added to the list. =null indicates that the list structure needs to be fetched from the list
if((e = first.next) ! =null) {
// When the length of the list reaches 8, convert the list to; At this point, determine whether it is a red-black tree and obtain data from it
if (first instanceof TreeNode)
return ((HashMap.TreeNode<K, V>) first).getTreeNode(hash, key);
// Walk through the list and get the data
do {
if(e.hash == hash && ((k = e.key) == key || (key ! =null && key.equals(k))))
return e;
} while((e = e.next) ! =null); }}return null;
}
Copy the codeconclusion
From the above source code analysis, it can be seen that HashMap is composed of arrays, single-linked lists and red-black trees.
- Add elements: First, the elements are stored in the data in sequence. If a hash conflict occurs, create a single-linked list on the hash bit. When the single-linked list length is greater than or equal to 8, the single-linked list is converted to a red-black tree
- Find elements: Check whether the hash value corresponding to the key exists in the array, if so, extract it from it; if the element next attribute is not null, check whether the hash value corresponding to the key exists in the tree and linked list and then extract it; if neither exists, return NULL
Read the original