JAVA8 TreeMap学习笔记

桃扇骨 2022-05-10 01:40 176阅读 0赞

### TreeMap ###

TreeMap集合是基于红黑树（Red-Black tree）的 NavigableMap实现。该集合最重要的特点就是可排序，该映射根据其键的自然顺序进行排序，或者根据创建映射时提供的 Comparator 进行排序，具体取决于使用的构造方法。这句话是什么意思呢？就是说TreeMap可以对添加进来的元素进行排序，可以按照默认的排序方式，也可以自己指定排序方式

【知识点】

*  TreeMap基于红黑树实现无容量限制；
 *  TreeMap是非线程安全的；

### 类名及类成员变量 ###

public class TreeMap<K,V>
    extends AbstractMap<K,V>
    implements NavigableMap<K,V>, Cloneable, java.io.Serializable
    {
    // 比较器对象
    private final Comparator<? super K> comparator;
    
    // 根节点
    private transient Entry<K,V> root;
    
    // 集合大小
    private transient int size = 0;
    
    // 树结构被修改的次数
    private transient int modCount = 0;
    
    // 静态内部类用来表示节点类型
    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; //
    }
    }

类构造方法

public TreeMap() { // 1,无参构造方法
    comparator = null; // 默认比较机制
    }
    
    public TreeMap(Comparator<? super K> comparator) { // 2，自定义比较器的构造方法
    this.comparator = comparator;
    }
    
    public TreeMap(Map<? extends K, ? extends V> m) { // 3，构造已知Map对象为TreeMap
    comparator = null; // 默认比较机制
    putAll(m);
    }
    
    public TreeMap(SortedMap<K, ? extends V> m) { // 4，构造已知的SortedMap对象为TreeMap
    comparator = m.comparator(); // 使用已知对象的构造器
    try {
    buildFromSorted(m.size(), m.entrySet().iterator(), null, null);
    } catch (java.io.IOException cannotHappen) {
    } catch (ClassNotFoundException cannotHappen) {
    }
    }

*  **put(K key, V value)**

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; // 集合大小为1
    modCount++; // 结构修改次数自增
    return null;
    }
    
    int cmp;
    Entry<K,V> parent;
    Comparator<? super K> cpr = comparator; // 比较器对象
    
    // 如果比较器对象不为空，也就是自定义了比较器
    if (cpr != null) {
    do { // 循环比较并确定元素应插入的位置(也就是找到该元素的父节点)
    parent = t; // t就是root
    
    // 调用比较器对象的compare()方法，该方法返回一个整数
    cmp = cpr.compare(key, t.key);
    if (cmp < 0) // 待插入元素的key"小于"当前位置元素的key，则查询左子树
    t = t.left;
    else if (cmp > 0) // 待插入元素的key"大于"当前位置元素的key，则查询右子树
    t = t.right;
    else // "相等"则替换其value。
    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) // 待插入元素的key"小于"当前位置元素的key，则查询左子树
    t = t.left;
    else if (cmp > 0) // 待插入元素的key"大于"当前位置元素的key，则查询右子树
    t = t.right;
    else // "相等"则替换其value。
    return t.setValue(value);
    } while (t != null);
    }
    
    Entry<K,V> e = new Entry<>(key, value, parent); // 根据key找到父节点后新建一个节点
    if (cmp < 0) // 根据比较的结果来确定放在左子树还是右子树
    parent.left = e;
    else
    parent.right = e;
    fixAfterInsertion(e);
    size++; // 集合大小+1
    modCount++; // 集合结构被修改次数+1
    return null;
    }

### 自定义比较器 ###

1.  key为String类型，因为String实现了Comparable接口，所以按照String类中的compareTo方法进行排序；
2.  TreeMap的key实现Comparable接口并实现compareTo方法；

public class User implements Comparable<User>{
    private String username;
    private int age;
    
    public User(String username, int age) {
    this.username = username;
    this.age = age;
    }
    
    @Override
    public String toString() {
    return "User [username=" + username + ", age=" + age + "]";
    }
    @Override
    public int compareTo(User user) {
    int temp = this.age - user.age;
    return temp == 0 ? this.username.compareTo(user.username) : temp;
    }
    }

1.  使用TreeMap的构造方法传递比较器

Map<User3, String> map = new TreeMap<>(new TreeMapComparator());

1.  使用匿名内部类的形式来写比较器

Map<User3, String> map = new TreeMap<>(new Comparator<User3>() {
    
    @Override
    public int compare(User3 o1, User3 o2) {
    int temp = o1.getAge() - o2.getAge();
    return temp == 0 ? o1.getUsername().compareTo(o2.getUsername()) : temp;
    }
    });

***参考资料***

[https://www.jianshu.com/p/69f11fc9ea38][https_www.jianshu.com_p_69f11fc9ea38]

[https_www.jianshu.com_p_69f11fc9ea38]: https://www.jianshu.com/p/69f11fc9ea38