从源码深入理解Java中的HashMap和TreeMap_Java

前言

在 java 集合框架中，map 接口是最常用的数据结构之一。而 hashmap 和 treemap 作为 map 的两个核心实现类，经常让开发者陷入选择的困惑：什么时候用 hashmap？什么时候用 treemap？它们的底层究竟有什么不同？

hashmap和treemap的整体架构

维度	hashmap	treemap
底层数据结构	数组 + 链表 + 红黑树	红黑树
元素顺序	无序，不保证顺序恒久不变	有序，按键的自然顺序或自定义比较器排序
时间复杂度	o(1) ~ o(log n)	o(log n)
键的要求	正确实现 hashcode() 和 equals()	实现 comparable 或传入 comparator
空键支持	允许 null 键和 null 值	不允许 null 键，允许 null 值
线程安全	否	否
继承关系	extends abstractmap	extends abstractmap, implements navigablemap
适用场景	高频增删查，不关心顺序	需要有序遍历、范围查询

hashmap源码解读

hashmap的成员变量：数组 + 链表 + 红黑树

hashmap 采用经典的哈希表设计，核心是一个 node<k,v>[] table 数组。

// hashmap 核心字段
transient node<k,v>[] table;          // 哈希表数组
transient int size;                   // 键值对数量
int threshold;                        // 扩容阈值 = capacity * loadfactor
final float loadfactor;               // 负载因子，默认 0.75

// 链表节点结构
static class node<k,v> {
    final int hash;
    final k key;
    v value;
    node<k,v> next;    // 指向下一个节点，形成链表
}


// 红黑树节点结构（继承自 linkedhashmap.entry，后者继承自 node）
static final class treenode<k,v> extends linkedhashmap.entry<k,v> {
    treenode<k,v> parent;
    treenode<k,v> left;
    treenode<k,v> right;
    treenode<k,v> prev;
    boolean red;
}

hashmap的常用方法

插入键值对：put(k key, v value)

put 是 hashmap 最核心的方法，它的实现展示了哈希表的所有设计精髓。

step1：哈希函数：扰动函数

static final int hash(object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashcode()) ^ (h >>> 16);
}

为什么要 h ^ (h >>> 16)？（高 16 位与低 16 位进行异或运算）
因为计算数组索引时使用 (n-1) & hash，如果 n 较小（如 16），只用到低 4 位，高位信息被浪费。异或运算让高位也参与索引计算，减少哈希冲突 。

step2：定位数组索引

// 数组长度必须是2的幂，这样 (n-1) & hash 等价于 hash % n，但更高效
int index = (n - 1) & hash;

step3：putval 核心逻辑

final v putval(int hash, k key, v value, boolean onlyifabsent, boolean evict) {
    node<k,v>[] tab; node<k,v> p; int n, i;
    // 1. 数组为空时，调用 resize() 初始化
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    
    // 2. 桶为空，直接新建节点放入
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newnode(hash, key, value, null);
    else {
        // 3. 桶不为空，处理冲突
        node<k,v> e; k k;
        // 3.1 检查第一个节点是否就是要找的key
        if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        // 3.2 如果是红黑树节点，走树化的插入逻辑
        else if (p instanceof treenode)
            e = ((treenode<k,v>)p).puttreeval(this, tab, hash, key, value);
        else {
            // 3.3 遍历链表
            for (int bincount = 0; ; ++bincount) {
                if ((e = p.next) == null) {
                    p.next = newnode(hash, key, value, null); // 尾插法
                    // 链表长度达到阈值8，转为红黑树
                    if (bincount >= treeify_threshold - 1)
                        treeifybin(tab, hash);
                    break;
                }
                // 找到相同key，跳出
                if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        // 4. 存在相同key，更新value
        if (e != null) {
            v oldvalue = e.value;
            if (!onlyifabsent || oldvalue == null)
                e.value = value;
            return oldvalue;
        }
    }
    ++modcount;
    // 5. 超过阈值，扩容
    if (++size > threshold)
        resize();
    return null;
}

流程图总结：

计算 key 的 hash 值 → 定位到数组索引
该位置为空 → 直接插入
该位置有节点：
- 判断是否为红黑树节点 → 执行红黑树插入
- 否则遍历链表 → 找到相同 key 则更新，否则尾插
- 链表长度 ≥ 8 → treeifybin() 转换红黑树
检查元素数量是否超过阈值 → 执行扩容

扩容机制：resize()

扩容是 hashmap 性能优化的关键，jdk 8 对此做了重大改进。

final node<k,v>[] resize() {
    node<k,v>[] oldtab = table;
    int oldcap = (oldtab == null) ? 0 : oldtab.length;
    int oldthr = threshold;
    int newcap, newthr = 0;
    
    if (oldcap > 0) {
        // 扩容：容量和阈值都翻倍
        newcap = oldcap << 1;
        newthr = oldthr << 1;
    } else {
        // 初始化：容量=16，阈值=12
        newcap = default_initial_capacity;
        newthr = (int)(default_load_factor * default_initial_capacity);
    }
    
    // 创建新数组
    node<k,v>[] newtab = (node<k,v>[])new node[newcap];
    table = newtab;
    
    if (oldtab != null) {
        // 迁移数据
        for (int j = 0; j < oldcap; ++j) {
            node<k,v> e = oldtab[j];
            if (e != null) {
                oldtab[j] = null;
                if (e.next == null) {
                    // 单节点，直接重新计算位置
                    newtab[e.hash & (newcap - 1)] = e;
                } else if (e instanceof treenode) {
                    // 红黑树节点的拆分
                    ((treenode<k,v>)e).split(this, newtab, j, oldcap);
                } else {
                    // 链表拆分：根据 hash & oldcap 分成高低两条链
                    node<k,v> lohead = null, lotail = null;  // 低位链（原位置）
                    node<k,v> hihead = null, hitail = null;  // 高位链（原位置+oldcap）
                    node<k,v> next;
                    do {
                        next = e.next;
                        if ((e.hash & oldcap) == 0) {
                            // 保留在原位置
                            if (lotail == null) lohead = e;
                            else lotail.next = e;
                            lotail = e;
                        } else {
                            // 移动到 原索引+oldcap 位置
                            if (hitail == null) hihead = e;
                            else hitail.next = e;
                            hitail = e;
                        }
                    } while ((e = next) != null);
                    // 将高低链放入新数组
                    if (lotail != null) {
                        lotail.next = null;
                        newtab[j] = lohead;
                    }
                    if (hitail != null) {
                        hitail.next = null;
                        newtab[j + oldcap] = hihead;
                    }
                }
            }
        }
    }
    return newtab;
}

jdk 8 扩容优化亮点：不再对每个元素重新计算 hash，而是利用 (e.hash & oldcap) == 0 判断元素是留在原位置还是移动到 原位置+oldcap。因为容量翻倍后，索引只取决于新增的那 1 位是 0 还是 1 。

根据key获取value： get (key)

public v get(object key) {
    node<k,v> e;
    return (e = getnode(hash(key), key)) == null ? null : e.value;
}

final node<k,v> getnode(int hash, object key) {
    node<k,v>[] tab; node<k,v> first, e; int n; k k;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        // 1. 检查第一个节点
        if (first.hash == hash && ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        if ((e = first.next) != null) {
            // 2. 红黑树查找
            if (first instanceof treenode)
                return ((treenode<k,v>)first).gettreenode(hash, key);
            // 3. 链表遍历
            do {
                if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

判断 key 相等的条件：hash 值相同且 equals() 返回 true。这就是重写 equals 必须重写 hashcode 的根本原因。

treemap源码解读

treemap的成员变量：纯粹的红黑树

treemap 没有任何数组结构，直接使用红黑树组织所有元素。红黑树是一种自平衡的二叉查找树，通过颜色约束（根黑、无连续红、黑高相等）保证树的高度不超过 2 l o g ( n ) 2log(n) 2log(n)，从而确保 o ( l o g n ) o(log n) o(logn) 的操作复杂度。

节点结构：entry

static final class entry<k,v> implements map.entry<k,v> {
    k key;
    v value;
    entry<k,v> left;    // 左子节点
    entry<k,v> right;   // 右子节点
    entry<k,v> parent;  // 父节点
    boolean color = black;  // 节点颜色
    
    entry(k key, v value, entry<k,v> parent) {
        this.key = key;
        this.value = value;
        this.parent = parent;
    }
}

每个树节点包含：键值对、左右子节点引用、父节点引用、以及红黑树的颜色标记。

核心成员属性

public class treemap<k,v> extends abstractmap<k,v>
    implements navigablemap<k,v>, cloneable, java.io.serializable {
    
    private final comparator<? super k> comparator;  // 比较器
    private transient entry<k,v> root;               // 根节点
    private transient int size = 0;                  // 元素个数
    private transient int modcount = 0;              // 结构性修改次数
}

comparator 决定了排序方式：为 null 时使用 key 的自然顺序（key 必须实现 comparable），否则使用指定的比较器。

treemap的常用方法

插入键值对： put(k key, v value)

treemap 的插入本质上是红黑树的插入操作。

public v put(k key, v value) {
    entry<k,v> t = root;
    // 1. 空树，新节点直接作为根
    if (t == null) {
        compare(key, key); // 类型检查
        root = new entry<>(key, value, null);
        size = 1;
        modcount++;
        return null;
    }
    
    int cmp;
    entry<k,v> parent;
    comparator<? super k> cpr = comparator;
    // 2. 查找插入位置（二叉搜索树查找）
    if (cpr != null) {
        // 使用自定义比较器
        do {
            parent = t;
            cmp = cpr.compare(key, t.key);
            if (cmp < 0)
                t = t.left;
            else if (cmp > 0)
                t = t.right;
            else
                return t.setvalue(value);  // key已存在，更新value
        } while (t != null);
    } else {
        // 使用自然顺序
        if (key == null)
            throw new nullpointerexception();  // treemap 不允许 null 键
        comparable<? super k> k = (comparable<? super k>) key;
        do {
            parent = t;
            cmp = k.compareto(t.key);
            if (cmp < 0)
                t = t.left;
            else if (cmp > 0)
                t = t.right;
            else
                return t.setvalue(value);
        } while (t != null);
    }
    
    // 3. 创建新节点并插入
    entry<k,v> e = new entry<>(key, value, parent);
    if (cmp < 0)
        parent.left = e;
    else
        parent.right = e;
    
    // 4. 修复红黑树平衡（关键！）
    fixafterinsertion(e);
    size++;
    modcount++;
    return null;
}

二分查找定位：从根节点开始，根据比较结果向左或向右递归查找
key 存在则覆盖：找到相同 key 时，只更新 value，不新增节点
红黑树再平衡：fixafterinsertion(e) 负责在插入后恢复红黑树的平衡性质，包括左旋、右旋、变色三种操作

根据key获取value：get (key)

public v get(object key) {
    entry<k,v> p = getentry(key);
    return (p == null ? null : p.value);
}

final entry<k,v> getentry(object key) {
    // 使用比较器或自然顺序进行二叉搜索
    if (comparator != null)
        return getentryusingcomparator(key);
    if (key == null)
        throw new nullpointerexception();
    comparable<? super k> k = (comparable<? super k>) key;
    entry<k,v> p = root;
    while (p != null) {
        int cmp = k.compareto(p.key);
        if (cmp < 0)
            p = p.left;
        else if (cmp > 0)
            p = p.right;
        else
            return p;
    }
    return null;
}

查找逻辑就是标准的二叉搜索树查找：比当前节点小则走左边，大则走右边，相等则返回。

treemap 的导航方法

treemap 实现了 navigablemap 接口，提供了一套强大的导航查询方法：

// 获取最小的键值对
map.entry<k,v> firstentry();

// 获取最大的键值对
map.entry<k,v> lastentry();

// 返回严格小于给定key的最大键值对
map.entry<k,v> lowerentry(k key);

// 返回小于等于给定key的最大键值对
map.entry<k,v> floorentry(k key);

// 返回大于等于给定key的最小键值对
map.entry<k,v> ceilingentry(k key);

// 返回严格大于给定key的最小键值对
map.entry<k,v> higherentry(k key);

实战示例：

treemap<integer, string> map = new treemap<>();
map.put(1, "a");
map.put(3, "c");
map.put(5, "e");

system.out.println(map.ceilingentry(2));  // 3=c
system.out.println(map.floorentry(4));    // 3=c
system.out.println(map.higherkey(3));     // 5

treemap 的范围视图

// 返回 [fromkey, tokey) 范围内的子 map
sortedmap<k,v> submap(k fromkey, k tokey);

// 返回小于 tokey 的部分
sortedmap<k,v> headmap(k tokey);

// 返回大于等于 fromkey 的部分
sortedmap<k,v> tailmap(k fromkey);

treemap 的自定义排序

// 降序排列
treemap<string, integer> map = new treemap<>((a, b) -> b.compareto(a));
map.put("tom", 85);
map.put("jack", 92);
map.put("lily", 76);
// 遍历结果将按降序输出

或者实现 comparable 接口：

class person implements comparable<person> {
    string name;
    int age;
    
    @override
    public int compareto(person o) {
        return integer.compare(this.age, o.age);  // 按年龄排序
    }
}

完整测试

public class maptest {
    public static void main(string[] args) {
        // 分别测试 hashmap 和 treemap
        system.out.println("====== hashmap 测试 (无序) ======");
        testmapapi(new hashmap<>());

        system.out.println("\n====== treemap 测试 (按 key 升序) ======");
        testmapapi(new treemap<>());
    }

    public static void testmapapi(map<string, integer> map) {
        // 1. put(k key, v value): 设置映射关系
        map.put("apple", 10);
        map.put("banana", 20);
        map.put("orange", 30);
        // 重复 put 会覆盖旧值，并返回旧值
        integer oldval = map.put("apple", 15);
        system.out.println("apple 原来的值是: " + oldval + ", 现在是: " + map.get("apple"));

        // 2. get(object key): 获取 value
        system.out.println("banana 的数量: " + map.get("banana"));
        system.out.println("pear 的数量 (不存在): " + map.get("pear")); // 返回 null

        // 3. getordefault(object key, v defaultvalue): 不存在则返回默认值
        system.out.println("pear 的默认值: " + map.getordefault("pear", 0));

        // 4. containskey & containsvalue: 判断是否存在
        system.out.println("是否包含 key 'orange': " + map.containskey("orange"));
        system.out.println("是否包含 value 50: " + map.containsvalue(50));

        // 5. keyset(): 返回所有 key 的不重复集合
        set<string> keys = map.keyset();
        system.out.println("所有的 key: " + keys);

        // 6. values(): 返回所有 value 的可重复集合
        collection<integer> values = map.values();
        system.out.println("所有的 value: " + values);

        // 7. entryset(): 返回所有的 key-value 映射关系（最推荐的遍历方式）
        system.out.println("遍历所有 entry:");
        for (map.entry<string, integer> entry : map.entryset()) {
            system.out.println("  - 商品: " + entry.getkey() + ", 价格: " + entry.getvalue());
        }

        // 8. remove(object key): 删除并返回被删除的 value
        integer removedval = map.remove("orange");
        system.out.println("被删除的 orange 价格是: " + removedval);
        system.out.println("删除后的 map: " + map);
    }
}

treemap<integer, string> treemap = new treemap<>();
treemap.put(10, "value10");
treemap.put(30, "value30");
treemap.put(50, "value50");
treemap.put(20, "value20");

// 1. 获取边界
system.out.println("最小 key: " + treemap.firstkey()); // 10
system.out.println("最大 key: " + treemap.lastkey());  // 50

// 2. 查找邻居
system.out.println("比 30 大的下一个: " + treemap.higherkey(30)); // 50
system.out.println("大于等于 25 的最小 key: " + treemap.ceilingkey(25)); // 30

// 3. 范围截取 (左闭右开)
system.out.println("10到35之间的子集: " + treemap.submap(10, 35)); // {10=..., 20=..., 30=...}

// 4. 倒序
system.out.println("倒序遍历: " + treemap.descendingmap());

性能分析与选型建议

时间复杂度对比

操作	hashmap	treemap
get	o(1) 平均，o(log n) 最差（红黑树）	o(log n)
put	o(1) 平均，o(log n) 最差	o(log n)
remove	o(1) 平均，o(log n) 最差	o(log n)
遍历	o(n)，无序	o(n)，有序
范围查询	不支持	o(log n + m)

空间占用

hashmap：需要维护数组、链表节点、红黑树节点。在未满负载时会有空间浪费（数组空槽位）
treemap：每个节点都需要存储 left、right、parent 指针和 color 属性，单节点内存开销更大，但空间利用率稳定

选型决策树

需要 map 实现？
    │
    ├── 需要键有序？── 是 ──→ treemap
    │                        （注意：键不能为 null）
    │
    ├── 需要范围查询？── 是 ──→ treemap
    │
    ├── 追求极致性能？── 是 ──→ hashmap
    │                        （o(1) vs o(log n)）
    │
    └── 其他情况 ────────────→ hashmap
                              （默认选择）

场景	推荐	理由
本地缓存	hashmap	o(1) 查询，性能最优
需要排序输出	treemap	天生有序，无需额外排序
分页查询	treemap	submap 天然支持范围截取
海量数据存储	hashmap	扩容后可保持 o(1) 性能
统计排名	treemap	按键排序后取前 n 名很方便
配置项存储	hashmap	无序，读取频繁，性能优先

面试笔试题

hashmap 和 treemap 有什么区别？

维度	hashmap	treemap
底层数据结构	数组 + 链表 + 红黑树	红黑树
元素顺序	无序，不保证顺序恒久不变	有序，按键的自然顺序或自定义比较器排序
时间复杂度	o(1) ~ o(log n)	o(log n)
键的要求	正确实现 hashcode() 和 equals()	实现 comparable 或传入 comparator
空键支持	允许 null 键和 null 值	不允许 null 键，允许 null 值
线程安全	否	否
继承关系	extends abstractmap	extends abstractmap, implements navigablemap
适用场景	高频增删查，不关心顺序	需要有序遍历、范围查询

如何决定使用 hashmap 还是 treemap？

参考答案：

对于插入、删除、定位元素这类操作，hashmap 是最佳选择
如果需要有序遍历 key 集合，或需要范围查询（如 submap）、邻近查找（如 ceilingkey），选择 treemap
一句话总结：要速度用 hashmap，要顺序用 treemap

hashmap 和 treemap 在性能上有什么区别？什么场景下 treemap 更合适？

参考答案：

hashmap：o(1) 常数级查找，适合高频随机访问
treemap：o(log n) 查找，适合有序遍历、范围查询、最值查找
treemap 典型场景：价格区间筛选、时间范围查询、按成绩排名、版本路由等

hashmap 的 put 方法流程是怎样的？

参考答案：

计算 key 的 hashcode，通过扰动函数（高 16 位异或低 16 位）得到 hash 值
判断数组是否初始化，若未初始化则调用 resize 初始化
通过 (n-1) & hash 计算索引位置
若该位置为空，直接插入
若不为空：
判断首节点是否相同（hash 相等且 key 相等），相同则覆盖
判断是否为红黑树节点，是则走树插入逻辑
否则遍历链表，找到相同 key 则覆盖，找不到则尾插法插入
链表长度 ≥ 8 且数组长度 ≥ 64 时，转为红黑树
判断 size 是否超过阈值，超过则扩容

hashmap 是如何解决哈希冲突的？

参考答案：

拉链法：冲突元素以链表形式存储在同一桶中
红黑树优化：链表长度 ≥ 8 且数组长度 ≥ 64 时，转为红黑树，将查找复杂度从 o(n) 降为 o(log n)
扰动函数：(h = key.hashcode()) ^ (h >>> 16) 让高位参与索引计算，减少冲突

hashmap的扩容（resize）/ 树化阶段 (treeify) / 退化阶段 (untreeify) 过程

为什么 hashmap 的容量必须是 2 的幂？

参考答案：

位运算效率高：(n-1) & hash 等价于 hash % n，但位运算更快
均匀分布：2 的幂保证低位掩码（n-1 全为 1），使 hash 分布更均匀，减少冲突
扩容时便于迁移：扩容后只需判断新增位的值即可确定新位置

hashmap中为什么链表转红黑树的阈值是 8？退化阈值是 6?

参考答案：

泊松分布：负载因子 0.75 下，链表长度达到 8 的概率极低（约 0.00000006）
性能考量：链表长度 8 时查询性能已明显退化，需要树化优化
退化阈值是 6：留出 7 作为缓冲区间，避免频繁转换

hashmap 为什么线程不安全？

参考答案：

数据覆盖：多线程 put 时，若 hash 相同且同时判断到槽位为空，后执行的会覆盖先执行的数据
size 不准确：++size 非原子操作，多线程下可能导致实际 size 偏小
jdk 7 死循环：扩容时头插法可能导致链表成环（jdk 8 已改为尾插法）
解决方案：使用 concurrenthashmap 或 collections.synchronizedmap()

什么是红黑树？为什么 treemap 用它而不用 avl 树？

对比项	红黑树	avl 树
平衡标准	黑高平衡（宽松）	严格高度平衡（高度差 ≤ 1）
插入/删除旋转次数	最多 3 次	可能 o(log n) 次
查询效率	o(log n)，常数稍大	略快（更严格平衡）
适用场景	频繁增删	高频查询

treemap 选择红黑树是因为它在增删和查询之间取得了更好平衡

treemap 支持 null 键吗？

参考答案：

自然排序时：不支持，会抛 nullpointerexception
自定义 comparator 时：可以在比较器中处理 null，从而支持 null 键
允许 null 值

重写 equals 为什么必须重写 hashcode？

参考答案：

hashmap 判断 key 相等需要同时满足：hashcode 相等 且 equals 返回 true
若只重写 equals 不重写 hashcode：
两个 equals 相等的对象，hashcode 可能不同
放入 hashmap 后，用另一个对象去 get，会因为 hash 不同定位到不同桶而取不出来
违反 java 规约，导致集合行为不确定

总结

到此这篇关于java中hashmap和treemap的文章就介绍到这了,更多相关java中hashmap和treemap内容请搜索代码网以前的文章或继续浏览下面的相关文章希望大家以后多多支持代码网！


验证码：

从源码深入理解Java中的HashMap和TreeMap

2026年07月27日 • Java •我要评论

前言