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

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

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

TreeMap简介

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

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

 

TreeMap数据结构

TreeMap底层通过红黑树(Red-Black tree)实现,是一种平衡二叉树。

TreeMap数据结构如下图所示:

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

红黑树规则特点:

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

 

TreeMap底层原理

1.TreeMap的继承关系

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

从上图中可以看出:

  • 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年+大厂架构经验,BAT资深面试官,就职于阿里巴巴、淘宝、百度等一线互联网大厂。

👇阅读更多mikechen架构文章👇

阿里架构 |双11秒杀 |分布式架构 |负载均衡 |单点登录 |微服务 |云原生 |高并发 |架构师

以上

关注作者「mikechen」公众号,获取更多技术干货!

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

评论交流
    说说你的看法