当前位置：首页 > ds >正文

Map（HashMap、LinkedHashMap、TreeMap）双列集合

ds 2025/7/28 9:24:52

HashMap:

一、核心特性：

二、底层实现原理：

三、扩容机制：

四、常用方法：

五、遍历操作：

LinkedHashMap:

TreeMap:

HashMap、LinkedHashMap、TreeMap的异同：

一、相同点：

二、不同点：

三、有序性：

`HashMap:`

HashMap 是 Java 集合框架中最常用的 键值对（key-value）存储结构，实现了 Map 接口，基于哈希表（数组 + 链表＋红黑树）实现，具有高效的增删改查操作。

一、核心特性：

（1）存储结构：键值对（key-value），通过 key 快速定位 value。

（2）允许 null：可以存储 null 键（仅允许一个）和 null 值（多个）。

（3）无序性：元素存储顺序与插入顺序无关，遍历顺序不固定。

（4）高效性：添加、删除、查询的平均时间复杂度为 O(1)。

（5）非线程安全：多线程环境下可能出现并发问题（如使用 ConcurrentHashMap 替代）。

二、底层实现原理：

HashMap 的底层是 哈希表，由数组、链表和红黑树组成：

（1）数组：每个元素是一个链表 / 红黑树的头节点，初始容量默认是 16（2 的幂次方）。

（2）链表：当多个 key 的哈希值相同时（哈希冲突），会以链表形式存储在同一数组中。

（3）红黑树：当链表长度超过阈值（默认 8）时，会转为红黑树，以提高查询效率（时间复杂度从 O (n) 优化为 O (log n)）。

三、扩容机制：

当 HashMap 中存储的键值对数量（size）超过 扩容阈值（threshold） 时，会自动触发扩容。
阈值计算公式：threshold = 当前容量（capacity） × 加载因子（loadFactor）

默认初始容量为 16，默认加载因子为 0.75f，因此初始阈值为 16 × 0.75 = 12。
当元素数量超过 12 时，容量会从 16 扩容至 32，新阈值为 32 × 0.75 = 24，以此类推。

（1）计算新容量：新容量 = 旧容量 × 2（始终保持为 2 的幂次方，这是 HashMap 的设计要求）。

（2）创建新哈希表：初始化一个容量为新容量的数组（新 "桶" 数组）

（3）迁移元素：将旧数组中的所有键值对重新计算哈希值，并迁移到新数组中：

对于链表中的元素：重新计算在新数组中的位置（因容量翻倍，哈希计算逻辑简化）。
对于红黑树中的元素：若树节点数少于 6，则退化为链表；否则拆分红黑树并迁移。

（4）更新参数：将新容量和新阈值（新容量 × 加载因子）赋值给当前 HashMap 实例。

四、常用方法：

（1）put(K key, V value)：添加键值对（若 key 已存在则覆盖 value）。

（2） putAll(map m) ：添加一个map双列集合，将指定map中的所有键值对存入当前map对象泛型类型一致，如果存在相同的键，值直接覆盖

（3）get(Object key)：根据 key 获取对应的 value（不存在返回 null）。

（4） getOrDefault(object key,v defaultValue)//根据key，返回【value值】:如果key不存在，则返回【默认值】

（5）remove(Object key)：根据 key 删除键值对。

（6） remove(Object key, Object value)：根据 key和所应用的值删除键值对。

（6）containsKey(Object key)：判断是否包含指定 key。

（7）containsValue(Object value)：判断是否包含指定 Value。

（8）isEmpty()：判空

（9）size():查看集合大小

（10）replace(K key, V value)：替换key 所对应的值为value

（11）replace(K key, V oldValue, V newValue）替换key 所对应的值value为newValue

package com.yuan.hashmap;import java.util.HashMap;public class Demo02 {public static void main(String[] args) {HashMap<String, String> hashMap = new HashMap<>();insertElement(hashMap);
//        selectElement(hashMap);deleteAndReplace(hashMap);}public static void insertElement(HashMap<String, String> hashMap) {System.out.println("=========进入到添加方法===========");//1.V put(K key，V value)存键值对，如果集合个存在此键，直接存，返回值为null//当存在此键时，返回值为上一次的键对应的value,用此value覆盖String item1 = hashMap.put("110", "北京");String item2 = hashMap.put("110", "天津");hashMap.put("130", "河北");hashMap.put("610", "陕西");System.out.println("第一次存返回值：" + item1);System.out.println("第二次存返回值：" + item2);//void putAll(map m)HashMap<String, String> hs1 = new HashMap<>();hs1.put("620", "甘肃");hs1.put("630", "宁夏");hs1.put("610", "内蒙");//将指定map中的所有键值对存入当前map对象  泛型类型一致，如果存在相同的键，值直接覆盖hashMap.putAll(hs1);//V putIfAbsent(K key,V value)如果存在此键，则不存，返回值为键所对应的旧值，如果不存在，直接放String oldValue = hashMap.putIfAbsent("611", "西安");System.out.println("putIfAbsent再次存放610键：" + oldValue);System.out.println(hashMap);}public static void selectElement(HashMap<String, String> hashMap) {System.out.println("=========进入到查看方法===========");System.out.println("目前当前元素为：" + hashMap);//V get(object key)根据key，返回【value值】:如果key不存在，则返回【null】String value1 = hashMap.get("120");System.out.println("键120对应的值为:" + value1);//V getOrDefault(object key,v defaultValue)//根据key，返回【value值】:如果key不存在，则返回【默认值】String value2 = hashMap.getOrDefault("120", "不知道");System.out.println("键120对应的值为:" + value2);//boolean containsKey(Object key)boolean b1 = hashMap.containsKey("611");System.out.println("键611是否存在:" + b1);//boolean containsValue(Object value)boolean b2 = hashMap.containsValue("宁夏1");System.out.println("值宁夏1是否存在:" + b2);//boolean isEmpty()System.out.println("集合map是否为空:" + hashMap.isEmpty());//int size():查看集合大小System.out.println("集合的size:" + hashMap.size());}public static void deleteAndReplace(HashMap<String, String> hashMap) {System.out.println("===========进入到删除和修改方法中===========");System.out.println("目前map中的元素为：" + hashMap);//根据key，替换value，并返回【原value值】；如果key不存在，则返回【null】String value = hashMap.replace("110", "北京");System.out.println(value);//根据key和value，替换value，返回true或者falseboolean b = hashMap.replace( "610",  "内蒙",  "陕西");System.out.println(b);//V remove(Object key)String oldValue = hashMap.remove("630");System.out.println("删除的键630对应的值为：" + oldValue);System.out.println("hashMap操作后：" + hashMap);boolean b2 = hashMap.remove("620", "甘肃");System.out.println("删除简直对是否成功：" + b2);System.out.println("hashMap操作后：" + hashMap);hashMap.clear();System.out.println("清空操作后：" + hashMap);}
}

五、遍历操作：

（1）keySet()：返回所有 key 的集合。

（2）values()：返回所有 value 的集合。

（3）entrySet()：返回所有键值对（Map.Entry）的集合，用于遍历。

package com.yuan.hashmap;import java.util.Collection;
import java.util.HashMap;
import java.util.Map;
import java.util.Set;public class Demo03 {public static void main(String[] args) {HashMap<String, String> hashMap = new HashMap<>();hashMap.put("110", "北京");hashMap.put("120", "天津");hashMap.put("130", "河北");hashMap.put("610", "陕西");hashMap.put("620", "甘肃");//1.Set<K> keySet() 获取所有的键Set<String> keys = hashMap.keySet();for (String key : keys) {String value = hashMap.get(key);System.out.printf("键为：%s - 值为%s\n", key, value);}//2.获取所有的value Collection<V> values()Collection<String> values = hashMap.values();System.out.println(values);//3.获取所有的键值对集合对象Set<Map.Entry<String, String>> entries = hashMap.entrySet();for (Map.Entry<String, String> entry : entries) {System.out.println(entry.getKey() + "=" + entry.getValue());}}
}

LinkedHashMap:

LinkedHashMap继承自HashMap,它的多种操作都是建立在HashMap操作的基础上的。和HashMap拥有相同的方法。同HashMap 不同的是，LinkedHashMap维护了一个双向链表，保证了插入的Entry中的顺序。这也是Linked的含义。

加入插入顺序为key1, key2, key3, key4, 那么就会维护一个红线所示的双向链表。为了实现双向链表，LinkedHashMap中提供了如下的Entry:

//LinkedHashMap中的node直接继承自HashMap中的Node。并且增加了双向的指针static class Entry<K,V> extends HashMap.Node<K,V> {//before表示上一个节点，after表示下一个节点//通过 before + after 属性，我们就可以形成一个以 Entry 为节点的链表。Entry<K,V> before, after;Entry(int hash, K key, V value, Node<K,V> next) {super(hash, key, value, next);}}

TreeMap:

HashMap是一种以空间换时间的映射表，它的实现原理决定了内部的Key是无序的，即遍历HashMap的Key时，其顺序是不可预测的（但每个Key都会遍历一次且仅遍历一次）。还有一种Map，它在内部会对Key进行排序，这种Map就是SortedMap。注意到SortedMap是接口，它的实现类是TreeMap。SortedMap保证遍历时以Key的顺序来进行排序。例如，放入的Key是"apple"、"pear"、"orange"，遍历的顺序一定是"apple"、"orange"、"pear"，因为String默认按字母排序：

public class Main {public static void main(String[] args) {Map<String, Integer> map = new TreeMap<>();map.put("orange", 1);map.put("apple", 2);map.put("pear", 3);for (String key : map.keySet()) {System.out.println(key);}// apple, orange, pear}
}

使用TreeMap时，放入的Key必须实现Comparable接口。String、Integer这些类已经实现了Comparable接口，因此可以直接作为Key使用。作为Value的对象则没有任何要求。如果作为Key的class没有实现Comparable接口，那么，必须在创建TreeMap时同时指定一个自定义比较器：

public class Main {public static void main(String[] args) {Map<Person, Integer> map = new TreeMap<>(new Comparator<Person>() {public int compare(Person p1, Person p2) {return p1.name.compareTo(p2.name);}});map.put(new Person("Tom"), 1);map.put(new Person("Bob"), 2);map.put(new Person("Lily"), 3);for (Person key : map.keySet()) {System.out.println(key);}// {Person: Bob}, {Person: Lily}, {Person: Tom}System.out.println(map.get(new Person("Bob"))); // 2}
}class Person {public String name;Person(String name) {this.name = name;}public String toString() {return "{Person: " + name + "}";}
}

注意到Comparator接口要求实现一个比较方法，它负责比较传入的两个元素a和b，如果a<b，则返回负数，通常是-1，如果a==b，则返回0，如果a>b，则返回正数，通常是1。TreeMap内部根据比较结果对Key进行排序。从上述代码执行结果可知，打印的Key确实是按照Comparator定义的顺序排序的。如果要根据Key查找Value，我们可以传入一个new Person("Bob")作为Key，它会返回对应的Integer值2。

另外，注意到Person类并未覆写equals()和hashCode()，因为TreeMap不使用equals()和hashCode()。

HashMap、LinkedHashMap、TreeMap的异同：

一、相同点：

1、都实现了 Map 接口，提供了基本的键值对操作方法（如 put()、get()、remove() 等）。

2、HashMap和LinkedHashMap允许存储 null 值（但对 null 键的支持有所不同）。

3、都是非线程安全的（多线程环境下需额外处理同步问题）

二、不同点：

特性	HashMap	LinkedHashMap	TreeMap
底层实现	基于哈希表（数组 + 链表 / 红黑树）	哈希表 + 双向链表	红黑树（一种自平衡二叉搜索树）
有序性	无序（插入顺序与遍历顺序无关）	有序（默认按插入顺序，可配置为访问顺序）	有序（按 key 的自然排序或自定义比较器）
查询效率	平均 O (1)，最坏 O (n)（哈希冲突严重时）	同 HashMap（额外维护链表不影响查询）	O (log n)（红黑树特性）
插入 / 删除效率	平均 O (1)，最坏 O (n)	同 HashMap（需维护链表指针，略低）	O(log n)
key 是否允许 null	允许 1 个 null 键	允许 1 个 null 键	不允许 null 键（会抛 NullPointerException）
排序依据	无	插入顺序或访问顺序（LRU 缓存常用）	key 的自然排序（如 Integer 升序）或自定义 `Comparator`
适用场景	一般场景，追求查询 / 插入效率	需要保持插入顺序或实现 LRU 缓存	需要按 key 排序的场景（如范围查询）