Java 中的 TreeSet

TreeSet 是一种可有序存放元素的集合，HashSet 是 value 为固定值的 HashMap，TreeSet 是 value 为固定值得 TreeMap。

TreeMap

       ┌───┐
       │Map│
       └───┘
         ▲
    ┌────┴─────┐
    │          │
┌───────┐ ┌─────────┐
│HashMap│ │SortedMap│
└───────┘ └─────────┘
               ▲
               │
          ┌─────────┐
          │ TreeMap │
          └─────────┘

HashMap 利用了 hashCode，TreeMap 则利用了树，一个二叉树。

比较 Key

TreeMap 的有序通过比较 key 来实现，无法利用 hashCode 来比较，它需要有一个比较 key 的规则。可通过 Key 继承 Comparable 接口或设置 Comparator 来提供。

Integer

public final class Integer extends Number implements Comparable<Integer> {
    ...
    public int compareTo(Integer anotherInteger) {
        return compare(this.value, anotherInteger.value);
    }
    // 根据元素大小比较，-1 小于 anotherInteger，0 等于，1 大于
    public static int compare(int x, int y) {
        return (x < y) ? -1 : ((x == y) ? 0 : 1);
    }
    ...
}

String

public final class String
    implements java.io.Serializable, Comparable<String>, CharSequence {
    ...
    public int compareTo(String anotherString) {
        byte v1[] = value;
        byte v2[] = anotherString.value;
        if (coder() == anotherString.coder()) {
            return isLatin1() ? StringLatin1.compareTo(v1, v2)
                              : StringUTF16.compareTo(v1, v2);
        }
        return isLatin1() ? StringLatin1.compareToUTF16(v1, v2)
                          : StringUTF16.compareToLatin1(v1, v2);
     }
    ...
}

final class StringLatin1 {
    ...
    public static int compareTo(byte[] value, byte[] other, int len1, int len2) {
        // 只比较短的部分
        int lim = Math.min(len1, len2);
        for (int k = 0; k < lim; k++) {
            // 返回不同的字符的 assic 差值
            if (value[k] != other[k]) {
                return getChar(value, k) - getChar(other, k);
            }
        }
        // 当短部分都相同时，比较长度
        return len1 - len2;
    }
    ...
    public static char getChar(byte[] val, int index) {
        return (char)(val[index] & 0xff);
    }
    ...
}

自定义类

使用 Comparator

// A class to represent a student. 
class Student { 
    int rollno; 
    String name, address; 
  
    // Constructor 
    public Student(int rollno, String name, 
                   String address) 
    { 
        this.rollno = rollno; 
        this.name = name; 
        this.address = address; 
    } 
  
    // Used to print student details 
    // in main() 
    public String toString() 
    { 
        return this.rollno + " "
            + this.name + " "
            + this.address; 
    } 
} 
  
// Comparator implementattion 
class Sortbyroll 
    implements Comparator<Student> { 
  
    // Used for sorting in ascending order of 
    // roll number 
    public int compare(Student a, Student b) 
    { 
        return a.rollno - b.rollno; 
    } 
} 
  
public class TreeMapImplementation { 
  
    static void Example2ndConstructor() 
    { 
        // Creating an empty TreeMap 
        TreeMap<Student, Integer> tree_map 
            = new TreeMap<Student, Integer>(new Sortbyroll()); 
  
        // Mapping string values to int keys 
        tree_map.put(new Student(111, "bbbb", 
                                 "london"), 
                     2); 
        tree_map.put(new Student(131, "aaaa", 
                                 "nyc"), 
                     3); 
        tree_map.put(new Student(121, "cccc", 
                                 "jaipur"), 
                     1); 
  
        // Displaying the TreeMap 
        System.out.println("TreeMap: "
                           + tree_map); 
    } 
  
    public static void main(String[] args) 
    { 
  
        System.out.println("TreeMap using "
                           + "TreeMap(Comparator)"
                           + " constructor:\n"); 
        Example2ndConstructor(); 
    } 
}

输出

TreeMap using TreeMap(Comparator) constructor:

TreeMap: {121 cccc jaipur=1, 131 aaaa nyc=3, 141 bbbb london=2}

使用 Comparable

class Student implements Comparable<Student>{
    int rollno;
    String name, address;

    // Constructor
    public Student(int rollno, String name,
                   String address)
    {
        this.rollno = rollno;
        this.name = name;
        this.address = address;
    }

    public int compareTo(Student anotherStudent)
    {
        return this.rollno - anotherStudent.rollno;
    }

    // Used to print student details
    // in main()
    public String toString()
    {
        return this.rollno + " "
                + this.name + " "
                + this.address;
    }
}

如何排序

添加时，跟 root 节点比较，小于放到左边，大于放到右边。

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，cpr 将不为 null
    Comparator<? super K> cpr = comparator;
    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);
        } while (t != null);
    }
    else {
        if (key == null)
            throw new NullPointerException();
        @SuppressWarnings("unchecked") // 获取 key 的 Comparable
            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;
}

时间复杂度

针对二叉树，4 层的总节点：2^0^ + 2^1^ + 2^2^ + 2^3^ -> 2^4^，如果树节点数为 n，树的高度为 log(n)。

所以 TreeMap 的查找和新增时间复杂度为 O(log(n))。

vs LinkedHashMap

LinkedHashMap 使用一个额外双向链表，记录插入顺序，所以它是根据插入顺序排序。