本文共 5621 字，大约阅读时间需要 18 分钟。

Java集合框架-Map接口-HashMap原理和源码

HashMap底层实现原理

HashMap的put操作（以jdk7为例说明）

在实际使用HashMap时，put操作是最常见的操作之一。以下是jdk7版本的put操作流程：

jdk7与jdk8的区别

初始化方式

• jdk7：在实例化时，底层数组table初始化为空数组Entry[]。
• jdk8：底层数组table初始化为空数组Node[]。在第一次调用put方法时，底层数组会被初始化为长度为16。

底层结构

• jdk7：仅支持数组+链表结构。
• jdk8：支持数组+链表+红黑树结构。当链表长度超过TREEIFY_THRESHOLD（8）且数组长度大于64时，链表会转化为红黑树。

扩容机制

• jdk7：默认扩容至原容量的两倍。
• jdk8：当链表长度超过TREEIFY_THRESHOLD且容器大小超过MIN_TREEIFY_CAPACITY（64）时，链表会转化为红黑树。

HashMap源码解析

常量定义

• DEFAULT_INITIAL_CAPACITY：默认初始化容量，值为16。
• MAXIMUM_CAPACITY：最大支持容量，值为2^30。
• DEFAULT_LOAD_FACTOR：默认负载因子，值为0.75。
• TREEIFY_THRESHOLD：链表长度大于该值时，转化为红黑树。
• UNTREEIFY_THRESHOLD：红黑树存储的节点数小于该值时，退化为链表。
• MIN_TREEIFY_CAPACITY：红黑树存储的节点数小于该值时，转化为链表。

构造器分析

jdk7构造器

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

在空参构造器中，调用HashMap(int initialCapacity, float loadFactor)构造器，初始化容量和负载因子。

jdk8构造器

public HashMap() {    this.loadFactor = DEFAULT_LOAD_FACTOR;}

在空参构造器中，直接设置负载因子为默认值DEFAULT_LOAD_FACTOR，其他字段在第一次put操作时初始化。

put方法源码解析（jdk8）

put方法调用链

public V put(K key, V value) {    return putVal(hash(key), key, value, false, true);}

putVal方法

private V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {    Node[] tab = table;    int n = tab.length;    int i = (n - 1) & hash;    Node p = tab[i];    if (tab == null || n == 0) {        n = resize();        tab = table = new Node[n];        p = tab[i = (n - 1) & hash];    }    if (p == null) {        tab[i] = newNode(hash, key, value, null);        if (n > 0 && (n < MIN_TREEIFY_CAPACITY || (size > 64 && (size > 8 * n)))) {            treeifyBin(tab, hash);        }        size++;        if (size > threshold) {            resize();        }        return null;    }    if (p.hash == hash && (p.key == null ? key == null : key.equals(p.key))) {        e = p;    } else if (p instanceof TreeNode) {        e = ((TreeNode) p).putTreeVal(this, tab, hash, key, value);    } else {        for (int binCount = 0; ; ++binCount) {            if (e = p.next) {                if (e.hash == hash && (e.key == null ? key == null : key.equals(e.key))) {                    break;                }            } else {                p.next = newNode(hash, key, value, null);                if (binCount >= TREEIFY_THRESHOLD - 1) {                    treeifyBin(tab, hash);                }                break;            }        }        if (e != null) {            old = e.value;            if (!onlyIfAbsent || old == null) {                e.value = value;            }            afterNodeAccess(e);            return old;        }    }    modCount++;    size++;    if (size > threshold) {        resize();    }    afterNodeInsertion(evict);    return null;}

resize方法

private void resize() {    Node[] oldTab = table;    int oldCap = oldTab == null ? 0 : oldTab.length;    int oldThr = threshold;    int newCap = oldCap < MAXIMUM_CAPACITY ? oldCap << 1 : MAXIMUM_CAPACITY;    int newThr = oldCap < MAXIMUM_CAPACITY ? (int) (oldCap * loadFactor) : Integer.MAX_VALUE;    Node[] newTab = new Node[newCap];    table = newTab;    if (oldTab != null) {        for (int j = 0; j < oldCap; ++j) {            Node e = oldTab[j];            if (e == null) {                continue;            }            oldTab[j] = null;            if (e.next == null) {                int i = e.hash & (newCap - 1);                newTab[i] = e;            } else if (e instanceof TreeNode) {                TreeNode hd = null, tl = null;                do {                    TreeNode p = replacementTreeNode(e, null);                    if (tl == null) {                        hd = p;                    } else {                        p.prev = tl;                        tl.next = p;                    }                    tl = p;                } while ((e = p.next) != null);                if (hd != null) {                    hd.treeify(newTab);                }            } else {                int loHead = null, loTail = null;                int hiHead = null, hiTail = null;                Node next = e.next;                do {                    if (e.hash & oldCap == 0) {                        if (loTail == null) {                            loHead = e;                        } else {                            loTail.next = e;                            loTail = e;                        }                    } else {                        if (hiTail == null) {                            hiHead = e;                        } else {                            hiTail.next = e;                            hiTail = e;                        }                    }                } while ((e = next) != null);                loTail.next = null;                newTab[j] = loHead;                if (hiTail != null) {                    hiTail.next = null;                    newTab[j + oldCap] = hiHead;                }            }        }    }    threshold = newThr;}

总结

HashMap作为Java集合框架中的核心类，其底层实现采用数组+链表（或红黑树）的结构，通过哈希函数实现高效的插入、删除和查找操作。其默认容量为16，负载因子为0.75，扩容时会将当前容量的两倍进行扩展。在jdk8中，进一步优化了链表到红黑树的转化机制，提升了性能和并发安全性。