《java集合》--TreeMap、TreeSet

《java集合》–TreeMap、TreeSet

说明：此文章基于jdk1.8

简介

数据结构

基于红黑二叉树存储

基本属性

• private final Comparator

构造器

public TreeMap() {
  comparator = null;
}
//带comparator的构造器
public TreeMap(Comparator<? super K> comparator) {
  this.comparator = comparator;
}
//传入的是map，默认的comparator为空，将map中的所有元素添加到treeMap中
public TreeMap(Map<? extends K, ? extends V> m) {
  comparator = null;
  putAll(m);
}
//传入一个sortedMap
public TreeMap(SortedMap<K, ? extends V> m) {
  //使用参数的comparator对key值进行排序
  comparator = m.comparator();
  try {
    //遍历参数中的所有元素，按照key值得顺序添加
    buildFromSorted(m.size(), m.entrySet().iterator(), null, null);
  } catch (java.io.IOException cannotHappen) {
  } catch (ClassNotFoundException cannotHappen) {
  }
}

存储的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;

  Entry(K key, V value, Entry<K,V> parent) {
    this.key = key;
    this.value = value;
    this.parent = parent;
  }

  public K getKey() {
    return key;
  }

  public V getValue() {
    return value;
  }

  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;
  }
}

添加元素

public V put(K key, V value) {
  Entry<K,V> t = root;
  //空map的时候将元素添加到map中
  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) {
    //循环将key同map中的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 {
    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;
}

删除元素

获取元素

遍历

排序

总结

• TreeMap是根据key进行排序的，它的排序和定位需要依赖比较器或覆写Comparable接口，也因此不需要key覆写hashCode方法和equals方法，就可以排除掉重复的key，而HashMap的key则需要通过覆写hashCode方法和equals方法来确保没有重复的key。

• TreeMap的查询、插入、删除效率均没有HashMap高，一般只有要对key排序时才使用TreeMap。

• TreeMap的key不能为null，而HashMap的key可以为null。

常用方法

TreeMap treeMap = new TreeMap();
treeMap.put("d", 1);
treeMap.put("b", 2);
treeMap.put("h", 3);
treeMap.put("a", 4);
System.out.println(treeMap.firstKey());//a
System.out.println(treeMap.firstEntry());//a=4
System.out.println(treeMap.lastKey());//h
System.out.println(treeMap.lastEntry());//h=3
System.out.println(treeMap.ceilingKey("b"));//b
System.out.println(treeMap.ceilingEntry("b"));//b=2
System.out.println(treeMap.higherKey("b"));//d
System.out.println(treeMap.higherEntry("b"));//d=1
System.out.println(treeMap.floorKey("b"));//b
System.out.println(treeMap.floorEntry("b"));//b=2
System.out.println(treeMap.lowerKey("b"));//a
System.out.println(treeMap.lowerEntry("b"));//a=4
/**
         * true：包含=的
         * false：不含=的
         */
System.out.println(treeMap.headMap("b",true));//小于b的
System.out.println(treeMap.tailMap("b"));//大于等于b的
System.out.println(treeMap.subMap("b",false, "e",true));//截取map
System.out.println(treeMap);
//弹出treeMap中的第一个
Entry pollFirstEntry = treeMap.pollFirstEntry();
Entry pollLastEntry = treeMap.pollLastEntry();
System.out.println(pollFirstEntry);
System.out.println(pollLastEntry);
System.out.println(treeMap);

treeMap.merge("b", 5, (oldValue, value)->{return oldValue;});
System.out.println(treeMap);
treeMap.put("b", 5);
System.out.println(treeMap);