Analysis of HashMap core source code: Jdk1.7HashMap
preface
The implementation of JDK7 is array + linked list; When a Hash conflict occurs, it is inserted into the head of the linked list (head insertion); Because if it is inserted in the tail, it needs to traverse the linked list, resulting in low insertion efficiency. Moreover, there is a locality principle in the operating system, that is, operations are often performed locally for a period of time, so generally speaking, the order of put is consistent with that of get, so the efficiency is faster.
1 important attributes
(0)DEFAULT_ INITIAL_ CAPACITY = 1 << 4; Default initialization size 16
(1)MAXIMUM_ CAPACITY= 1 << 30； Maximum capacity
(2)DEFAULT_LOAD_FACTOR = 0.75f； Default load factor 0.75
(3)Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_ TABLE； The underlying implementation array of HashMap
(4)transient int size； hashMap capacity
(5)float loadFactor; Load factor for hashentry
(6)transient int hashSeed = 0; Hash seed
(7)int threshold; Threshold value, that is, the size of the next capacity expansion. The calculation formula is (capacity * load factor)
(8)Entry<?,?> [] EMPTY_ TABLE = {}; Empty hash table
(9)transient int modCount; Modification times of HashMap
2 constructor
// Initialize capacity and load factor
// The default load factor is 0.75 static final float DEFAULT_LOAD_FACTOR = 0.75f;
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
// Initialization threshold
threshold = initialCapacity;
init(); // Empty method, implemented by subclasses.
}
3 put
public V put(K key, V value) {
//Judge whether HashTable is empty,
if (table == EMPTY_TABLE) {
//Initialize if it is empty.
inflateTable(threshold);
}
// If the key is equal to null, value with null key will be assigned. hashmap supports entry with null key.
if (key == null)
return putForNullKey(value);
// Calculate hashcode
int hash = hash(key);
// Calculate the index of hashtable corresponding to hashcode
int i = indexFor(hash, table.length);
// Traverse the hash table to find out whether the key already exists. If so, modify the value value of the original specified key
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this); // Empty method, subclass implementation.
// Change the original value to a new value and return oldValue
return oldValue;
}
}
// If there is no such key in the Hashtable, execute the insert operation.
modCount++;
addEntry(hash, key, value, i);
return null;
}
// toSize will be processed here, and the number returned is a power greater than or equal to 2 of toSize
private void inflateTable(int toSize) {
// Find a power of 2 greater than or equal to toSize
int capacity = roundUpToPowerOf2(toSize);
threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
table = new Entry[capacity];
initHashSeedAsNeeded(capacity);
}
// This method is very attractive.
// First (number - 1) <1, move number - 1 to the left as 1, which is equivalent to subtracting one first, and then multiplying by 1
// Call integer The highestonebit method obtains a power number less than or equal to 2 of the specified number
// After doubling the number, remove the 1 in other positions except the high position.
private static int roundUpToPowerOf2(int number) {
// assert number >= 0 : "number must be non-negative";
return number >= MAXIMUM_CAPACITY
? MAXIMUM_CAPACITY
: (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;
}
// This method is to find the power of 2 smaller than i, just opposite to the above function.
// How to achieve it??
/*
Assume i = 17
17 0001 0001
>>1 0000 1000
| 0001 1001
>>2 0000 0110
| 0001 1111
>>4 0000 0001
| 0001 1111
>>8 0000 0000
| 0001 1111
then:
>>1 0000 1111
- 0001 0000
You can see that it is equivalent to erasing the 1
*/
public static int highestOneBit(int i) {
// HD, Figure 3-1
i |= (i >> 1);
i |= (i >> 2);
i |= (i >> 4);
i |= (i >> 8);
i |= (i >> 16);
return i - (i >>> 1);
}
final int hash(Object k) {
//Get the hash seed. The default value is 0
int h = hashSeed;
if (0 != h && k instanceof String) {
return sun.misc.Hashing.stringHash32((String) k);
}
// The XOR operation is performed with 0. The XOR result is 1 when the bits are different
h ^= k.hashCode();
// Ensure that the high bit of hashcode can also participate in the operation. On hashcode more hash
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
// Get the index position of the array corresponding to the specified hashcode
// Here, the hashcode and the index subscript of the array are enlarged for fetching and operation
// Since the bits of the maximum index are all 1, it is equivalent to intercepting the significant bits in the specified index of the hashcode
// 0000 1101 & 0000 1111 = 0000 1101； The last four bits are truncated, which also explains why the length of hashmap must be an integer power of 2.
// Why not use the remainder operation? Because the remainder calculation is more time-consuming than the direct bit operation, in the computer, the remainder instruction will also be optimized into the bit operation, so the bit operation is selected to improve the efficiency
static int indexFor(int h, int length) {
// assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
return h & (length-1);
}
// The Entry with null key exists in the first position of the hash array; This method is very simple. It is to traverse the hash table, find the node whose key of the linked list corresponding to the first position of the array is equal to null, and then modify its value value. Why traverse?? Because the hashcode calculation may also be 0 Even other elements may exist at 0
private V putForNullKey(V value) {
for (Entry<K,V> e = table[0]; e != null; e = e.next) {
if (e.key == null) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(0, null, value, 0);
return null;
}
// Want to add elements to the hash array.
void addEntry(int hash, K key, V value, int bucketIndex) {
// If the current hashmap size has reached the threshold, or the Entry of the position to be inserted is not empty, there are elements
if ((size >= threshold) && (null != table[bucketIndex])) {
// Double the capacity.
resize(2 * table.length);
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex);
}
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
Entry[] newTable = new Entry[newCapacity];
transfer(newTable, initHashSeedAsNeeded(newCapacity));
table = newTable;
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
// Single thread capacity expansion
// Expand the capacity in your own thread and copy it to the old hash table after success.
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
// Create a new array and transfer the elements of the old array to the new array
Entry[] newTable = new Entry[newCapacity];
// The references on the old and new arrays are copied to the new array,
transfer(newTable, initHashSeedAsNeeded(newCapacity));
// Transfer the new array to the old array.
table = newTable;
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
//Modification of hash seed
final boolean initHashSeedAsNeeded(int capacity) {
// The default hash seed is 0. Judge whether the seed has changed
boolean currentAltHashing = hashSeed != 0;
// Judge whether the JVM is started and whether it is greater than the threshold of modifiable hash
// This value is determined by the JVM parameter jdk map. althashing. Threshold to specify
boolean useAltHashing = sun.misc.VM.isBooted() &&
(capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
boolean switching = currentAltHashing ^ useAltHashing;
if (switching) {
hashSeed = useAltHashing
? sun.misc.Hashing.randomHashSeed(this)
: 0;
}
return switching;
}
// Because it is an array + linked list, the double loop implements the migration of arrays.
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;
// Whether to re hash
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
int i = indexFor(e.hash, newCapacity);
// This is also the head interpolation method. The current element is pointed to the chain header, and then the reference of the current element is assigned to the chain header
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}
// Header inserting method: first, create a node, the pointer of the node executes the header node, and then assign the reference of the node to table[bucketIndex]
void createEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] = new Entry<>(hash, key, value, e);
size++;
}
In JDK1.7, there are only two cases of capacity expansion: one is that the position does not move, and the other is that the position moves;
HashMap is thread unsafe. During the capacity expansion of JDK1.7 under multithreading, a circular linked list will appear, resulting in an endless loop.
At the beginning, e of thread 1 points to node 1, and next points to node 2; E of thread 2 also points to node 1, and next points to node 2
Since thread 1 is preempted for CPU time, then thread 2 finishes executing the while loop. In this case, node 3 - > node 2 - > node 1->NULL; After thread 2 executes the while loop, thread 1 immediately grabs back the CPU. At this time, it executes the first loop, mounts e (node 1) to the array of thread 1, and then points to NULL; Execute the second cycle, e points to node 2, and next points to node 1. At this time, it is equivalent to attaching node 2 to the array; Execute the third cycle, e points to node 1, next points to NULL, and then point node 1 to the head node (head interpolation). At this time, node 1 points to node 2, and node 2 points to node 1. A circular linked list appears, and then E points to NULL. When the cycle execution ends, exit; Then re assign the value to the upper edge of the array, but this will cause a circular linked list, which will be stuck in the next get. I'm sorry I didn't like this picture.
4 delete element
Deleting an element is actually very simple. First, find the position of the element to be deleted in the array, then traverse the single linked list pointed to by the array element, find the element to be deleted, and delete it. In essence, delete an element in the single linked list.
public V remove(Object key) {
Entry<K,V> e = removeEntryForKey(key);
return (e == null ? null : e.value);
}
final Entry<K,V> removeEntryForKey(Object key) {
if (size == 0) {
return null;
}
int hash = (key == null) ? 0 : hash(key);
int i = indexFor(hash, table.length);
Entry<K,V> prev = table[i];
Entry<K,V> e = prev;
while (e != null) {
Entry<K,V> next = e.next;
Object k;
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k)))) {
modCount++;
size--;
if (prev == e)
table[i] = next;
else
prev.next = next;
e.recordRemoval(this);
return e;
}
prev = e;
e = next;
}
return e;
}
5 find elements
The search is also very simple, that is, determine the array index of the specified key, and then traverse the single linked list pointed to by the index.
public V get(Object key) {
if (key == null)
return getForNullKey();
Entry<K,V> entry = getEntry(key);
return null == entry ? null : entry.getValue();
}
final Entry<K,V> getEntry(Object key) {
if (size == 0) {
return null;
}
int hash = (key == null) ? 0 : hash(key);
for (Entry<K,V> e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
}
return null;
}
6 ConcurrentModificationException
import java.util.HashMap;
public class Test {
public static void main(String[] args) {
HashMap<String, String> hashMap = new HashMap<String, String>();
hashMap.put("1", "12");
hashMap.put("2", "1002");
for (String key :
hashMap.keySet()) {
hashMap.remove(key);
}
}
}
In the HashMap, there is a variable modCount, which represents the number of changes to the HashMap. Check the source code, and you can find the following code. When you find that modCount and expectedModCount do not want to wait, an exception will be thrown. In fact, the reason is that the iterator maintains an expectedModCount, which represents the number of changes to the HashMap when the iterator is created. If you find that the number of changes to the HashMap is different from that when the iterator is created during the iteration, I'm afraid that the HashMap changes after modification, resulting in inaccurate iteration, so I threw an exception. To avoid the occurrence of ConcurrentModificationException, the remove method of the iterator can be used. In the remove method of the iterator of HashMap, expectedModCount is assigned the latest modCount.
private abstract class HashIterator<E> implements Iterator<E> {
Entry<K,V> next; // next entry to return
int expectedModCount; // For fast-fail
int index; // current slot
Entry<K,V> current; // current entry
HashIterator() {
expectedModCount = modCount;
if (size > 0) { // advance to first entry
Entry[] t = table;
while (index < t.length && (next = t[index++]) == null)
;
}
}
public final boolean hasNext() {
return next != null;
}
final Entry<K,V> nextEntry() {
// Exception thrown here
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
Entry<K,V> e = next;
if (e == null)
throw new NoSuchElementException();
if ((next = e.next) == null) {
Entry[] t = table;
while (index < t.length && (next = t[index++]) == null)
;
}
current = e;
return e;
}
// In order not to throw a ConcurrentModificationException, you can use the remove method of the iterator.
public void remove() {
if (current == null)
throw new IllegalStateException();
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
Object k = current.key;
current = null;
HashMap.this.removeEntryForKey(k);
expectedModCount = modCount;
}
}