Skip to main content
 首页 » 编程设计

深入理解Java TreeMap

2022年07月19日134bonelee

本文我们学习Map的另一个实现TreeMap。它可以让key默认按照自然顺序排列,或提供比较器实现自定义排序。同时也和Map的另外两个实现(HashMap和 LinkHashMap)的相似性进行对比。

TreeMap键顺序

本节介绍TreeMap默认顺序,自定义键顺序。同时介绍TreeMap键顺序特性的应用。

缺省顺序

TreeMap默认按照自然顺序对键排序,对数字按升序,字符串按照字母顺序。请看示例:

@Test 
public void givenTreeMap_whenOrdersEntriesNaturally_thenCorrect() {
    
    TreeMap<Integer, String> map = new TreeMap<>(); 
    map.put(3, "val"); 
    map.put(2, "val"); 
    map.put(1, "val"); 
    map.put(5, "val"); 
    map.put(4, "val"); 
 
    assertEquals("[1, 2, 3, 4, 5]", map.keySet().toString()); 
} 

上面数字键并没有按顺序放入,但TreeMap确实为我们按照升序方式维护键顺序。同样对于字符串会按照字母顺序:

@Test 
public void givenTreeMap_whenOrdersEntriesNaturally_thenCorrect2() {
    
    TreeMap<String, String> map = new TreeMap<>(); 
    map.put("c", "val"); 
    map.put("b", "val"); 
    map.put("a", "val"); 
    map.put("e", "val"); 
    map.put("d", "val"); 
 
    assertEquals("[a, b, c, d, e]", map.keySet().toString()); 
} 

TreeMap与HashMap和LinkHashMap不同,并没有使用任何哈希算法,因为它没有使用数字存储条目。

自定义排序

如果自然顺序不能满足,我们可以自定义排序规则,通过给TreeMap构造函数传入排序方式。下面示例我们希望整数键按照降序排序:

@Test 
public void givenTreeMap_whenOrdersEntriesByComparator_thenCorrect() {
    
    TreeMap<Integer, String> map =  
      new TreeMap<>(Comparator.reverseOrder()); 
    map.put(3, "val"); 
    map.put(2, "val"); 
    map.put(1, "val"); 
    map.put(5, "val"); 
    map.put(4, "val"); 
         
    assertEquals("[5, 4, 3, 2, 1]", map.keySet().toString()); 
} 

HashMap 不能包装键存储顺序,也不能保证顺序始终相同。但是treeMap可以保证键总是按照特定顺序存储。

TreeMap键顺序应用

我们现在了解了TreeMap键按顺序存储,利用这个特性,可以实现特定查询:查找最大或最小元素,查找小于或大禹特定值的所有键等。

下面示例展示一小部分特性:

@Test 
public void givenTreeMap_whenPerformsQueries_thenCorrect() {
    
    TreeMap<Integer, String> map = new TreeMap<>(); 
    map.put(3, "val"); 
    map.put(2, "val"); 
    map.put(1, "val"); 
    map.put(5, "val"); 
    map.put(4, "val"); 
         
    Integer highestKey = map.lastKey(); 
    Integer lowestKey = map.firstKey(); 
    Set<Integer> keysLessThan3 = map.headMap(3).keySet(); 
    Set<Integer> keysGreaterThanEqTo3 = map.tailMap(3).keySet(); 
 
    assertEquals(new Integer(5), highestKey); 
    assertEquals(new Integer(1), lowestKey); 
    assertEquals("[1, 2]", keysLessThan3.toString()); 
    assertEquals("[3, 4, 5]", keysGreaterThanEqTo3.toString()); 
} 

TreeMap 内部实现

TreeMap实现NavigableMap 接口,其内部基于红黑树实现:

public class TreeMap<K,V> extends AbstractMap<K,V> 
  implements NavigableMap<K,V>, Cloneable, java.io.Serializable 

红黑树在此不深入,但为了理解TreeMap,需要记住一些关键的东西。

  1. 红黑树由一些节点组成的树型数据结构;可以想象一颗倒置的树,树根在上,树枝往下;树根包括加入树的第一个元素。从树根开始,任何左分支的节点总是小于该节点自身的元素,而右分支节点大于。由元素的自然顺序或自定义比较器决定大于或小于。该规则保证整个treemap的元素总是按照一定顺序。

  2. 红黑树是自平衡的二叉搜索树。该属性及上节的特性保证基本操作如搜索、get、put、删除的时间复杂度为O(log n)

    自我平衡是关键,当我们持续插入和删除元素时,想象树一遍会边长或另一边会变短。这意味着在短的一边操作时间更短,而长的一边时间会更长,这不是我们希望发生的。这就是为什么要设计红黑树,对于每次插入和删除操作,树任何边的最大高度被维护在O(log n),保证树持续平衡。

  3. 和hashMap、LinkHashMap一样,treeMap也不是同步的,因此在多线程场景中需要它们俩一样实现同步控制。

正确选择Map实现

下面简要对比三者:HashMap、LinkHashMap、TreeMap.

  • HashMap :Map的通用实现,提供快速存储和获取操作。但缺点是元素混乱无序。这导致在特定场景中性能较差,如迭代整个底层数组容量,而另外两个实现仅迭代实际存储的元素。
  • LinkHashMap :它在保留HashMap优势的同时增加元素顺序维护,因此迭代性能更好,它仅扫描实际存储元素,而不用考虑容量。
  • TreeMap :完全控制键的顺序存储方式,反之,性能相交另外两个稍差。

LinkHashMap 较 HashMap 消除了键的混乱,同时也没有导致如TreeMap那样性能损失。

总结

本文介绍了TreeMap类及其内部实现,同时对比了Map接口的三个实现。


本文参考链接:https://blog.csdn.net/neweastsun/article/details/120477684
阅读延展