TreeMap

TreeMap

底层是红黑树，实现NavigableMap这个接口（NavigableMap接口继承着SortedMap接口），可以根据key自然排序，也可以在构造方法上传递Comparator实现Map的排序

有序的map一般是使用comparaTo或者compare方法来比较key，只要这两个方法认为相等，在map的角度就认为这两个元素相等

非同步

域

//Comparator维护了一个变量，如果该变量为null，则使用自然顺序排序
   private final Comparator<? super K> comparator;

//红黑树的根节点
   private transient Entry<K,V> root;

//红黑树的大小
   private transient int size = 0;

//结构性修改的次数
   private transient int modCount = 0;

构造方法

//comparator维护的变量设置为null
   public TreeMap() {
       comparator = null;
   }

//comparator维护的变量设置为作为参数传递进来的
   public TreeMap(Comparator<? super K> comparator) {
       this.comparator = comparator;
   }

//使用putAll()将Map转为TreeMap
   public TreeMap(Map<? extends K, ? extends V> m) {
       comparator = null;
       putAll(m);
   }

//如果是SortMap，那就是用buildFromSorted()来转TreeMap
  public TreeMap(SortedMap<K, ? extends V> m) {
       comparator = m.comparator();
       try {
           buildFromSorted(m.size(), m.entrySet().iterator(), null, null);
       } catch (java.io.IOException | ClassNotFoundException cannotHappen) {
       }
   }

//TreeMap有序是通过Comparator来进行比较的，如果comparator为null，那么就是用自然顺序

put

  public V put(K key, V value) {
      Entry<K,V> t = root;
//如果根节点为空，新建红黑树
      if (t == null) {
    //判断key是否为空
          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) {
    //comparator比较，找到合适的位置插入到红黑树中
          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);
      }
//如果comparator为null，则使用key作为比较器进行比较，并且key必须实现Comparable接口
      else {
    //如果key为null抛出异常
          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;
//调整红黑树，使红黑树平衡
      fixAfterInsertion(e);
      size++;
      modCount++;
      return null;
  }

  final int compare(Object k1, Object k2) {
      return comparator==null ? ((Comparable<? super K>)k1).compareTo((K)k2)
          : comparator.compare((K)k1, (K)k2);
  }

get

//返回找到的value，找不到返回null
   public V get(Object key) {
       Entry<K,V> p = getEntry(key);
       return (p==null ? null : p.value);
   }

   final Entry<K,V> getEntry(Object key) {
       // Offload comparator-based version for sake of performance
       if (comparator != null)
    //如果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;
    //不然就是使用compareTo()方法
    //从红黑树中找到对应的值，返回出去
       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;
   }

   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) {
        //调用的是Comparator自己实现的方法来获取对应的位置，总体逻辑和外面没啥区别
               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;
   }

remove

  public V remove(Object key) {
      Entry<K,V> p = getEntry(key);
      if (p == null)
          return null;

      V oldValue = p.value;
//删除节点并且平衡红黑树
      deleteEntry(p);
      return oldValue;
  }

遍历方法

TreeMap遍历是使用EntryIteraotr这个内部类的

class EntrySet extends AbstractSet<Map.Entry<K,V>> {
    public Iterator<Map.Entry<K,V>> iterator() ｛
        return new EntryIterator(getFirstEntry());
    }

final class EntryIterator extends PrivateEntryIterator<Map.Entry<K,V>> ｛
    EntryIterator(Entry<K,V> first) {
        super(first);
    }
    public Map.Entry<K,V> next() {
        return nextEntry();
    }
}

final class EntryIterator extends PrivateEntryIterator<Map.Entry<K,V>> ｛
    EntryIterator(Entry<K,V> first) {
        super(first);
    }
    public Map.Entry<K,V> next() {
        return nextEntry();
}

static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) {
    if (t == null)
        return null;
    else if (t.right != null) {
        Entry<K,V> p = t.right;
        while (p.left != null)
            p = p.left;
        return p;
    } else {
        Entry<K,V> p = t.parent;
        Entry<K,V> ch = t;
        while (p != null && ch == p.right) {
            ch = p;
            p = p.parent;
        }
        return p;
    }
}

总结

如果在构造方法中传递了Comparator对象，那么就会以Comparator对象的方法进行比较。否则，则使用Comparator的compareTo(T o)方法来比较

• 如果用的是compareTo(T o)方法来比较，key一定不能为null，并且得实现了Comparable接口的。
• 即使是传入了Comparator对象，不用compareTo(T o)方法来比较，key也是不能为null的