HashMap源码分析，看一遍就懂！("轻松掌握HashMap源码：一看即懂的深度解析！")

原创

ithorizon 7个月前 (10-21) 阅读数 22 #后端开发

轻松掌握HashMap源码：一看即懂的深度解析！

一、HashMap简介

HashMap是Java中非常常用的一种数据结构，它基于散列（Hash）原理实现，允许我们以键值对（Key-Value）的形式存储数据。HashMap具有以下特点：

允许使用null作为键和值

键的唯一性，不允许重复的键

高效的查询和修改操作，时间繁复度为O(1)

二、HashMap的数据结构

HashMap底层采用数组加链表（或红黑树）的数据结构。当哈希表中的条目数量超过数组的容量时，链表会转换成红黑树，以缩减查询时间。以下是HashMap的核心成员变量：


    transient Node<K,V>[] table;
    transient int size;
    transient int modCount;
    int threshold;
    final float loadFactor;

table是一个Node数组，用于存储键值对；size是存储的键值对数量；modCount是HashMap结构修改次数；threshold是扩容的阈值；loadFactor是负载因子，用于计算扩容时机。

三、HashMap的构造方法

HashMap提供了多个构造方法，以下是最常用的两个：


    public HashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0 || loadFactor <= 0)
            throw new IllegalArgumentException("Illegal initial capacity or load factor");
        this.loadFactor = loadFactor;
        this.threshold = initialCapacity;
        init();
    }
    public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }

第一个构造方法允许我们自定义初始容量和负载因子，第二个构造方法使用默认的负载因子（0.75）和初始容量（16）。init()方法用于初始化内部数据结构。

四、HashMap的put方法

HashMap的put方法用于添加键值对，以下是put方法的源码：


    public V put(K key, V value) {
        if (table == EMPTY_TABLE) {
            inflateTable();
        }
        if (key == null)
            return putForNullKey(value);
        int hash = hash(key);
        int i = indexFor(hash, table.length);
        for (Node<K,V> e = table[i]; e != null; e = e.next) {
            K 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;
    }

以下是put方法的关键步骤：

检查table是否为空，如果是，则进行初始化

处理null键的特殊情况

计算键的哈希值

按照哈希值计算数组索引

遍历链表，检查键是否已存在，如果存在，更新值并返回旧值

如果键不存在，将键值对添加到链表头部，并调整HashMap的大小

五、HashMap的get方法

HashMap的get方法用于获取键对应的值，以下是get方法的源码：


    public V get(Object key) {
        if (key == null)
            return getForNullKey();
        Node<K,V> e = getEntry(key);
        if (e == null)
            return null;
        return e.value;
    }
    final Node<K,V> getEntry(Object key) {
        if (key == null)
            return getForNullKey();
        int hash = hash(key);
        for (Node<K,V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) {
            K k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
                return e;
        }
        return null;
    }

以下是get方法的关键步骤：

处理null键的特殊情况

计算键的哈希值

按照哈希值计算数组索引

遍历链表，查找键对应的节点

如果找到，返回节点对应的值；如果未找到，返回null

六、HashMap的扩容机制

当HashMap中的元素数量约为阈值threshold时，会触发扩容操作。以下是扩容方法的源码：


    void resize(int newCapacity) {
        Node<K,V>[] oldTable = table;
        int oldCapacity = oldTable.length;
        if (oldCapacity == 16) {
            threshold = 16 * 3;
        } else if (oldCapacity >= 64) {
            threshold = oldCapacity * 3 / 2;
        } else {
            threshold = oldCapacity * 3;
        }
        Node<K,V>[] newTable = new Node[newCapacity];
        transfer(newTable, initHashSeedAsNeeded(newCapacity));
        table = newTable;
    }
    void transfer(Node<K,V>[] newTable, boolean rehash) {
        int newCapacity = newTable.length;
        for (Node<K,V> e : table) {
            while (null != e) {
                Node<K,V> next = e.next;
                int i = indexFor(e.hash, newCapacity);
                e.next = newTable[i];
                newTable[i] = e;
                e = next;
            }
        }
    }