HashMap源码解读

Bertha 。 2022-04-11 09:25 176阅读 0赞

HashMap保存数据的结构是数组+单向链表，它集成AbstractMap类以及实现Map接口：

public class HashMap<K,V>
        extends AbstractMap<K,V>
        implements Map<K,V>, Cloneable, Serializable
    {
        //初始化大小16
        static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
        //最大大小
        static final int MAXIMUM_CAPACITY = 1 << 30;
       //默认加载因子
        static final float DEFAULT_LOAD_FACTOR = 0.75f;
    
        static final Entry<?,?>[] EMPTY_TABLE = {};
    
        transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
        
         /**
         * The number of key-value mappings contained in this map.
         */
        transient int size;//map中key-value个数
    
        /**
         * The next size value at which to resize (capacity * load factor).
         * @serial
         */
        // If table == EMPTY_TABLE then this is the initial capacity at which the
        // table will be created when inflated.
        int threshold;//当size值大于等于threshold时需要扩容

HashMap有四个构造方法：

1、带初始化大小和加载因子的构造方法

public HashMap(int initialCapacity, float loadFactor)

public HashMap(Map<? extends K, ? extends V> m)

2、带初始化大小的构造方法

public HashMap(int initialCapacity)

3、无参构造方法

public HashMap()

4、带Map类型参数的构造方法

public HashMap(Map<? extends K, ? extends V> m)

在HashMap中，通过key的hash值来计算元素在数组table中的位置

int hash = hash(key);
    int i = indexFor(hash, table.length);

如果hash相等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);
                    return oldValue;
                }
            }

如果不同的key计算出来的位置相同，则这些key-value组成单向链表，当实际的数据个数大于等于临界值threshold时，则需要以原大小的2倍的对table进行扩容：

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);
            }
    
            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);
        }

并且需要重新计算数据再新数组中的位置并复制到新数组中。

通过key取value时，也是先通过key的hash计算位置，再遍历链表：

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;
        }