JDK7 version of the source code analysis

The HashMap class is implemented as an array + linked list

Let’s meet some people

Class important attributes

Hash table array, must be 2 power N transient Entry<K,V>[] TABLE = (Entry<K,V>[]) EMPTY_TABLE; Number of included elements TRANSIENT int size; Threshold = Capacity * load factor int threshold. LoadFactor final float loadFactor;Copy the code

List objects in a hash table – important key-value objects

static class Entry<K,V> implements Map.Entry<K,V> { final K key; V value; Entry<K,V> next; // The next object in the list is int hash; Entry(int h, K k, V v, Entry<K,V> n) { value = v; next = n; key = k; hash = h; } public final int hashCode() {return objects.hashCode (getKey()) ^ Objects.hashCode(getValue()); } public final String toString() {// Return getKey() + "=" + getValue(); }... Omit part of the source}Copy the code

The most complex constructor

Look at the most complete constructor, other overloaded constructors do not write, just default method arguments, see

Public HashMap(int initialCapacity, float loadFactor) {// Check two values, 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; // Initialize load factor threshold = initialCapacity; // Initialize threshold init(); // Empty method, ignore}Copy the code

public V put(K key, V value)

The table constructor is not initialized. It’s actually initialized in the put method

Public V put(K key, V value) {if (table == EMPTY_TABLE) {// inflateTable(threshold); } if (key == null)// Return putForNullKey(value); int hash = hash(key); // Get hashCode int I = indexFor(hash, table.length); For (Entry<K,V> e = table[I]; e ! = null; E = e.ext) {// Iterate over the list Object k at the beginning of the specified array; If (e.h ash = = hash && ((k = e.k ey) = = key | | key. Equals (k))) {/ / e.h ash by addEntry source discovery is the key of hash value / / key hash value, If the keys are equal, the same key already exists in the linked list, and you need to update the oldValue to the new value V oldValue = e.value; e.value = value; e.recordAccess(this); return oldValue; } } modCount++; // If table[I]=null or no key is found in the linked list, add a key-value object to the list at table[I]. return null; }Copy the code

Initialize the table array

Private void inflateTable(int toSize) {// Find a power of 2 >= toSize // Int capacity = roundUpToPowerOf2(toSize); roundUpToPowerOf2(toSize); roundUpToPowerOf2(toSize); //threshold Calculate the true value by capacity * loadFactor threshold = (int) math. min(capacity * loadFactor, MAXIMUM_CAPACITY + 1); // Create an array of tables, default to null table = new Entry[capacity]; initHashSeedAsNeeded(capacity); }Copy the code

How do you compute 2 to the n?

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; HighestOneBit = Integer; highestOneBit = Integer; highestOneBit = Integer; Integer.highestonebit ((number - 1) << 1));Copy the code

Add the key=null element

When the key of put =null, the processing is a little different

Private V putForNullKey(V value) {private V putForNullKey(V value) {private V putForNullKey(V value) {private V putForNullKey(V value) { If the first position in the array is null, add a key-value pair with key= NULL and the value is value, and return null 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 when table[0]==null; }Copy the code

Adds a key-value to the specified array position

void addEntry(int hash, K key, V value, int bucketIndex) { if ((size >= threshold) && (null ! = table[bucketIndex])) {resize(2 * table.length); hash = (null ! = key) ? hash(key) : 0; bucketIndex = indexFor(hash, table.length); } // Add a key-value object createEntry(hash, key, value, bucketIndex) at the specified array position; }Copy the code
Void createEntry(int hash, K key, V value, int bucketIndex) {void createEntry(int hash, K key, V value, int bucketIndex) {// Table [bucketIndex]; table[bucketIndex] = new Entry<>(hash, key, value, e); size++; }Copy the code

Calculates the array position based on the key’s hashCode and the array’s capacity

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); // Return h%(length-1); }Copy the code

Array capacity

Now look again at the implementation of the addEntry method

void addEntry(int hash, K key, V value, int bucketIndex) { if ((size >= threshold) && (null ! = table[bucketIndex])) {resize(2 * table.length); hash = (null ! = key) ? hash(key) : 0; bucketIndex = indexFor(hash, table.length); } // Add an element to the list. See createEntry(Hash, key, value, bucketIndex); }Copy the code

Array table is doubled in size

void resize(int newCapacity) { Entry[] oldTable = table; int oldCapacity = oldTable.length; if (oldCapacity == MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return; } // Create an array, newCapacity =2 * table.length, double the size of the original array Entry[] newTable = new Entry[newcapacity]; Transfer (newTable, initHashSeedAsNeeded(newCapacity)); //table refers to the expanded array, that is, the new array to replace the old array table = newTable; // Recalculate threshold = (int) math. min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1); }Copy the code

The real expansion, but also the way of head plug

void transfer(Entry[] newTable, boolean rehash) { int newCapacity = newTable.length; For (Entry<K,V> e: table) {// Iterate over each array position while(null! // The next object reference to which the current k-v object points is temporarily saved to next Entry< k, v > next = e.next; // Ignore if (rehash) {e.hash = null == e.key? 0 : hash(e.key); } // Calculate the position in the new array after the expansion int I = indexFor(e.hash, newCapacity); // The current k-v object points to the next k-v object. If newTable[I] is null, it points to null. Otherwise point to the k-v object e.ext = newTable[I]; NewTable [I] = e; newTable[I] = e; // Move the reference pointer e to the next node e = next; }}}Copy the code

public V get(Object key)

Next, parse the GET method, which is fairly simple

Public V get(Object key) {// Key =null return getForNullKey(); //key! Null Query Entry<K,V> Entry = getEntry(key); return null == entry ? null : entry.getValue(); }Copy the code

Query value where key=null

private V getForNullKey() { if (size == 0) { return null; } for (Entry<K,V> e = table[0]; e ! = null; e = e.next) { if (e.key == null) return e.value; } return null; }Copy the code

Query is the key! = null value

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) {// Locate the array by the key hash and iterate over the list Object k represented by the array; if (e.hash == hash && ((k = e.key) == key || (key ! = null &&key. equals(k))))) } return null; }Copy the code

Thread safety

Review key steps

From the above analysis, it can be seen that there is an expansion operation transfer in the PUT method. Now take out a few steps:

for (Entry<K,V> e : table) {
    while(null != e) {
        Entry<K,V> next = e.next;
        int i = indexFor(e.hash, newCapacity);
        e.next = newTable[i];
        newTable[i] = e;
        e = next;
    }
}
Copy the code

Analyze a thread-safe situation

Thread-safe situations are not limited to this.

Suppose you have two threads, T1 and T2, simultaneously rehash the first linked list element of table[I] into the new array.

Analysis 1: T1 run newTable[I] = e; NewTable [I] =null; newTable[I] =null Thread T1 is stopped;

Analysis 2: T2 start from Entry<K,V> next = e.next; Next =null after Entry<K,V> next= e.next = newTable[I]; E.next points to itself, e, forming a loop; E = next; When e==null, the while exits and the next for loop begins

As can be seen from the above, circular linked lists will appear after expansion. Then, by analyzing the GET method before, it can be seen that the condition of the for loop in GET is always met, but the condition of if is always not met, there will be an infinite loop of query, and the GET method cannot be returned all the time, which may lead to 100% CPU

The capacity has to be two to the NTH, right?

Yeah, yeah

Two reasons

  1. Make elements as evenly distributed as possible to reduce hash collisions
  2. Take advantage of binary computing efficiency. H %(length-1) is equal to h & (Length-1) at 2 to the n, and bitwise sum is more efficient