TreeMap是Java集合，它以有序的键及其相应的值的办法安排数据。它自JDK 1.2以来就已经存在。在内部，TreeMap运用红黑树来安排数据，这是一种自平衡二叉树。TreeMap中的键是仅有的标识符，默许状况下，TreeMap会根据键的自然次序来摆放数据。
关于整数键，它们是按键的升序存储的；关于String键，数据将按字母次序存储。咱们总是能够掩盖数据的默许排序，并在创立TreeMap时运用比较器来依照比较器中供给的逻辑以任何界说的办法进行自界说排序。在这篇文章中，咱们将具体评论一些自界说混合排序办法，并供给一些代码示例。
最盛行的查找和排序数据结构之一是二叉查找树（BST）。当涉及到查找操作性能时，二叉查找树具有最坏状况下的杂乱度为O(n)，这简直与线性查找相同。
红黑树关于每次刺进和删去操作都有一个恒定的时刻杂乱度O(log n)，由于它在每次操作后自我平衡，保证树一直是平衡的。这意味着树会主动以最优办法进行调整，这保证了查找和查找操作十分高效，而且关于任何数据集以及任何类型的查找操作，时刻杂乱度都不会超越O(log n)。
它运用一个简略但强大的机制，经过为树中的每个节点着色为赤色或黑色来保持一个平衡的结构。它能够被称为自平衡二叉查找树。它具有良好、高效的最坏状况下的运转时刻杂乱度。
【squids.cn】 全网zui贱价RDS，免费的迁移东西DBMotion、数据库备份东西DBTwin、SQL开发东西等
为什么运用TreeMap？
大多数BST操作（如查找、删去、查找和更新）需要O(log n)的时刻，其间n是二叉查找树中的节点数。关于一切键都沿着一个特定途径的偏斜的二叉树，这些操作的成本或许会变为O(n)，即它要么是一个左偏斜的二叉树，一切元素只沿左途径，要么是一个右偏斜的二叉查找树，一切元素都沿二叉查找树的右途径。这些类型的数据状况会使二叉查找树变得十分高效，一切类型的操作都会十分耗时。
除了查找操作外，刺进或删去操作在最坏的状况下也将需要O(n)的时刻杂乱度。这种状况会导致一个完全不平衡的二叉查找树，树的高度简直等于树中的节点数。
假如咱们保证每次刺进和删去后树的高度保持在O(log n)，那么咱们能够保证一切这些操作的上界为O(log n)，即便在数据高度偏斜的最坏状况下。这是经过引进红黑树来完结的，无论数据是偏斜还对错偏斜，树总是平衡的。红黑树的高度一直是O(log n)，其间n是树中的节点数。
默许状况下，红黑树具有以下特点，这些特点在TreeMap数据集中是固有的：
- 每个节点在TreeMap中都有指向父节点、右子节点和左子节点的引证。假如某个节点不存在，则在TreeMap中或许有这三个引证或削减的引证。
- 左子元素键的值总是小于父元素键的值。
- 右子元素键的值总是大于或等于TreeMap中父元素键的值。
- 每个树节点要么是赤色，要么是黑色。
- 树的根节点总是黑色的。
- 从根到任何叶节点的每条途径必须有相同数量的黑色节点。
- 不能有两个赤色节点相邻；即赤色节点不能是另一个赤色节点的父节点或子节点。
假如您查看下面的表格，红黑树在任何数据状况下的时刻杂乱度一直是相同的，它不受数据偏斜的影响，一直体现稳定。这使得TreeMap成为处理高容量数据集的十分高效和广泛运用的数据结构，在这些数据集中，咱们不确认底层数据的偏斜度，而且咱们能够在TreeMap上执行一些在其他映射数据结构（如HashMap）中不或许的共同操作。
时刻杂乱度
| 操作 | 均匀状况 | 最坏状况 |
| 查找 | O(log n) | O(log n) |
| 刺进 | O(log n) | O(log n) |
| 删去 | O(log n) | O(log n) |
在极点偏斜数据的状况下进行查找操作，这是在二叉查找树中安排数据的最坏状况，红黑树关于最坏的状况体现更好。红黑树能够用于高效地索引数据库中的数据，支撑需要快速查找和检索数据的技术。
在这篇文章中，我不打算具体解说红黑算法，但咱们将要点介绍TreeMap供给的一些小众功用，TreeMap是红黑树的一个杰出完结。
为何运用TreeMap
Java中的TreeMap类供给了丰厚的API，支撑多种查找操作。它不只支撑相等查找操作（被查找的元素存在于映射中），还支撑其他的特别查找操作，如查找映射中比给定元素稍大或稍小的元素。
此外，还有给定规模内的映射的子映射。只有当键依照某种次序摆放时，这种杂乱的查找操作才是或许的，而TreeMap对错常合适处理此类处理需求的数据结构。查找操作一般需要O(log n)时刻来回来成果。与HashMap不同，尽管HashMap只需要常数时刻，但执行查找操作需要对数时刻。这让人不禁想知道为什么它首要会被引进。
答案是，即便关于不属于HashMap的最坏状况类别的场景，HashMap以常数时刻杂乱度供给最优查找，数据也会以接连的办法保存在内存中。而关于TreeMap，没有这样的限制，它只运用存储项目所需的内存量，与运用接连内存区域的HashMap不同。如上所述的另一个要害原因是，TreeMap供给了执行特别查找操作的功用，这不只仅是在映射中找到给定的键，还能够找到其他键，这些键或许只是稍大、稍小或最小的键，或许是给定键规模的数据集的一部分。
与只供给等值查找操作的HashMap不同，即要查找的值等于Map中的任何键，TreeMap供给了以TreeMap的办法结构化的各种查找操作的才能。查找的才能使TreeMap成为处理杂乱查找用例的十分要害的数据结构，在我的经历中，我广泛地运用它来处理许多杂乱的业务需求。以下是TreeMap供给的一些最主要的查找功用。咱们首要将熟悉TreeMap供给的基本功用，之后将评论一些特别的查找需求，在这些需求中，咱们将结合上述TreeMap功用来到达不同品种的查找功用的特别需求：
- floorKey(K key): 此函数在TreeMap中查找小于或等于给定键的最大键。假如函数找不到这样的键，它将回来null。
- ceilingKey(K key): 此函数在TreeMap中查找大于或等于给定键的最小键。假如函数找不到这样的键，它将回来null。
- higherKey(K key): 此函数在TreeMap中查找严厉大于给定键的最小键。假如函数找不到这样的键，它将回来null。
- lowerKey(K key): 此函数在TreeMap中查找严厉小于给定键的最大键。假如函数找不到这样的键，它将回来null。
- subMap(K from Key, K toKey): 此函数查找此映射的部分视图，其键的规模从fromKey（包含）到toKey（不包含）。
- tailMap(K fromKey): 此函数查找此映射的部分视图，其键大于或等于fromKey。
- headMap(K toKey): 此函数查找与小于给定键的最小键相关的键值映射，或许假如没有这样的键则回来null。
现在咱们已经了解了TreeMap供给的要害功用和不同类型的查找功用，咱们将经过代码示例更好地理解它，稍后咱们将尝试界说一些新的特别查找和数据结构功用，运用上面列出的TreeMap功用的不同组合：
运用事例
咱们将运用下面捕获的职工实体。此类具有几个要害的职工特性，用于说明用例。
在以下职工类中，除了职工标识符特点外，咱们还捕获了一些将在用例中运用的额外的不同特点。这些特点如下：
- lastYearRating: 此特点保存了职工去年的评价评级。
- tenure: 此特点保存了职工与安排共度的年数的四舍五入值。
- currentSalary: 此特点存储了职工的当前年薪。
class Employee {
String empName;
String designation;
Integer empId;
String lastYearRating;
Integer tenure;
Integer currentSalary;
public Employee(String empName, String designation, Integer empId, String lastYearRating, Integer tenure, Integer currentSalary) {
this.empName = empName;
this.designation = designation;
this.empId = empId;
this.lastYearRating = lastYearRating;
this.tenure = tenure;
this.currentSalary = currentSalary;
}
@Override
public String toString() {
return "Employee{" +
"empName='" + empName + ''' +
", designation='" + designation + ''' +
", empId=" + empId +
", lastYearRating='" + lastYearRating + ''' +
", tenure=" + tenure +
", currentSalary=" + currentSalary +
'}';
}
public Integer getCurrentSalary() {
return currentSalary;
}
public void setCurrentSalary(Integer currentSalary) {
this.currentSalary = currentSalary;
}
public String getEmpName() {
return empName;
}
public void setEmpName(String empName) {
this.empName = empName;
}
public String getDesignation() {
return designation;
}
public void setDesignation(String designation) {
this.designation = designation;
}
public Integer getEmpId() {
return empId;
}
public void setEmpId(Integer empId) {
this.empId = empId;
}
public String getLastYearRating() {
return lastYearRating;
}
public void setLastYearRating(String lastYearRating) {
this.lastYearRating = lastYearRating;
}
public Integer getTenure() {
return tenure;
}
public void setTenure(Integer tenure) {
this.tenure = tenure;
}
}
鄙人面的代码示例中，咱们将运用TreeMap的功用来处理一些特别场景：
咱们将依照安排的工龄分桶来对一切职工进行分桶：咱们将有六个工龄桶，并将每个职工记载放在他们所属的正确桶中。这将运用TreeMap供给的一些特别功用，并将以十分简化的办法展现。接下来，咱们将为每个职工相关正确的工龄桶。
import java.util.ArrayList;
import java.util.TreeMap;
public class TreeMapCeilingFloorExample {
public static void main(String[] args) {
TreeMap<Integer, Object> tenureTreeMap = new TreeMap<>();
/* employee List, for illustration purpose just creating few dummy entries but in actual it can be read from source
* and can run into very high numbers including all employees for the organization */
ArrayList<Employee> empList = new ArrayList<Employee>();
empList.add(new Employee("John", "Engineer", 24, "A1", 6,150000));
empList.add(new Employee("David", "Manager", 35, "A2", 3,145000));
empList.add(new Employee("Fred", "Architect", 41, "B1", 2, 155000));
empList.add(new Employee("Brad", "Engineer", 21, "A3", 8,120000));
empList.add(new Employee("Jason", "Engineer", 32, "A1", 4,170000));
empList.add(new Employee("Adam", "Senior Engineer", 12, "A1", 14,85000));
empList.add(new Employee("Christie", "Director", 10, "A1", 15,178000));
empList.add(new Employee("Martha", "Accountant", 26, "A1", 6,85000));
empList.add(new Employee("Diana", "Engineer", 28, "A1", 6,108000));
empList.add(new Employee("Lisa", "Developer", 14, "A1", 12,82000));
/* Adding the default buckets for the employee tenures with 0-5, 6- 10, 11-15, 16-20, 21-25, 26-30
* Adding only higher bound as key so can efficiently use ceiling function to categorize all employees into right bucket */
tenureTreeMap.put(5, new ArrayList<Employee>());
tenureTreeMap.put(10, new ArrayList<Employee>());
tenureTreeMap.put(15, new ArrayList<Employee>());
tenureTreeMap.put(20, new ArrayList<Employee>());
tenureTreeMap.put(25, new ArrayList<Employee>());
tenureTreeMap.put(30, new ArrayList<Employee>());
/* Using ceilingKey function to check for every employee record and adding the employee to the right bucket.
* This is a simple illustration leveraging ceilingKey function to easily bucket employees into the right bucket */
empList.forEach(employeeObj -> {
Integer key = tenureTreeMap.ceilingKey(employeeObj.getTenure());
ArrayList matchingList = (ArrayList) tenureTreeMap.get(key);
matchingList.add(employeeObj);
tenureTreeMap.put(key, matchingList);
});
// Printing all Employees in the bucket starting with lowest to highest
tenureTreeMap.forEach((key, value) -> {
System.out.println("Key : " + key + " Value : ");
((ArrayList) value).forEach(empObj -> System.out.println());
});
}
}
成果
以下是工龄TreeMap的描绘，其间每个职工都被归入正确的工龄类别。要害是工龄桶的上界，下界是先前记载的上界+1。这是根据给定规模结构化数据的有用办法。这里咱们有六个工龄桶，如下：
- 0年到5年： 关于这个规模，要害是5，这是这个桶的上界。三个职工记载落入这个桶。
- 6年到10年： 关于这个规模，要害是10，这是这个桶的上界。四个职工记载落入这个桶。
- 11年到15年： 关于这个规模，要害是15，这是这个桶的上界。三个职工记载落入这个桶。
- 16年到20年： 关于这个规模，要害是20，这是这个桶的上界。没有职工记载落入这个桶。
- 21年到25年： 关于这个规模，要害是25，这是这个桶的上界。没有职工记载落入这个桶。
- 26年到30年： 关于这个规模，要害是30，这是这个桶的上界。没有职工记载落入这个桶。
修改
记住，TreeMap运用键的自然次序（或许供给的自界说比较器）来确认元素的次序。保证导入TreeMap类，并处理办法回来null的状况，假如没有合适的键依照你的用例。
以下代码函数为每个职工记载相关工龄规模。成果也打印在代码下面，显现每个职工记载的工龄规模。TreeMap是用工龄规模的上界作为键创立的，一切给定工龄规模的职工都在办法为数组列表的给定键对应的值中。
下面列出的代码运用天花板和地板函数在TreeMap中为任何键查找下界和上界。鄙人面的状况下，咱们企图找出每个职工记载的工龄规模，经过运用lowerKey函数获得下界。接下来运用ceilingEntry办法确认上界，构成规模字符串，并与每个职工记载相相关。这是一个简略的插图，展现了TreeMap功用的力气，经过利用内置功用轻松完结杂乱的需求。
成果：鄙人面的输出中，每个职工都有一个与该记载相相关的任期存储桶。
希望这篇文章协助你熟悉了TreeMap数据结构，并协助你运用内置的TreeMap函数来处理杂乱的数据分类和查找需求。
作者：Alejandro Duarte
更多技术干货请重视大众号“云原生数据库”
