treemap排序原理

TreeMap介绍和实现Comparator自定义比较器

与SortedSet接口类似，SortedMap也是一个结构，待排序的Map，其一个比较常用的实现类是TreeMap。

TreeMap的put(K key, V value)方法在每添加一个元素时，都会自动排序。

构造方法：

TreeMap()

使用键的自然顺序构造一个新的、空的树映射。

TreeMap(Comparator comparator)

构造一个新的、空的树映射，该映射根据给定比较器进行排序。

TreeMap(Map m)

构造一个与给定映射具有相同映射关系的新的树映射，该映射根据其键的自然顺序 进行排序。

创建自定义的Comparator比较器：

//这里根据字符的ASCII码大小进行降序排序：

class MyComparator2 implements Comparator{

@Override

public int compare(String o1, String o2) {

return pareTo(o1);

}

}

在SortedSet中，当保存对象时一定要自定义一个比较器Comparator，但是在SortedMap中，保存对象却不一定要，因为SortedMap是比较Key而不是Value，所以创建的自定义比较器也是针对Key的，比如上面创建的Comparator是针对Key类型为String的Map进行排序。

Map map = new TreeMap(new MyComparator2());

对于TreeMap的迭代和HashMap一样，同样有三种方法，以下是常用的其中一种：

Set> set = map.entrySet();

for(Iterator> iter = set.iterator();

iter.hasNext();){

Map.Entry entry = iter.next();

java中常用的键值类型

1.引言

1.1 概述

概述：

在Java编程语言中，键值类型是一种非常常见且重要的数据结构。它们用于存储和访问键值对（key-value）数据，其中键（key）是用于唯一标识数据的标识符，值（value）则是与该键相关联的数据。这种数据结构在实际应用中非常有用，特别是在需要快速访问、查找和更新数据的场景下。

在Java中，常用的键值类型包括HashMap、LinkedHashMap、TreeMap、Hashtable和Properties。每种类型都有其特定的特点和适用场景，下面将对每种类型进行详细介绍。

（接下来的内容可以分别对HashMap、LinkedHashMap、TreeMap、Hashtable和Properties进行介绍，包括其定义、特点和使用场景等）

1.2 文章结构

本文将介绍 Java 中常用的键值类型，主要包括 HashMap、LinkedHashMap、TreeMap、Hashtable 和 Properties。在本文中，将会详细介绍每种键值类型的特点、用法以及适用场景。

正文部分将分成五个小节，分别介绍每种键值类型。

2.1 HashMap

HashMap 是 Java 中最常用的键值对容器之一。它基于哈希表的实现，可以提供快速的插入、删除和查找操作。在 HashMap 中，键和值可以为任意对象，但是键是唯一的，而值可以重复。

2.2 LinkedHashMap

LinkedHashMap 是 HashMap 的一个子类，它除了具有

HashMap 的特性外，还维护一个插入顺序的链表。因此，在遍历

LinkedHashMap 时，可以按照插入的顺序获取元素。这种特性在某些场景下非常有用。

2.3 TreeMap

TreeMap 是一个基于红黑树的实现，它可以保持键的有序性。与

HashMap 不同，TreeMap 中的键是按照自然顺序或者自定义的比较器进行排序的。因此，可以在 TreeMap 中按照键的顺序获取元素。

Map排序（按key排序，按value排序）

主要分两种，按键排序、按值排序。 ⽽且，按key排序主要⽤于TreeMap，⽽按value排序则对于Map的⼦类们都适⽤。

⼀、按键排序

按Key排序主要⽤于TreeMap，可以实现按照Key值的⼤⼩，在对象插⼊时直接插⼊到合适的位置，保持Map的顺序性。

来看TreeMap的构造函数：( comparator)：构造⼀个新的、空的树映射，该映射根据给定⽐较器进⾏排序。

这⾥的⽐较器是key的⽐较器。所以定义⽐较器时⽤于⽐较的两个参数是Key的数据类型的对象。

实例代码如下：

public class MapSortTest {

public static void main(String[] args) {

Map stu=new TreeMap<>(new MyComparator());//传进来⼀个key的⽐较器对象来构造treemap

stu.put("apple", "55");

stu.put("boy", "32");

stu.put("cat", "22");

stu.put("dog", "12");

stu.put("egg", "11");

//map的遍历：把key抽取出来⽤set存放，然后⽤迭代器遍历keyset，同时⽤map.get(KEY)获取key所对应的value。

Set keySet=stu.keySet();

Iterator it=keySet.iterator();

while (it.hasNext()) {

String next = (String)it.next();

System.out.println(next+","+stu.get(next));

}

}}

//定义key的⽐较器，⽐较算法根据第⼀个参数o1,⼩于、等于或者⼤于o2分别返回负整数、0或者正整数，来决定⼆者存放的先后位置：返回负数则o1在前，正数则o2在前。

- 1 - treemap底层实现原理

Treemap是一种基于红黑树实现的数据结构，用于在Java中实现有序映射（SortedMap）接口。Treemap的底层实现原理是将所有元素保存在一个红黑树中，通过红黑树的特性保证数据的有序性和快速查找。

红黑树是一种自平衡的二叉搜索树，它具有以下性质：

1. 每个节点都是红色或黑色。

2. 根节点是黑色的。

3. 所有叶子节点都是黑色的。

4. 如果一个节点是红色的，则它的两个子节点都是黑色的。

5. 对于任意节点而言，从该节点到其子孙节点的所有路径上包含相同数量的黑色节点。

将元素插入到红黑树中，首先将其作为一个红色节点插入到树中。然后，根据红黑树的性质对节点进行旋转、重构等操作，使得红黑树保持平衡，同时保持有序性。

在Treemap中，元素的比较是通过实现Comparator接口或元素对象的Comparable接口来实现的。在插入元素时，会根据比较结果将元素插入到红黑树的合适位置。

由于红黑树的自平衡性，Treemap的添加、删除、查找等操作都具有较高的效率。同时，由于红黑树的有序性，Treemap可以方便地支持按照元素的自然顺序或指定顺序进行遍历、查找等操作。

总之，Treemap是一种高效、有序的数据结构，底层实现原理是 - 2 - 基于红黑树的。通过深入理解红黑树的原理和性质，可以更好地理解和应用Treemap。