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

TreeMap

article 2025/1/4 16:39:27

一、什么是

  • TreeMap是Map接口的一个实现类

二、基本特性

(1)有序性

  • TreeMap中的键值对按照键的顺序进行排序，也就是说当你遍历 TreeMap 时，键值对会按照键的顺序排列。
  • 或者可以通过指定的Comparator来进行排序。

(2)线程是否安全

  • TreeMap是线程不安全的
  • 如果需要在多线程环境下使用，需要考虑外部同步或使用ConcurrentSkipListMap等线程安全的替代方案。

(3)null

  • TreeMap不允许null键。但是允许null值
  • 如果尝试插入 null 键，会抛出 NullPointerException。

(4)键的唯一性

  • 键是唯一的，但是键不能重复，值可以重复的 

三、底层结构 

TreeMap的底层结构是基于红黑树实现的。红黑树是一种自平衡的二叉搜索树，它具备以下特性：

 (1)节点颜色:每个节点都有颜色，红或黑

(2)根节点是黑色:树的根节点必须是黑色的

(3)红节点的子节点是黑色的:：如果有的话，红色节点的子节点必须是黑色;即红色节点不能有红色的父节点或子节点。

(4)黑色平衡:从任意节点到其每个叶子的所有路径都包含相同数量的黑色节点。

(5)自平衡:通过旋转和重新着色操作，红黑树能够在插入和删除操作后保持平衡，从而保证O(log n)的操作效率。

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;
    }
 
    // 其他方法...
}

四、 构造方法

(1)无参构造方法

  • 创建一个按照键的自然顺序排序的TreeMap。
  • import java.util.TreeMap; 
 
public class TreeMapExample1 {
    public static void main(String[] args) {
        // 创建一个按照键的自然顺序排序的 TreeMap
        TreeMap<String, Integer> treeMap = new TreeMap<>();
 
        // 插入键值对 
        treeMap.put("apple",  1);
        treeMap.put("banana",  2);
        treeMap.put("cherry",  3);
        treeMap.put("date",  4);
 
        // 遍历并打印 TreeMap
        for (String key : treeMap.keySet())  {
            System.out.println("Key:  " + key + ", Value: " + treeMap.get(key)); 
        }
    }
}

(2)带Comparator参数的构造方法

  • 创建一个按照自定义Comparator排序的TreeMap。
  • import java.util.Comparator; 
import java.util.TreeMap; 
 
public class TreeMapExample2 {
    public static void main(String[] args) {
        // 创建一个自定义 Comparator 
        Comparator<String> customComparator = (a, b) -> b.compareTo(a); 
 
        // 创建一个按照自定义 Comparator 排序的 TreeMap
        TreeMap<String, Integer> treeMap = new TreeMap<>(customComparator);
 
        // 插入键值对
        treeMap.put("apple",  1);
        treeMap.put("banana",  2);
        treeMap.put("cherry",  3);
        treeMap.put("date",  4);
 
        // 遍历并打印 TreeMap
        for (String key : treeMap.keySet())  {
            System.out.println("Key:  " + key + ", Value: " + treeMap.get(key)); 
        }
    }
}

(3)带SortedMap参数的构造方法

  • 根据提供的SortedMap创建一个新的TreeMap，并继承其排序规则。
  • import java.util.SortedMap; 
import java.util.TreeMap; 
 
public class TreeMapExample3 {
    public static void main(String[] args) {
        // 创建一个 SortedMap
        SortedMap<String, Integer> sortedMap = new TreeMap<>();
        sortedMap.put("apple",  1);
        sortedMap.put("banana",  2);
        sortedMap.put("cherry",  3);
        sortedMap.put("date",  4);
 
        // 根据提供的 SortedMap 创建一个新的 TreeMap
        TreeMap<String, Integer> treeMap = new TreeMap<>(sortedMap);
 
        // 遍历并打印 TreeMap
        for (String key : treeMap.keySet())  {
            System.out.println("Key:  " + key + ", Value: " + treeMap.get(key)); 
        }
    }
}

(4)带Map参数的构造方法

  • 根据提供的Map创建一个新的TreeMap。如果提供的Map不是SortedMap，则TreeMap会按照键的自然顺序或自定义Comparator（如果提供了的话）进行排序。
  • import java.util.HashMap; 
import java.util.Map; 
import java.util.TreeMap; 
 
public class TreeMapExample4 {
    public static void main(String[] args) {
        // 创建一个普通的 Map 
        Map<String, Integer> map = new HashMap<>();
        map.put("apple",  1);
        map.put("banana",  2);
        map.put("cherry",  3);
        map.put("date",  4);
 
        // 根据提供的 Map 创建一个新的 TreeMap
        TreeMap<String, Integer> treeMap = new TreeMap<>(map);
 
        // 遍历并打印 TreeMap
        for (String key : treeMap.keySet())  {
            System.out.println("Key:  " + key + ", Value: " + treeMap.get(key)); 
        }
    }
}

五、常用方法

  • put：插入键值对。
  • get：根据键获取值。
  • remove：根据键删除键值对。
  • containsKey：检查是否包含指定的键。
  • containsValue：检查是否包含指定的值。
  • size：返回键值对的数量。
  • isEmpty：检查是否为空。
  • clear：清空键值对。
public V put(K key, V value) {
    Entry<K,V> t = root;
    if (t == null) {
        compare(key, key); // type (and possibly null) check
        root = new Entry<>(key, value, null);
        size = 1;
        modCount++;
        return null;
    }
    int cmp;
    Entry<K,V> parent;
    // split comparator and comparable paths
    Comparator<? super K> cpr = comparator;
    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); 
        } while (t != null);
    } else {
        if (key == null)
            throw new NullPointerException();
        @SuppressWarnings("unchecked")
            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);
    }
    Entry<K,V> e = new Entry<>(key, value, parent);
    if (cmp < 0)
        parent.left  = e;
    else
        parent.right  = e;
    fixAfterInsertion(e);
    size++;
    modCount++;
    return null;
}
 
public V get(Object key) {
    Entry<K,V> p = getEntry(key);
    return (p==null ? null : p.value); 
}
 
public V remove(Object key) {
    Entry<K,V> p = getEntry(key);
    if (p == null)
        return null;
    V oldValue = p.value; 
    deleteEntry(p);
    return oldValue;
}
 
public boolean containsKey(Object key) {
    return getEntry(key) != null;
}
 
public boolean containsValue(Object value) {
    if (value == null)
        return containsNullValue();
    Iterator<V> i = values().iterator();
    while (i.hasNext())  {
        if (value.equals(i.next())) 
            return true;
    }
    return false;
}
 
public int size() {
    return size;
}
 
public boolean isEmpty() {
    return size == 0;
}
 
public void clear() {
    modCount++;
    size = 0;
    root = null;
}

六、 应用场景

1.需要对键值对进行排序的场景

  • 如根据学生的分数进行排名等。
  • import java.util.Map; 
import java.util.TreeMap; 

public class StudentScores {
    public static void main(String[] args) {
        TreeMap<String, Integer> studentScores = new TreeMap<>();
        studentScores.put("Alice",  85);
        studentScores.put("Bob",  92);
        studentScores.put("Charlie",  78);

        // TreeMap自动按键（分数）的自然顺序排序
        for (Map.Entry<String, Integer> entry : studentScores.entrySet())  {
            System.out.println(entry.getKey()  + ": " + entry.getValue()); 
        }
    }
}

2.需要快速查找、插入和删除键值对的场景

  • TreeMap的时间复杂度为O(log n)，适用于需要高效操作的情况。
  • import java.util.TreeMap; 

public class TreeMapOperations {
    public static void main(String[] args) {
        TreeMap<Integer, String> map = new TreeMap<>();
        map.put(1,  "One");
        map.put(3,  "Three");
        map.put(2,  "Two");

        // 查找
        System.out.println("Value  for key 2: " + map.get(2)); 

        // 插入
        map.put(4,  "Four");
        System.out.println("Map  after insertion: " + map);

        // 删除
        map.remove(3); 
        System.out.println("Map  after deletion: " + map);
    }
}

3.需要操作子映射的场景

  • 如获取某个范围内的键值对。
  • import java.util.TreeMap; 

public class TreeMapOperations {
    public static void main(String[] args) {
        TreeMap<Integer, String> map = new TreeMap<>();
        map.put(1,  "One");
        map.put(3,  "Three");
        map.put(2,  "Two");

        // 查找
        System.out.println("Value  for key 2: " + map.get(2)); 

        // 插入
        map.put(4,  "Four");
        System.out.println("Map  after insertion: " + map);

        // 删除
        map.remove(3); 
        System.out.println("Map  after deletion: " + map);
    }
}

七、常见问题及解决问题

1.多线程环境下的使用

  •  由于 TreeMap 是线程不安全的，如果在多线程环境中使用，需要进行外部同步或使用线程安全的替代方案。
  • 外部同步
  • import java.util.Collections; 
import java.util.Map; 
import java.util.TreeMap; 
 
public class ThreadSafeTreeMapExample {
    public static void main(String[] args) {
        Map<String, Integer> treeMap = Collections.synchronizedMap(new  TreeMap<>());
 
        // 插入键值对 
        treeMap.put("apple",  1);
        treeMap.put("banana",  2);
        treeMap.put("cherry",  3);
 
        // 遍历并打印 TreeMap
        synchronized (treeMap) {
            for (String key : treeMap.keySet())  {
                System.out.println("Key:  " + key + ", Value: " + treeMap.get(key)); 
            }
        }
    }
}
  • 使用 ConcurrentSkipListMap
  • import java.util.concurrent.ConcurrentSkipListMap; 
 
public class ConcurrentSkipListMapExample {
    public static void main(String[] args) {
        ConcurrentSkipListMap<String, Integer> concurrentMap = new ConcurrentSkipListMap<>();
 
        // 插入键值对
        concurrentMap.put("apple",  1);
        concurrentMap.put("banana",  2);
        concurrentMap.put("cherry",  3);
 
        // 遍历并打印 TreeMap
        for (String key : concurrentMap.keySet())  {
            System.out.println("Key:  " + key + ", Value: " + concurrentMap.get(key)); 
        }
    }
}

 2.null处理

  • TreeMap 不允许 null 键，但允许 null 值。如果需要处理可能包含 null 键的情况，可以在插入前进行检查。
  • import java.util.TreeMap; 
 
public class NullKeyHandlingExample {
    public static void main(String[] args) {
        TreeMap<String, Integer> treeMap = new TreeMap<>();
 
        // 插入键值对 
        String key = null;
        if (key != null) {
            treeMap.put(key,  1);
        } else {
            System.out.println("Cannot  insert null key.");
        }
 
        // 插入其他键值对
        treeMap.put("banana",  2);
        treeMap.put("cherry",  3);
 
        // 遍历并打印 TreeMap 
        for (String key : treeMap.keySet())  {
            System.out.println("Key:  " + key + ", Value: " + treeMap.get(key)); 
        }
    }
}

八、性能优化 

1.避免频繁的插入和删除操作

  • 频繁的插入和删除操作会导致红黑树的频繁调整，影响性能。如果需要频繁操作，可以考虑批量处理。

2.使用合适的 Comparator

  • 选择合适的 Comparator 可以提高排序效率。如果键的自然顺序已经满足需求，可以直接使用默认排序。 

九、 相关类和接口

TreeMap 实现了 NavigableMap 接口，提供了更多的导航方法，如 ceilingKey、floorKey、higherKey 和 lowerKey。

import java.util.NavigableMap; 
import java.util.TreeMap; 
 
public class NavigableMapExample {
    public static void main(String[] args) {
        NavigableMap<String, Integer> treeMap = new TreeMap<>();
        treeMap.put("apple",  1);
        treeMap.put("banana",  2);
        treeMap.put("cherry",  3);
        treeMap.put("date",  4);
        treeMap.put("fig",  5);
 
        // 获取大于等于 "banana" 的最小键 
        String ceilingKey = treeMap.ceilingKey("banana"); 
        System.out.println("Ceiling  Key: " + ceilingKey);
 
        // 获取小于等于 "cherry" 的最大键 
        String floorKey = treeMap.floorKey("cherry"); 
        System.out.println("Floor  Key: " + floorKey);
 
        // 获取大于 "banana" 的最小键
        String higherKey = treeMap.higherKey("banana"); 
        System.out.println("Higher  Key: " + higherKey);
 
        // 获取小于 "cherry" 的最大键
        String lowerKey = treeMap.lowerKey("cherry"); 
        System.out.println("Lower  Key: " + lowerKey);
    }
}

十、 常见面试题

TreeMap和HashMap的区别

特性TreeMapHashMap
排序按键的自然顺序或自定义 Comparator 排序不保证顺序，除非使用 LinkedHashMap 保持插入顺序
时间复杂度- 插入：O(log n)- 插入：O(1)
- 删除：O(log n)- 删除：O(1)
- 查找：O(log n)- 查找：O(1)
空间复杂度较高，因为需要维护红黑树结构较低，因为使用数组和链表/红黑树结构
线程安全性线程不安全，需要外部同步或使用 ConcurrentSkipListMap线程不安全，需要外部同步或使用 ConcurrentHashMap
键的唯一性键必须是唯一的键必须是唯一的
键的 null 值不允许 null 键允许一个 null 键
值的 null 值允许 null 值允许 null 值
实现接口NavigableMap（扩展了 SortedMap）Map
底层数据结构红黑树数组 + 链表/红黑树（JDK 1.8 及以上版本）
适用场景需要排序的场景，如排名、日志等需要快速查找、插入和删除的场景，如缓存、索引等
额外方法- firstKey()
- lastKey()
- subMap()
- headMap()
- tailMap()		- 无额外方法，但 LinkedHashMap 保持插入顺序

http://www.kler.cn/a/461159.html

相关文章：

  • C++ —— 模板类扩展
  • 图书项目：整合SSM
  • 【JVM】总结篇-字节码篇
  • 全新免押租赁系统助力商品流通高效安全
  • LVGL 移植到 Arduino IDE（适用SP32 Arduino RP系列）
  • C++类对象内存对齐方式
  • 如何使用C#与SQL Server数据库进行交互
  • 【每日学点鸿蒙知识】深色模式、Webview查看版本、window设置亮度、List缓存节点更新、预编译JS
  • 1panel fail2ban助力服务器SSH以及删除SSH登陆日志
  • ubuntu22 安装CUDA
  • 【蓝桥杯——物联网设计与开发】系列前言
  • git clone 超时
  • 吊舱激光测距核心技术详解！
  • 5G终端串口AT命令 FM650 常用命令
  • STM32-笔记24-智能开关垃圾桶盖
  • 数据要素在金融领域如何应用？
  • 深入理解C#的冒泡排序、快速排序、插入排序、选择排序和归并排序
  • v3.0.8- 「S+会员」新增专属运动秀，试试新穿搭吧- 与「好友」
  • 基于SpringBoot的电影购票平台的设计与实现（源码+SQL+LW+部署讲解）
  • PyQt6+OpenCV 项目练习
  • 2024年12月31日Github流行趋势
  • ThreadLocal的概述，及如何避免内存泄漏
  • 【优选算法 分治】深入理解分治算法：分治算法入门小专题详解
  • 【持续集成与持续部署（CI/CD）工具 - Jenkins】详解
  • PHP 中的魔术常量
  • BurstAttention：高效的分布式注意力计算框架