TreeMap详解(底层数据结构与实现原理)

之前有小伙伴面试被问到TreeMap的数据结构与底层实现，今天就重点来给大家分享TreeMap的底层实现@mikechen

TreeMap简介

在Java Map集合框架中，除了HashMap以外，TreeMap也是常用到的Java集合对象。

TreeMap 底层基于红黑树实现，可保证在log(n)时间复杂度内完成get、put 和 remove等方法操作，效率很高。

 

TreeMap数据结构

TreeMap底层通过红黑树（Red-Black tree）实现，是一种平衡二叉树。

TreeMap数据结构如下图所示：

红黑树规则特点：

• 节点分为红色或者黑色；
• 根节点必为黑色；
• 叶子节点都为黑色，且为null；
• 连接红色节点的两个子节点都为黑色（红黑树不会出现相邻的红色节点）；
• 从任意节点出发，到其每个叶子节点的路径中包含相同数量的黑色节点；
• 新加入到红黑树的节点为红色节点；

 

TreeMap底层原理

1.TreeMap的继承关系

从上图中可以看出：

• TreeMap实现继承于AbstractMap，并且实现了NavigableMap接口；
• TreeMap的本质是R-B Tree(红黑树)，它包含几个重要的成员变量： root, size, comparator；
• root 是红黑数的根节点，它是Entry类型，Entry是红黑数的节点，它包含了红黑数的6个基本组成成分：key(键)、value(值)、left(左孩子)、right(右孩子)、parent(父节点)、color(颜色)；
• Entry节点根据key进行排序，Entry节点包含的内容为value；
• 红黑数排序时，根据Entry中的key进行排序，Entry中的key比较大小是根据比较器comparator来进行判断的；
• size是红黑数中节点的个数。

 

2.TreeMap构造函数

// 默认构造函数。使用该构造函数，TreeMap中的元素按照自然排序进行排列。
TreeMap()

// 创建的TreeMap包含Map
TreeMap(Map<? extends K, ? extends V> copyFrom)

// 指定Tree的比较器
TreeMap(Comparator<? super K> comparator)

// 创建的TreeSet包含copyFrom
TreeMap(SortedMap<K, ? extends V> copyFrom)

 

3.TreeMap成员属性

/**
 * 我们前面提到TreeMap是可以自动排序的，默认情况下comparator为null，这个时候按照key的自然顺序进行排
 * 序，然而并不是所有情况下都可以直接使用key的自然顺序，有时候我们想让Map的自动排序按照我们自己的规则，
 * 这个时候你就需要传递Comparator的实现类
 */
private final Comparator<? super K> comparator;
 
/**
 * TreeMap的存储结构既然是红黑树，那么必然会有唯一的根节点。
 */
private transient Entry<K,V> root;
 
/**
 * Map中key-val对的数量，也即是红黑树中节点Entry的数量
 */
private transient int size = 0;
 
/**
 * 红黑树结构的调整次数
 */
private transient int modCount = 0;

 

4.TreeMap常用方法

1.增添元素

V put(K key, V value)：将指定映射放入该TreeMap中
V putAll(Map map)：将指定map放入该TreeMap中

 

2.删除元素

void clear()：清空TreeMap中的所有元素
V remove(Object key)：从TreeMap中移除指定key对应的映射

 

3.修改元素

V replace(K key, V value)：替换指定key对应的value值
boolean replace(K key, V oldValue, V newValue)：当指定key的对应的value为指定值时，替换该值为新值

 

4.查找元素

boolean containsKey(Object key)：判断该TreeMap中是否包含指定key的映射
boolean containsValue(Object value)：判断该TreeMap中是否包含有关指定value的映射
Map.Entry<K, V> firstEntry()：返回该TreeMap的第一个（最小的）映射
K firstKey()：返回该TreeMap的第一个（最小的）映射的key
Map.Entry<K, V> lastEntry()：返回该TreeMap的最后一个（最大的）映射
K lastKey()：返回该TreeMap的最后一个（最大的）映射的key
v get(K key)：返回指定key对应的value
SortedMap<K, V> headMap(K toKey)：返回该TreeMap中严格小于指定key的映射集合
SortedMap<K, V> subMap(K fromKey, K toKey)：返回该TreeMap中指定范围的映射集合（大于等于fromKey，小于toKey）

 

5.遍历接口

Set<Map<K, V>> entrySet()：返回由该TreeMap中的所有映射组成的Set对象
void forEach(BiConsumer<? super K,? super V> action)：对该TreeMap中的每一个映射执行指定操作
Collection<V> values()：返回由该TreeMap中所有的values构成的集合

 

5.TreeMap遍历方式

1.遍历TreeMap的键值对

// 假设map是TreeMap对象
// map中的key是String类型，value是Integer类型
Integer integ = null;
Iterator iter = map.entrySet().iterator();
while(iter.hasNext()) {
    Map.Entry entry = (Map.Entry)iter.next();
    // 获取key
    key = (String)entry.getKey();
        // 获取value
    integ = (Integer)entry.getValue();
}

第一步：根据entrySet()获取TreeMap的“键值对”的Set集合。

第二步：通过Iterator迭代器遍历“第一步”得到的集合。

 

2.遍历TreeMap的键

// 假设map是TreeMap对象
// map中的key是String类型，value是Integer类型
String key = null;
Integer integ = null;
Iterator iter = map.keySet().iterator();
while (iter.hasNext()) {
        // 获取key
    key = (String)iter.next();
        // 根据key，获取value
    integ = (Integer)map.get(key);
}

第一步：根据keySet()获取TreeMap的“键”的Set集合。

第二步：通过Iterator迭代器遍历“第一步”得到的集合。

 

3. 遍历TreeMap的值

// 假设map是TreeMap对象
// map中的key是String类型，value是Integer类型
Integer value = null;
Collection c = map.values();
Iterator iter= c.iterator();
while (iter.hasNext()) {
    value = (Integer)iter.next();
}

第一步：根据value()获取TreeMap的“值”的集合。

第二步：通过Iterator迭代器遍历“第一步”得到的集合。

 

TreeMap使用示例

public static void main(String[] args) {
        TreeMap<String, String> treeMap = new TreeMap<String,String>();
        treeMap.put("1", "1");
        treeMap.put("2", "2");
        treeMap.put("3", "3");
        treeMap.put("4", "4");
        treeMap.put("5", "5");
        treeMap.put("6", "6");
        treeMap.put("7", "7");
        System.out.println("treeMap:"+treeMap);
        System.out.println("treeMap.get(1):"+treeMap.get("1"));
        System.out.println("treeMap.get(2):"+treeMap.get("2"));
        System.out.println("treeMap.isEmpty():"+treeMap.isEmpty());
        System.out.println("treeMap.containsKey(2):"+treeMap.containsKey("3"));
        System.out.println("treeMap.keySet():"+treeMap.keySet());
        System.out.println("treeMap.entrySet():"+treeMap.entrySet());
        System.out.println("treeMap.size():"+treeMap.size());
        System.out.println("treeMap.firstEntry():"+treeMap.firstEntry());
        System.out.println("treeMap.lastEntry():"+treeMap.lastEntry());
        System.out.println("treeMap.ceilingEntry(3):"+treeMap.ceilingEntry("3"));
        System.out.println("treeMap.floorKey(3):"+treeMap.floorKey("3"));
        System.out.println("treeMap.higherKey(2):"+treeMap.higherKey("2"));
        System.out.println("treeMap.lowerEntry(2):"+treeMap.lowerEntry("2"));
        System.out.println("treeMap.replace(2, 8):"+treeMap.replace("2", "8"));
        System.out.println("treeMap.descendingMap():"+treeMap.descendingMap());
        System.out.println("treeMap.navigableKeySet():"+treeMap.navigableKeySet());
        System.out.println("treeMap.headMap(3):"+treeMap.headMap("3"));
        System.out.println("treeMap.tailMap(3):"+treeMap.tailMap("3"));

        System.out.println("迭代器遍历");
        Iterator<String> strItr = treeMap.keySet().iterator();
        while(strItr.hasNext()){
            System.out.println(treeMap.get(strItr.next()));
        }
    }

运行结果如下：

treeMap:{1=1, 2=2, 3=3, 4=4, 5=5, 6=6, 7=7}
treeMap.get(1):1
treeMap.get(2):2
treeMap.isEmpty():false
treeMap.containsKey(2):true
treeMap.keySet():[1, 2, 3, 4, 5, 6, 7]
treeMap.entrySet():[1=1, 2=2, 3=3, 4=4, 5=5, 6=6, 7=7]
treeMap.size():7
treeMap.firstEntry():1=1
treeMap.lastEntry():7=7
treeMap.ceilingEntry(3):3=3
treeMap.floorKey(3):3
treeMap.higherKey(2):3
treeMap.lowerEntry(2):1=1
treeMap.replace(2, 8):2
treeMap.descendingMap():{7=7, 6=6, 5=5, 4=4, 3=3, 2=8, 1=1}
treeMap.navigableKeySet():[1, 2, 3, 4, 5, 6, 7]
treeMap.headMap(3):{1=1, 2=8}
treeMap.tailMap(3):{3=3, 4=4, 5=5, 6=6, 7=7}
迭代器遍历
1
8
3
4
5
6
7

 

 

陈睿mikechen

10年+大厂架构经验，资深技术专家，就职于阿里巴巴、淘宝、百度等一线互联网大厂。

关注「mikechen」公众号，获取更多技术干货！

后台回复【面试】即可获取《史上最全阿里Java面试题总结》，后台回复【架构】，即可获取《阿里架构师进阶专题全部合集》