JDK容器学习之TreeMap (一) : 底层数据结构

TreeMap

在日常的工作中,相比较与HashMap而言,TreeMap的使用会少很多,即使在某些场景,需要使用到排序的Map时,也更多的是选择 LinkedHashMap,那么这个TreeMap到底是个怎样的容器,又适用于什么样的应用场景呢?

1. 数据结构分析

分析数据结构,最好的方式无疑是google+baidu+源码了

1. 继承体系

看到源码第一眼,就会发现与HashMap不同的是 TreeMap 实现的是 NavigableMap, 而不是直接实现 Map

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

有必要仔细看下这个 NavigableMap,到底有些什么特殊之处

继承体系: Map -> SortMap -> NavigbleMap

其中 SortMap 新增了下面几个接口,目前也不知道具体有啥用,先翻译下源码注释

// 既然叫做SortMap, 要排序的话,当然需要一个比较器了
Comparator<? super K> comparator();

SortedMap<K,V> subMap(K fromKey, K toKey);

// 源码注释: 返回比Map中key比参数toKey小的所有kv对
SortedMap<K,V> headMap(K toKey);

// 源码注释:返回比Map中key比参数fromKey大或相等的所有kv对
SortedMap<K,V> tailMap(K fromKey);

K firstKey();

K lastKey();

接着就是 NavigableMap 定义的接口

// 返回Map中比传入参数key小的kv对中,key最大的一个kv对
Map.Entry<K,V> lowerEntry(K key);
K lowerKey(K key);

// 返回Map中比传入参数key小或相等的kv对中,key最大的一个kv对
Map.Entry<K,V> floorEntry(K key);
K floorKey(K key);

// 返回Map中比传入参数key大或相等的kv对中,key最小的一个kv对
Map.Entry<K,V> ceilingEntry(K key);
K ceilingKey(K key);

// 返回Map中比传入参数key大的kv对中,key最小的一个kv对
Map.Entry<K,V> higherEntry(K key);
K higherKey(K key);


Map.Entry<K,V> firstEntry();
Map.Entry<K,V> lastEntry();
Map.Entry<K,V> pollFirstEntry();
NavigableMap<K,V> descendingMap();
NavigableSet<K> navigableKeySet();
NavigableSet<K> descendingKeySet();

基本上这两个接口就是提供了一些基于排序的获取kv对的方式

2. 数据结构

看下内部的成员变量,发现可能涉及到数据结构的就只有下面的这个root了

private transient Entry<K,V> root;

结合 TreeMap 的命名来看,底层的结构多半就真的是Tree了,有树的根节点,一般来讲遍历都是没啥问题的

接下来看下 Entry的实现

static final class Entry<K,V> implements Map.Entry<K,V> {
  K key;
  V value;
  Entry<K,V> left;
  Entry<K,V> right;
  Entry<K,V> parent;
  boolean color = BLACK;

  /**
   * Make a new cell with given key, value, and parent, and with
   * {@code null} child links, and BLACK color.
   */
  Entry(K key, V value, Entry<K,V> parent) {
      this.key = key;
      this.value = value;
      this.parent = parent;
  }

  /**
   * Returns the key.
   *
   * @return the key
   */
  public K getKey() {
      return key;
  }

  /**
   * Returns the value associated with the key.
   *
   * @return the value associated with the key
   */
  public V getValue() {
      return value;
  }

  /**
   * Replaces the value currently associated with the key with the given
   * value.
   *
   * @return the value associated with the key before this method was
   *         called
   */
  public V setValue(V value) {
      V oldValue = this.value;
      this.value = value;
      return oldValue;
  }

  public boolean equals(Object o) {
      if (!(o instanceof Map.Entry))
          return false;
      Map.Entry<?,?> e = (Map.Entry<?,?>)o;

      return valEquals(key,e.getKey()) && valEquals(value,e.getValue());
  }

  public int hashCode() {
      int keyHash = (key==null ? 0 : key.hashCode());
      int valueHash = (value==null ? 0 : value.hashCode());
      return keyHash ^ valueHash;
  }

  public String toString() {
      return key + "=" + value;
  }
}

从Entry的内部成员变量可以看出,这是一个二叉树,且极有可能就是一颗红黑树(因为有个black

2. 添加一个kv对

通过新增一个kv对的调用链,来分析下这棵树,到底是不是红黑树

将put方法捞出来, 然后补上注释

public V put(K key, V value) {
  Entry<K,V> t = root;
  if (t == null) {
      // 奇怪的一行逻辑,感觉并没有什么用
      compare(key, key); // type (and possibly null) check

      root = new Entry<>(key, value, null);
      size = 1;
      modCount++;
      return null;
  }
  int cmp;
  Entry<K,V> parent;
  // split comparator and comparable paths
  Comparator<? super K> cpr = comparator;
  if (cpr != null) {
      // 下面这个循环可以得出树的左节点小于根小于右节点
      // 然后找到新增的节点,作为叶子节点在树中的位置
      // 注意这个相等时,直接更新了value值(这里表示插入一条已存在的记录)
      do {
          parent = t;
          cmp = cpr.compare(key, t.key);
          if (cmp < 0)
              t = t.left;
          else if (cmp > 0)
              t = t.right;
          else
              return t.setValue(value);
      } while (t != null);
  }
  else { 
      // 比较器不存在的逻辑,这时要求key继承 Comparable 接口
      if (key == null)
          throw new NullPointerException();
      @SuppressWarnings("unchecked")
          Comparable<? super K> k = (Comparable<? super K>) key;
      do {
          parent = t;
          cmp = k.compareTo(t.key);
          if (cmp < 0)
              t = t.left;
          else if (cmp > 0)
              t = t.right;
          else
              return t.setValue(value);
      } while (t != null);
  }
  
  // 创建一个Entry节点
  Entry<K,V> e = new Entry<>(key, value, parent);
  if (cmp < 0)
      parent.left = e;
  else
      parent.right = e;
      
  // 红黑树的重排
  fixAfterInsertion(e);
  size++;
  modCount++;
  return null;
}

从添加逻辑,可以得出结论:

  1. 树结构为二叉排序树(且不能出现相等的情况)
  2. 重排的方法可以保证该树为红黑树

所以新增一个kv对的逻辑就比较简单了

遍历树,将kv对作为叶子节点存在对应的位置

小结

红黑树相关可以作为独立的一个知识点,这里不详细展开,基本上通过上面的分析,可以得出下面几个点

  1. TreeMap 底层结构为红黑树
  2. 红黑树的Node排序是根据Key进行比较
  3. 每次新增删除节点,都可能导致红黑树的重排
  4. 红黑树中不支持两个or已上的Node节点对应红黑值相等

相关博文

  • JDK容器学习之HashMap (一) : 底层存储结构分析
  • JDK容器学习之HashMap (二) : 读写逻辑详解
  • JDK容器学习之HashMap (三) : 迭代器实现

关注更多

扫一扫二维码,关注 小灰灰blog

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据结构与算法

2010 求后序遍历

2010 求后序遍历 时间限制: 1 s 空间限制: 64000 KB 题目等级 : 白银 Silver 题目描述 Description 输入一...

33060
来自专栏来自地球男人的部落格

[LeetCode] 78. Subsets

【原题】 Given a set of distinct integers, nums, return all possible subsets. Not...

28390
来自专栏用户2442861的专栏

【Java集合源码剖析】ArrayList源码剖析

转载请注明出处:http://blog.csdn.net/ns_code/article/details/35568011

8930
来自专栏Java3y

TreeMap就这么简单【源码剖析】

23750
来自专栏编程理解

数据结构(二):二叉搜索树(Binary Search Tree)

二分法的查找过程是,在一个有序的序列中,每次都会选择有效范围中间位置的元素作判断,即每次判断后,都可以排除近一半的元素,直到查找到目标元素或返回不存在,所以

33710
来自专栏Jed的技术阶梯

普通树简介以及Java代码实现

88120
来自专栏python学习路

数据结构与算法(二)

排序与搜索 排序算法(英语:Sorting algorithm)是一种能将一串数据依照特定顺序进行排列的一种算法。 排序算法的稳定性 稳定性:稳定排序算法会让原...

36680
来自专栏Code_iOS

数据结构:集合

工程代码 Github: Data_Structures_C_Implemention -- Set

32730
来自专栏计算机视觉与深度学习基础

Leetcode 209 Minimum Size Subarray Sum

Given an array of n positive integers and a positive integer s, find the minima...

210100
来自专栏JAVA高级架构

Java数据结构与算法解析——2-3树

二叉查找树对于大多数情况下的查找和插入在效率上来说是没有问题的,但是他在最差的情况下效率比较低。平衡查找树的数据结构能够保证在最差的情况下也能达到lgN的效率,...

40270

扫码关注云+社区

领取腾讯云代金券