TreeMap详解

一、概念及概述

TreeMap 是一个有序的key-value集合，非同步，基于红黑树（Red-Black tree）实现，每个key-value作为红黑树的一个节点。

TreeMap存储时会进行排序的，会根据key来对key-value键值对进行排序，其中排序方式也是分为两种，一种是默认排序（按key的升序），一种是定制排序，具体取决于使用的构造方法。

二、插入

插入操作比较复杂一些，当往 TreeMap 中放入新的键值对后，可能会破坏红黑树的性质，在此只做简单说明

源码分析

public V put(K key, V value) { Entry 
  
    t = root; // 1.如果根节点为 null，将新节点设为根节点 if (t == null) { compare(key, key); root = new Entry<>(key, value, null); size = 1; modCount++; return null; } int cmp; Entry 
   
     parent; // split comparator and comparable paths Comparator 
     cpr = comparator; if (cpr != null) { // 2.为 key 在红黑树找到合适的位置 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 { // 与上面代码逻辑类似，省略 } Entry 
    
      e = new Entry<>(key, value, parent); // 3.将新节点链入红黑树中 if (cmp < 0) parent.left = e; else parent.right = e; // 4.插入新节点可能会破坏红黑树性质，这里修正一下 fixAfterInsertion(e); size++; modCount++; return null; } 
     
    
  

三、查找

TreeMap基于红黑树实现，而红黑树是一种自平衡二叉查找树，所以 TreeMap 的查找操作流程和二叉查找树一致。二叉树的查找流程是这样的，先将目标值和根节点的值进行比较，如果目标值小于根节点的值，则再和根节点的左孩子进行比较。如果目标值大于根节点的值，则继续和根节点的右孩子比较。在查找过程中，如果目标值和二叉树中的某个节点值相等，则返回 true，否则返回 false。TreeMap 查找和此类似，只不过在 TreeMap 中，节点（Entry）存储的是键值对

。在查找过程中，比较的是键的大小，返回的是值，如果没找到，则返回null。TreeMap 中的查找方法是get，具体实现在getEntry方法中。

相关源码如下：

public V get(Object key) { Entry 
  
    p = getEntry(key); return (p==null ? null : p.value); } final Entry 
   
     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 
     k = (Comparable 
    ) key; Entry 
    
      p = root; // 查找操作的核心逻辑就在这个 while 循环里 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; } 
     
    
  

四、删除

删除操作是红黑树最复杂的部分，原因是该操作可能会破坏红黑树性质5（从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点），修复性质5要比修复其他性质（性质2和4需修复，性质1和3不用修复）复杂的多。

红黑树的五个特性：

删除的相关源码如下：

public V remove(Object key) { Entry 
  
    p = getEntry(key); if (p == null) return null; V oldValue = p.value; deleteEntry(p); return oldValue; } private void deleteEntry(Entry 
   
     p) { modCount++; size--; /* * 1. 如果 p 有两个孩子节点，则找到后继节点， * 并把后继节点的值复制到节点 P 中，并让 p 指向其后继节点 */ if (p.left != null && p.right != null) { Entry 
    
      s = successor(p); p.key = s.key; p.value = s.value; p = s; } // p has 2 children // Start fixup at replacement node, if it exists. Entry 
     
       replacement = (p.left != null ? p.left : p.right); if (replacement != null) { /* * 2. 将 replacement parent 引用指向新的父节点， * 同时让新的父节点指向 replacement。 */ replacement.parent = p.parent; if (p.parent == null) root = replacement; else if (p == p.parent.left) p.parent.left = replacement; else p.parent.right = replacement; // Null out links so they are OK to use by fixAfterDeletion. p.left = p.right = p.parent = null; // 3. 如果删除的节点 p 是黑色节点，则需要进行调整 if (p.color == BLACK) fixAfterDeletion(replacement); } else if (p.parent == null) { // 删除的是根节点，且树中当前只有一个节点 root = null; } else { // 删除的节点没有孩子节点 // p 是黑色，则需要进行调整 if (p.color == BLACK) fixAfterDeletion(p); // 将 P 从树中移除 if (p.parent != null) { if (p == p.parent.left) p.parent.left = null; else if (p == p.parent.right) p.parent.right = null; p.parent = null; } } } 
      
     
    
  

上面对 fixAfterDeletion 部分代码逻辑就行了分析，通过配图的形式解析了每段代码逻辑所处理的情况。

五、遍历

 遍历操作也是大家使用频率较高的一个操作，对于TreeMap，使用方式一般如下：

for(Object key : map.keySet()) { // do something }

或者

for(Map.Entry entry : map.entrySet()) { // do something }

Set keys = map.keySet(); Iterator ite = keys.iterator(); while (ite.hasNext()) { Object key = ite.next(); // do something }