HashMap源码分析

一、HashMap底层实现

HashMap底层结构：数组+链表+红黑树

Java中的HashMap是以键值对(key-value)的形式存储元素的。HashMap需要一个hash函数，它使用hashCode()和equals()方法来向集合/从集合添加和检索元素。当调用put()方法的时候，HashMap会计算key的hash值，然后把键值对存储在集合中合适的索引上。如果key已经存在了，value会被更新成新值

HashMap的一些重要的特性是它的容量(capacity)，负载因子(load factor)和扩容极限(threshold resizing)

二、初始化HashMap

源码：三种构造函数

 
//initialCapacity：初始化大小，loadFactor:加载因子
public HashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0) {
            throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
        } else {
            if (initialCapacity > 1073741824) {
                initialCapacity = 1073741824;
            }

            if (loadFactor > 0.0F && !Float.isNaN(loadFactor)) {
                this.loadFactor = loadFactor;
                this.threshold = tableSizeFor(initialCapacity);
            } else {
                throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
            }
        }
    }

    public HashMap(int initialCapacity) {
        this(initialCapacity, 0.75F);
    }

    public HashMap() {
        this.loadFactor = 0.75F;
    }

   public HashMap(Map<? extends K, ? extends V> m) {
        this.loadFactor = 0.75F;
        this.putMapEntries(m, false);
    }

默认值大小

private static final long serialVersionUID = 362498820763181265L;
    static final int DEFAULT_INITIAL_CAPACITY = 16;//HashMap的默认容量，16;
    static final int MAXIMUM_CAPACITY = 1073741824;//最大容量
    static final float DEFAULT_LOAD_FACTOR = 0.75F;//默认加载因子 0.75
    static final int TREEIFY_THRESHOLD = 8;//Bucket中链表长度大于该默认值，转化为红黑树 8
    static final int UNTREEIFY_THRESHOLD = 6;
    static final int MIN_TREEIFY_CAPACITY = 64;

三、put操作

public V put(K key, V value) {
    if (table == EMPTY_TABLE) {
        inflateTable(threshold);
    }
    // 键为 null 单独处理
    if (key == null)
        return putForNullKey(value);
    int hash = hash(key);
    // 确定桶下标
    int i = indexFor(hash, table.length);
    // 先找出是否已经存在键为 key 的键值对，如果存在的话就更新这个键值对的值为 value
    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;
        }
    }

    modCount++;
    // 插入新键值对
    addEntry(hash, key, value, i);
    return null;
}

四、扩容原理

//判断增加元素后的容量是否大于老容量
if (++this.size > this.threshold) {
            this.resize();
        }
final HashMap.Node<K, V>[] resize() {
        HashMap.Node<K, V>[] oldTab = this.table;
        int oldCap = oldTab == null ? 0 : oldTab.length;
        int oldThr = this.threshold;
        int newThr = 0;//临界值=capacity*loadfactor
        int newCap;
        if (oldCap > 0) {
　　　　　　　　//如果容量大于最大容量，将threshold改为2倍的容量-1
            if (oldCap >= 1073741824) {
                this.threshold = 2147483647;
                return oldTab;
            }
　　　　　　　　//如果新容量的2倍还是小于最大容量，或者容量小于16容量就翻二倍
            if ((newCap = oldCap << 1) < 1073741824 && oldCap >= 16) {
                newThr = oldThr << 1;
            }
        } else if (oldThr > 0) {
            newCap = oldThr;
        } else {
            newCap = 16;
            newThr = 12;

　　　　}return newTab;
 }

总结：

HashMap的扩容机制：当`hashmap`被初始化创建的时候容量为16，由于初始化的加载因子的值为0.75，所以在集合大小为16*0.75=12的时候开始进行扩容，扩容的大小为当前集合的大小的2倍，也就是32，下一次集合大小为32*0.75=24时开始扩容.....

在Java8中，如果一条链表的元素个数超过树化阈值(默认是8)，并且集合的大小>=阈值(默认64)，就会进行树化（红黑树）

本文摘自：https://www.cnblogs.com/

HashMap源码分析2022-04-29 13:47:48

HashMap源码分析
2022-04-29 13:47:48