How HashMap works in Java

HashMap implements the map interface. It is an asynchronous implementation based on hash table. It stores elements in the form of key value pairs. Both keys and values can be null. HashMap does not guarantee the order of mapping, especially it does not guarantee that the order remains unchanged.

HashMap underlying implementation

Its bottom layer is implemented through an array. Each element of the array is a linked list, which is implemented by the internal class of entry. The important attributes of entry are key, value and next.

The Java source code is as follows:

transient Entry[] table;

static class Entry<K,V> implements Map.Entry<K,V> {
    final K key;
    V value;
    Entry<K,V> next;
    final int hash;
    ……
}

It can be seen that an entry is an element in the array. Each entry is actually a key value pair, which holds a reference to the next element, which constitutes a linked list.

HashMap constructor

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
static final float DEFAULT_LOAD_FACTOR = 0.75f;

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

HashMap has three constructors. The above constructors are parameterless constructors. Their work is to assign values to the two member properties LoadFactor and threshold.

Threshold: initial capacity, indicating the number of buckets in the hash table, that is, the size of the array at the initial time. LoadFactor: load factor, which is 0.75 by default and represents the maximum fill ratio of the current hash table. When threshold * LoadFactor < the number of buckets in the current hash table, the threshold of the hash table needs to be doubled.

Access and implementation of HashMap

During storage, HashMap will first determine whether the key is null. If it is null, insert the key value pair into the position with index 0 in the table;

If the key is not null, calculate the hash value of the key, and then generate its subscript index in the table according to the hash value. Traverse the linked list corresponding to this subscript to see if the key value exists. If yes, replace it. If not, insert a new element in the head of the linked list.

Storage: put (key, value)

public V put(K key,V value) {
    //对table数组分配内存，可以看出HashMap只有在存储元素时才会分配内存
    if (table == EMPTY_TABLE) {
        inflateTable(threshold);
    }
    // 当key为null时，调用putForNullKey方法,将该key保存在table数组下标为0的位置上。
    if (key == null)
        return putForNullKey(value);
    // 计算key的hash值
    int hash = hash(key);
    // 计算插入数据所在链表在table中的下标(内部实现很奇妙，下次来分析这个好了↖(^ω^)↗~)
    int i = indexFor(hash,table.length);
    // 遍历此下标对应的链表，看是否存在该key值
    for (Entry < K,V > e = table[i]; e != null; e = e.next) {
        Object k;
        // 判断链表上是否有相同hash值的entry，有则替换entry的value
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            // 返回旧值，结束插入操作
            return oldValue;
        }
    }
    // 在下标i对应的链表中没有找到key相同的Entry，则创建一个新的Entry，进行插入操作
    modCount++;
    // 在下标为i的链表的头部进行插入操作（放在最后的话需要遍历单链表，消耗内存）
    addEntry(hash,key,value,i);
    return null;
}

When reading, judge whether the key is null. If yes, directly find the value value of the entry with null key in the linked list with subscript 0;

Otherwise, calculate the hash value of the key, find its index in the table according to the hash value, traverse the linked list corresponding to the index, and find the value value of the entry corresponding to the key value.

Read: get (key)

public V get(Object key) {
    // 若key为null，调用getForNullKey方法，即查找下标为0的链表中key为null的Entry的value，如果未找到则返回null
    if (key == null)
        return getForNullKey();
    //获取key对应的Entry对象
    Entry<K,V> entry = getEntry(key);
    return null == entry ? null : entry.getValue();
}

final Entry<K,V> getEntry(Object key) {
    if (size == 0) {
        return null;
    }
    // 计算key的hash值
    int hash = (key == null) ? 0 : hash(key);
    //根据key的hash值计算在table中的索引
    for (Entry<K,V> e = table[indexFor(hash,table.length)];
        e != null;
        e = e.next) {
        Object k;
        //先判断e.hash == hash，过滤大量不符合的节点，然后对剩下的节点继续判断
        if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
            return e;
        }
        return null;
    }

The judgment condition in the last if (k = e.key) = = key | (key! = null & & key. Equals (k)) involves a classic experience: when rewriting the equals method, you must rewrite the hashcode method.

Because the hashcode value of the default object is generally the number corresponding to the memory address, the hashcode value of different objects is generally different.

Therefore, when overriding the equals method, if we want the two objects to be logically the same without overriding the hashcode, there will be a problem in the HashMap. The two objects are logically the same, but because the default hashcode values are different, the two objects will be considered different. Therefore, when using HashMap to store objects, you must override the hashcode () method.

Hashcode () method rewrite rule: when the equlas method returns true, the hashcodes of the two objects are the same.