Uncover the data stored procedure for a HashMap from its roots

• [free] exclusive: this is a very valuable collection of Android knowledge system!!

Tips:4 links, 5.7 hours of careful polishing to complete the online.

In our daily development process, HashMap usage is still very high. This paper will first give a brief introduction to the basic attributes and methods of the Map interface, and then discuss the initialization and data addition of HashMap.

Through the learning of this article, you can learn:

A brief introduction to Map interfaces

Initialization of HashMap

The process of adding data to HashMap

A brief introduction to Map interfaces

We can see the Map source code, Map is key-value(key-value pair) in the form of interface, derived from it is quite a number of interfaces and classes, such as today’s main character HashMap, TreeMap, Hashtable, SortedMap and so on.

Its common methods and descriptions are as follows:

For more information about Map, see the Api documentation

Initialization of HashMap

Let’s take a look at the inheritance and interface implementation of HashMap:

public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable
Copy the code

AbstractMap also implements the Map interface. Therefore, there is no doubt that a HashMap has all the characteristics of a Map. And the static inner class HashMap HashMapEntry<K,V> also implements the map. Entry<K,V> interface, as follows:

static class HashMapEntry<K,V> implements Map.Entry<K,V> { final K key; V value; HashMapEntry<K,V> next; int hash; HashMapEntry(int h, K k, V v, HashMapEntry<K,V> n) { value = v; next = n; key = k; hash = h; }... }Copy the code

Each data stored in a HashMap table is an object of HashMapEntry<K,V>, which contains the key, value, the reference object next to the next object, and the hash code value generated by that key.

Let’s start by looking at a few important global variables of HashMap

Static final int DEFAULT_INITIAL_CAPACITY = 4; Static final int MAXIMUM_CAPACITY = 1 << 30; Static final float DEFAULT_LOAD_FACTOR = 0.75f; Static final HashMapEntry<? ,? >[] EMPTY_TABLE = {}; [] TABLE = (HashMapEntry<K,V>[]) EMPTY_TABLE; // This deserialized array table is used when HashMap needs to adjust capacity. // HashMap transient int size; // This value is used when the HashMap needs to adjust the capacity using int threshold; // loadFactor, default is 0.75f final float loadFactor = DEFAULT_LOAD_FACTOR; // counter TRANSIENT int modCount;Copy the code

A HashMap can be constructed by:

We’ll explore the first constructor, which looks like this:

public HashMap() {
    this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}

public HashMap(int initialCapacity, float loadFactor) {
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
    if (initialCapacity > MAXIMUM_CAPACITY) {
        initialCapacity = MAXIMUM_CAPACITY;
    } else if (initialCapacity < DEFAULT_INITIAL_CAPACITY) {
        initialCapacity = DEFAULT_INITIAL_CAPACITY;
    }

    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
    
    threshold = initialCapacity;
    init();
}
Copy the code

As you can see from the default constructor, there are two parameters initialCapacity and loadFactor. Since we didn’t pass these two parameters in through any other constructor, the default values will be used.

The constructor is shown as follows using a flow chart:

Therefore, the whole initialization process is just to judge the rationality of parameters and determine the initial values of several variables.

The process of adding data to HashMap

Now that we have an instance of a HashMap, we can store data in it using the following methods:

public V put(K key, V value) { if (table == EMPTY_TABLE) { inflateTable(threshold); } if (key == null) return =; int hash = sun.misc.Hashing.singleWordWangJenkinsHash(key); int i = indexFor(hash, table.length); for (HashMapEntry<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); return oldValue; } } modCount++; addEntry(hash, key, value, i); return null; }Copy the code

The entire process of the PUT method is resolved as follows:

InflateTable initialization: In the constructor, we did not initialize the table, so the inflateTable method will be executed.

private void inflateTable(int toSize) {
    int capacity = roundUpToPowerOf2(toSize);

    float thresholdFloat = capacity * loadFactor;
    if (thresholdFloat > MAXIMUM_CAPACITY + 1) {
        thresholdFloat = MAXIMUM_CAPACITY + 1;
    }

    threshold = (int) thresholdFloat;
    table = new HashMapEntry[capacity];
}

private static int roundUpToPowerOf2(int number) {
    int rounded = number >= MAXIMUM_CAPACITY
            ? MAXIMUM_CAPACITY
            : (rounded = Integer.highestOneBit(number)) != 0
                ? (Integer.bitCount(number) > 1) ? rounded << 1 : rounded
                : 1;

    return rounded;
}
Copy the code

RoundUpToPowerOf2 (roundUpToPowerOf2) roundUpToPowerOf2 (roundUpToPowerOf2) roundUpToPowerOf2 (roundUpToPowerOf2) roundUpToPowerOf2 (roundUpToPowerOf2)

2. Store data by key: There are two handling cases: Key is null and key is not null.

Case 1: The key is null

In this case, the putForNullKey method is called,

private V putForNullKey(V value) { for (HashMapEntry<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; }Copy the code

The array table is iterated from beginning to end. When a null key is found, the old value is replaced by the new value and the old value is returned. Otherwise, the counter modCount is incremented by 1, the addEntry method is called, and null is returned.

Case 2: The key is not null

In this case, the table is searched for the value of the same bucketIndex based on the bucketIndex generated by indexFor(hash, table.length). If yes, the old value is replaced with the new value and the old value is returned. Otherwise, the counter modCount is incremented by 1, the addEntry method is called, and null is returned.

Both cases end up pointing to the addEntry method. Let’s see how it is implemented:

void addEntry(int hash, K key, V value, int bucketIndex) { if ((size >= threshold) && (null ! = table[bucketIndex])) { resize(2 * table.length); hash = (null ! = key) ? sun.misc.Hashing.singleWordWangJenkinsHash(key) : 0; bucketIndex = indexFor(hash, table.length); } createEntry(hash, key, value, bucketIndex); }Copy the code

In this method, check whether the table needs to be expanded. If you need to expand the table, run the resize method and enter twice the length of the existing table.

void resize(int newCapacity) {
    HashMapEntry[] oldTable = table;
    int oldCapacity = oldTable.length;
    if (oldCapacity == MAXIMUM_CAPACITY) {
        threshold = Integer.MAX_VALUE;
        return;
    }

    HashMapEntry[] newTable = new HashMapEntry[newCapacity];
    transfer(newTable);
    table = newTable;
    threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
Copy the code

The resize method returns integer.max_value if the table has reached its maximum size. Otherwise, create a new table based on the new capacity value and perform the data migration method transfer.

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

The transfer method migrates all data from the old table to the new table.

void createEntry(int hash, K key, V value, int bucketIndex) {
    HashMapEntry<K,V> e = table[bucketIndex];
    table[bucketIndex] = new HashMapEntry<>(hash, key, value, e);
    size++;
}
Copy the code

Finally, add the data to the bucketIndex position of the table and add size by 1.

Now, two small diagrams represent the two states of the PUT process, as follows:

The bucketIndex location is determined by the key and the length of the table. It can be calculated in addEntry method:

bucketIndex = indexFor(hash, table.length);
Copy the code

Therefore, it is possible to have the same bucketIndex, also known as a bucketIndex collision. When a collision occurs, the values of the same bucketIndex will be linked together in a single chain. In this case, the next in HashMapEntry<K,V> will point to the next element. Which proves the following statement:

If hashCode is different, equals must be false; Equals is not set to true if hashCode is the same.

Finally, I wish you a happy study!

• [free] exclusive: this is a very valuable collection of Android knowledge system!!