Java 中的 TreeSet

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

TreeMap

       ┌───┐
│Map│
└───┘

┌────┴─────┐
│ │
┌───────┐ ┌─────────┐
│HashMap│ │SortedMap│
└───────┘ └─────────┘


┌─────────┐
│ TreeMap │
└─────────┘

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

Treemap Internal Working

比较 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 使用一个额外双向链表,记录插入顺序,所以它是根据插入顺序排序。

延伸阅读

Depp Wang wechat
个人公众号