【Java集合】TreeMap分析

时间：2020-11-24 17:17:45

【Java集合】TreeMap分析

初识TreeMap

TreeMap的继承关系

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

// 抽象类AbstractMap继承实现关系
public abstract class AbstractMap<K,V> implements Map<K,V>

// 接口Navigable的继承关系
public interface NavigableMap<K,V> extends SortedMap<K,V>

// 接口SortedMap的继承关系
public interface SortedMap<K,V> extends Map<K,V>

// Clonable 和 Serializable 是标记接口，不包含抽象方法

TreeMap跟HashMap在功能上的最大区别是，TreeMap支持有序类型的操作。
原因是，TreeMap的原理是红黑树，而HashMap的原理是拉链法的散列表（Java8中，为了提高查找速度，如果链表超过8，则会将链表转换成红黑树）

红黑树

红黑树是完美黑色平衡的二叉树，即所有的空链接到根结点的路径中的黑色结点（链接）的个数相等。

为了保证红黑树是近似平衡的二叉树搜索树，红黑树满足：
1. 结点是红色或者是黑色的
2. 根结点为黑色的
3. 叶子结点为黑色的
4. 红色结点的子结点必定是黑色的（红色结点是黑色结点的左孩子）
5. 从任意一结点出发，到其后继的叶子结点的路径中，黑色结点的数目相同

由此，可以得到一个重要的结论：
根结点到叶子结点的最长路径不会大于根结点到叶子结点最短路径的 2 倍。
这样，可以将红黑树看作近似平衡的二叉搜索树。

TreeMap源码分析

put方法

put方法包括两个步骤：
1. 根据键的大小找到合适的位置，将该键值对作为红色结点插入
2. 调整为红黑树（满足红黑树的规则）

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;
// 1 根据键的大小找到合适的位置，将该键值对作为红色结点插入
// 比较器优先于Comparable
if (cpr != null) {  // 若比较器不为空，则用比较器查找新结点合适的位置
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);  // 如果该key已经村存在，则更新value
         } while (t != null);
     }
else {
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<K,V> e = new Entry<>(key, value, parent);
if (cmp < 0)
parent.left = e;
else
parent.right = e;
// 2 调整为红黑树（满足红黑树的规则） 
     fixAfterInsertion(e);
     size++;
     modCount++;
return null;
 }

调整为红黑树（满足红黑树的规则）的方法fixAfterInsertion

新插入结点后，将树调整为红黑树的方式有
1. 改变结点的颜色
2. 左旋转，可以将一个右倾斜的红色链接旋转为左链接
3. 右旋，可以将一个左倾斜的红色链接旋转为右链接
具体细节，参考《算法 第四版》第三章 平衡二叉树，红黑树部分

private void fixAfterInsertion(Entry<K,V> x) {
      x.color = RED;

while (x != null && x != root && x.parent.color == RED) {
if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
              Entry<K,V> y = rightOf(parentOf(parentOf(x)));
if (colorOf(y) == RED) {
setColor(parentOf(x), BLACK);
setColor(y, BLACK);
setColor(parentOf(parentOf(x)), RED);
                  x = parentOf(parentOf(x));
              } else {
if (x == rightOf(parentOf(x))) {
                      x = parentOf(x);
                      rotateLeft(x);
                  }
setColor(parentOf(x), BLACK);
setColor(parentOf(parentOf(x)), RED);
                  rotateRight(parentOf(parentOf(x)));
              }
          } else {
              Entry<K,V> y = leftOf(parentOf(parentOf(x)));
if (colorOf(y) == RED) {
setColor(parentOf(x), BLACK);
setColor(y, BLACK);
setColor(parentOf(parentOf(x)), RED);
                  x = parentOf(parentOf(x));
              } else {
if (x == leftOf(parentOf(x))) {
                      x = parentOf(x);
                      rotateRight(x);
                  }
setColor(parentOf(x), BLACK);
setColor(parentOf(parentOf(x)), RED);
                  rotateLeft(parentOf(parentOf(x)));
              }
          }
      }
      root.color = BLACK;
  }

remove方法

get方法

查找方法相对简单，类似于二分查找，不断缩小查找空间，到达叶子结点没有找到表明TreeMap不包括该键，否则返回该结点。

 public V get(Object key) {
     Entry<K,V> p = getEntry(key);
return (p==null ? null : p.value);
 }

具体查找由以下两个方法完成

/**
 * Returns this map's entry for the given key, or {@code null} if the map
 * does not contain an entry for the key.
 */
final Entry<K,V> getEntry(Object key) {
// Offload comparator-based version for sake of performance
if (comparator != null)
return getEntryUsingComparator(key);
if (key == null)
throw new NullPointerException();
@SuppressWarnings("unchecked")
         Comparable<? super K> k = (Comparable<? super K>) key;

// 自然排序比较方式查找
     Entry<K,V> p = root;
while (p != null) {
int cmp = k.compareTo(p.key);
if (cmp < 0)
             p = p.left;
else if (cmp > 0)
             p = p.right;
else
return p;
     }
return null;
 }




/**
 * Version of getEntry using comparator. Split off from getEntry
 * for performance. (This is not worth doing for most methods,
 * that are less dependent on comparator performance, but is
 * worthwhile here.)
 */
final Entry<K,V> getEntryUsingComparator(Object key) {
@SuppressWarnings("unchecked")
         K k = (K) key;
// 比较器比较方式查找 
     Comparator<? super K> cpr = comparator;
if (cpr != null) {
         Entry<K,V> p = root;
while (p != null) {
int cmp = cpr.compare(k, p.key);
if (cmp < 0)
                 p = p.left;
else if (cmp > 0)
                 p = p.right;
else
return p;
         }
     }
return null;
 }

有序操作的方法

使用二叉树的中序遍历，因为二叉搜索树的中序遍历序列是有序的。

TreeMap和HashMap的比较

不同点有以下：

  1. TreeMap的数据结构是二叉树（红黑树）；
    HashMap的数据结构是数组+链表（或者红黑树）

  2. TreeMap支持有序类的操作；
    HashMap不支持有序类的操作
    （TreeMap中序遍历的序列是有序的）

  3. TreeMap访问数据的时间复杂度是 O(lgN)
    HashMap访问数据的时间复杂度是 O(1)

  4. TreeMap 不允许插入 null 键，因为null无法和其他的key比较
    HashMap可以插入null键（Hashtable不支持插入null键）

  5. TreeMap是根据key进行排序的，它的排序和定位需要依赖比较器或覆写Comparable接口，也因此不需要key覆写hashCode方法和equals方法，就可以排除掉重复的key，
    HashMap的key则需要通过覆写hashCode方法和equals方法来确保没有重复的key，要求key必须实现Comparable接口，或者初始化传入Comparator版本比较器；

相同点有如下：

  1. 两者都存储键值对
  2. 两者都不是线程安全的

使用建议：

  • HashMap的操作的效率更高，一般情况下，使用HashMap存储键值对
  • TreeMap的额外操作是有时间代价的，只有需要有序列的操作时，才考虑使用TreeMap。
标签：

相关文章