一、前言
前面所说的hashMap和linkedHashMap都不具备统计的功能，或者说它们的统计性能的时间复杂度都不是很好，要想对两者进行统计，需要遍历所有的entry，时间复杂度比较高，此时，我们就需要使用treeMap。
treeMap的key按照自然顺序进行排序或根据创建时提供的comparator接口进行排序，TreeMap为增、删、改、查这些操作提供了log(N)的时间开销，从存储角度而言，这比HashMap与LinkedHashMap的O(1)时间复杂度要差些；但是在统计性能上，TreeMap同样可以保证log(N)的时间开销，这又比HashMap与LinkedHashMap的O(N)时间复杂度好不少。
因此，如果只需要存储功能，使用hashMap或linkedHashMap是一种更好的选择；如果还需要保证统计功能或是对key按照一定的规则进行排序，那么使用treeMap是一种更好的选择。
四个关注点在treeMap上的答案
二、treeMap的数据结构
treeMap底层使用的数据结构是红黑树，下图为典型的红黑树结构，效率很高。
用来存储key-value的是treeMap中的Entry类，除了key-value属性，还有该节点的左节点left，右节点right，父节点parent。
三、treeMap源码分析-属性及构造函数
3.1 类的继承关系
public class TreeMap<K,V>
extends AbstractMap<K,V>
implements NavigableMap<K,V>, Cloneable, java.io.Serializable
说明：继承了抽象类AbstractMap，AbstractMap实现了Map接口，实现了部分方法。实现了NavigableMap,Cloneable,Serializable接口，其中NavigableMap是继承自SortedMap的接口，定义了一系列规范。
3.2 类的属性
/**
* The comparator used to maintain order in this tree map, or
* null if it uses the natural ordering of its keys.
* 比较器，用于维持treeMap中key的顺序，为null时，使用的是key的自然顺序
* @serial
*/
private final Comparator<? super K> comparator;
//树的根节点
private transient Entry<K,V> root; /**
* The number of entries in the tree 树中节点的数量
*/
private transient int size = 0; /**
* The number of structural modifications to the tree. 对树进行结构性修改的次数
*/
private transient int modCount = 0;
3.3 类的构造函数
1、TreeMap()型
/**
* Constructs a new, empty tree map, using the natural ordering of its
* keys. All keys inserted into the map must implement the {@link
* Comparable} interface. Furthermore, all such keys must be
* <em>mutually comparable</em>: {@code k1.compareTo(k2)} must not throw
* a {@code ClassCastException} for any keys {@code k1} and
* {@code k2} in the map. If the user attempts to put a key into the
* map that violates this constraint (for example, the user attempts to
* put a string key into a map whose keys are integers), the
* {@code put(Object key, Object value)} call will throw a
* {@code ClassCastException}.
*/
public TreeMap() {
comparator = null;
}
说明：定义一个新的，空的treeMap，排序规则是key的自然顺序，所有要存储的元素的key必须实现Comparable接口，而且，这些key要可以互相比较，否则会抛ClassCastException，即类型转换异常。
举例：正常情况下，key实现了Comparable接口
public class Test {
public static void main(String[] args) {
TreeMap<String, String> treeMap = new TreeMap<>();
treeMap.put("a","aaa");
treeMap.put("d","ddd");
treeMap.put("b","bbb");
treeMap.put("c","ccc");
Set<Map.Entry<String, String>> entries = treeMap.entrySet();
for(Map.Entry<String, String> entry : entries) {
System.out.println(entry.getKey() + "========" + entry.getValue());
}
}
}结果：
a========aaa
b========bbb
c========ccc
d========ddd
说明：可以看到，treeMap中已经根据key的自然顺序进行排序了，key所属类型String类实现了Comparable接口
public final class String
implements java.io.Serializable, Comparable<String>, CharSequence
key所属String类下的比较规则：
/**
* Compares two strings lexicographically.
* The comparison is based on the Unicode value of each character in
* the strings. The character sequence represented by this
* {@code String} object is compared lexicographically to the
* character sequence represented by the argument string. The result is
* a negative integer if this {@code String} object
* lexicographically precedes the argument string. The result is a
* positive integer if this {@code String} object lexicographically
* follows the argument string. The result is zero if the strings
* are equal; {@code compareTo} returns {@code 0} exactly when
* the {@link #equals(Object)} method would return {@code true}.
* <p>
* This is the definition of lexicographic ordering. If two strings are
* different, then either they have different characters at some index
* that is a valid index for both strings, or their lengths are different,
* or both. If they have different characters at one or more index
* positions, let <i>k</i> be the smallest such index; then the string
* whose character at position <i>k</i> has the smaller value, as
* determined by using the < operator, lexicographically precedes the
* other string. In this case, {@code compareTo} returns the
* difference of the two character values at position {@code k} in
* the two string -- that is, the value:
* <blockquote><pre>
* this.charAt(k)-anotherString.charAt(k)
* </pre></blockquote>
* If there is no index position at which they differ, then the shorter
* string lexicographically precedes the longer string. In this case,
* {@code compareTo} returns the difference of the lengths of the
* strings -- that is, the value:
* <blockquote><pre>
* this.length()-anotherString.length()
* </pre></blockquote>
*
* @param anotherString the {@code String} to be compared.
* @return the value {@code 0} if the argument string is equal to
* this string; a value less than {@code 0} if this string
* is lexicographically less than the string argument; and a
* value greater than {@code 0} if this string is
* lexicographically greater than the string argument.
*/
public int compareTo(String anotherString) {
int len1 = value.length;
int len2 = anotherString.value.length;
int lim = Math.min(len1, len2);
char v1[] = value;
char v2[] = anotherString.value; int k = 0;
while (k < lim) {
char c1 = v1[k];
char c2 = v2[k];
if (c1 != c2) {
return c1 - c2;
}
k++;
}
return len1 - len2;
}
第二种情况：定义一个Student类当做treeMap的key，Student类并未实现Comparable接口
public class Student{
private String name;
private String age;
public Student() {
}
public Student(String name, String age) {
this.name = name;
this.age = age;
}
@Override
public String toString() {
return "Student{" +
"name='" + name + '\'' +
", age='" + age + '\'' +
'}';
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public String getAge() {
return age;
}
public void setAge(String age) {
this.age = age;
}
}测试一下：
public class Test {
public static void main(String[] args) {
TreeMap<Student, String> treeMap = new TreeMap<>();
Student student1 = new Student("zs", "10");
Student student2 = new Student("ls", "12");
Student student3 = new Student("ww", "11");
Student student4 = new Student("zl", "15");
treeMap.put(student1,"beijing");
treeMap.put(student2,"shenzhen");
treeMap.put(student3,"hangzhou");
treeMap.put(student4,"guangzhou");
Set<Map.Entry<Student, String>> entries = treeMap.entrySet();
for(Map.Entry<Student, String> entry : entries) {
System.out.println(entry.getKey() + "==========" + entry.getValue());
}
}
}结果：
Exception in thread "main" java.lang.ClassCastException: com.dajia.test.Student cannot be cast to java.lang.Comparable
at java.util.TreeMap.compare(TreeMap.java:1294)
at java.util.TreeMap.put(TreeMap.java:538)
at com.dajia.test.Test.main(Test.java:23)
说明：可以看到，当key未实现Comparable接口时，在put元素的时候就会报错。
当Student类实现Comparable接口时：比较规则是按照age的大小进行比较
public class Student implements Comparable<Student>{
private String name;
private String age;
public Student() {
}
public Student(String name, String age) {
this.name = name;
this.age = age;
}
@Override
public String toString() {
return "Student{" +
"name='" + name + '\'' +
", age='" + age + '\'' +
'}';
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public String getAge() {
return age;
}
public void setAge(String age) {
this.age = age;
}
@Override
public int compareTo(Student o) {
return this.age.compareTo(o.age);
}
}相同的测试代码测试一下，结果：按照key（student）的排序规则进行了排序
Student{name='zs', age='10'}==========beijing
Student{name='ww', age='11'}==========hangzhou
Student{name='ls', age='12'}==========shenzhen
Student{name='zl', age='15'}==========guangzhou2、TreeMap(Comparator<? super K> comparator)型
/**
* Constructs a new, empty tree map, ordered according to the given
* comparator. All keys inserted into the map must be <em>mutually
* comparable</em> by the given comparator: {@code comparator.compare(k1,
* k2)} must not throw a {@code ClassCastException} for any keys
* {@code k1} and {@code k2} in the map. If the user attempts to put
* a key into the map that violates this constraint, the {@code put(Object
* key, Object value)} call will throw a
* {@code ClassCastException}.
*
* @param comparator the comparator that will be used to order this map.
* If {@code null}, the {@linkplain Comparable natural
* ordering} of the keys will be used.
*/
public TreeMap(Comparator<? super K> comparator) {
this.comparator = comparator;
}
说明：定义一个新的，空的treeMap，参数是自定义的比较器，排序规则是该比较器的比较规则，这些key要可以互相比较，否则会抛ClassCastException，即类型转换异常。
举例：自定义一个比较器StudentComparator，比较student下的age大小
public class StudentComparator implements Comparator<Student>{
@Override
public int compare(Student o1, Student o2) {
return o1.getAge().compareTo(o2.getAge());
}
}测试一下：
public class Test {
public static void main(String[] args) {
StudentComparator studentComparator = new StudentComparator();
TreeMap<Student, String> treeMap = new TreeMap<>(studentComparator);
Student student1 = new Student("zs", "10");
Student student2 = new Student("ls", "12");
Student student3 = new Student("ww", "11");
Student student4 = new Student("zl", "15");
treeMap.put(student1,"beijing");
treeMap.put(student2,"shenzhen");
treeMap.put(student3,"hangzhou");
treeMap.put(student4,"guangzhou");
Set<Map.Entry<Student, String>> entries = treeMap.entrySet();
for(Map.Entry<Student, String> entry : entries) {
System.out.println(entry.getKey() + "==========" + entry.getValue());
}
}
}结果：
Student{name='zs', age='10'}==========beijing
Student{name='ww', age='11'}==========hangzhou
Student{name='ls', age='12'}==========shenzhen
Student{name='zl', age='15'}==========guangzhou3、TreeMap(Map<? extends K, ? extends V> m)型
/**
* Constructs a new tree map containing the same mappings as the given
* map, ordered according to the <em>natural ordering</em> of its keys.
* All keys inserted into the new map must implement the {@link
* Comparable} interface. Furthermore, all such keys must be
* <em>mutually comparable</em>: {@code k1.compareTo(k2)} must not throw
* a {@code ClassCastException} for any keys {@code k1} and
* {@code k2} in the map. This method runs in n*log(n) time.
*
* @param m the map whose mappings are to be placed in this map
* @throws ClassCastException if the keys in m are not {@link Comparable},
* or are not mutually comparable
* @throws NullPointerException if the specified map is null
*/
public TreeMap(Map<? extends K, ? extends V> m) {
comparator = null;
putAll(m);
}
说明：定义一个新的treeMap，根据key的自然排序将参数中m的元素存储到treeMap中。
4、TreeMap(SortedMap<K, ? extends V> m)型
/**
* Constructs a new tree map containing the same mappings and
* using the same ordering as the specified sorted map. This
* method runs in linear time.
*
* @param m the sorted map whose mappings are to be placed in this map,
* and whose comparator is to be used to sort this map
* @throws NullPointerException if the specified map is null
*/
public TreeMap(SortedMap<K, ? extends V> m) {
comparator = m.comparator();
try {
buildFromSorted(m.size(), m.entrySet().iterator(), null, null);
} catch (java.io.IOException cannotHappen) {
} catch (ClassNotFoundException cannotHappen) {
}
}
说明：定义一个新的treeMap，根据sortedMap中比较器的排序规则将参数中m的元素存储到treeMap中。
四、treeMap源码分析-核心函数
4.1 增：put函数----存储元素
/**
* Associates the specified value with the specified key in this map.
* If the map previously contained a mapping for the key, the old
* value is replaced.
*
* @param key key with which the specified value is to be associated
* @param value value to be associated with the specified key
*
* @return the previous value associated with {@code key}, or
* {@code null} if there was no mapping for {@code key}.
* (A {@code null} return can also indicate that the map
* previously associated {@code null} with {@code key}.)
* @throws ClassCastException if the specified key cannot be compared
* with the keys currently in the map
* @throws NullPointerException if the specified key is null
* and this map uses natural ordering, or its comparator
* does not permit null keys
*/
public V put(K key, V value) {
//将根节点赋值给t
Entry<K,V> t = root;
if (t == null) {
//根节点为null，添加的是第一个元素，先check key的type
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;//定义put进来的元素的父节点
// split comparator and comparable paths
Comparator<? super K> cpr = comparator;
if (cpr != null) {
do {
parent = t;//获取要存储元素的parent节点
//从root开始，比较两者key的大小
cmp = cpr.compare(key, t.key);
if (cmp < 0)
//小于已存在节点的key，将t.left赋值给t，以便再次进行比较
t = t.left;
else if (cmp > 0)
//大于已存在节点的key，将t.right赋值给t,以便再次进行比较
t = t.right;
else
//为0，表示两者相等，用value替换原value值，并返回原value
return t.setValue(value);
} while (t != null);//t != null，接着进行比较
}
else {
//The comparator used to maintain order in this tree map, or null if it uses the natural ordering of its keys.
if (key == null)
throw new NullPointerException();
@SuppressWarnings("unchecked")//获取key的compareTo方法
Comparable<? super K> k = (Comparable<? super K>) key;
do {
parent = t;//获取要存储元素的parent节点
//从root开始，比较两者key的大小
cmp = k.compareTo(t.key);
if (cmp < 0)
//小于已存在节点的key，将t.left赋值给t，以便再次进行比较
t = t.left;
else if (cmp > 0)
//大于已存在节点的key，将t.right赋值给t,以便再次进行比较
t = t.right;
else
//为0，表示两者相等，用value替换原value值，并返回原value
return t.setValue(value);
} while (t != null);//t != null，接着进行比较
}
//构建要存储的新元素
Entry<K,V> e = new Entry<>(key, value, parent);
if (cmp < 0)//小于0，位于parent的左边
parent.left = e;
else//大于0，位于parent元素的右边
parent.right = e;
//插入后进行修正
fixAfterInsertion(e);
size++;
modCount++;
return null;
}
说明：插入一个元素时，若用户自定义一个比较器，则会按照用户自定义比较器中的排序规则确定元素的插入位置，否则，将会使用key自身实现的比较器确定插入位置。该方法主要是通过key的比较寻找插入节点的parent节点，并将parent节点与插入节点联系起来。
4.2 删：remove和removeNode函数----删除元素
/**
* Removes the mapping for this key from this TreeMap if present.
*
* @param key key for which mapping should be removed
* @return the previous value associated with {@code key}, or
* {@code null} if there was no mapping for {@code key}.
* (A {@code null} return can also indicate that the map
* previously associated {@code null} with {@code key}.)
* @throws ClassCastException if the specified key cannot be compared
* with the keys currently in the map
* @throws NullPointerException if the specified key is null
* and this map uses natural ordering, or its comparator
* does not permit null keys
*/
public V remove(Object key) {
Entry<K,V> p = getEntry(key);
if (p == null)
return null; V oldValue = p.value;
deleteEntry(p);
return oldValue;
}
通过getEntry获取要删除的节点
/**
* Returns this map's entry for the given key, or {@code null} if the map
* does not contain an entry for the key.
*
* @return this map's entry for the given key, or {@code null} if the map
* does not contain an entry for the key
* @throws ClassCastException if the specified key cannot be compared
* with the keys currently in the map
* @throws NullPointerException if the specified key is null
* and this map uses natural ordering, or its comparator
* does not permit null keys
*/
final Entry<K,V> getEntry(Object key) {
// Offload comparator-based version for sake of performance
if (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;
//比较器为null，通过key的循环比较获取节点
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;
}
再通过deleteEntry将该节点进行删除，这个方法没看懂，先放着 o(╥﹏╥)o
/**
* Delete node p, and then rebalance the tree.
*/
private void deleteEntry(Entry<K,V> p) {
modCount++;
size--; // If strictly internal, copy successor's element to p and then make p
// point to successor.
if (p.left != null && p.right != null) {
Entry<K,V> s = successor(p);
p.key = s.key;
p.value = s.value;
p = s;
} // p has 2 children // Start fixup at replacement node, if it exists.
Entry<K,V> replacement = (p.left != null ? p.left : p.right); if (replacement != null) {
// Link replacement to parent
replacement.parent = p.parent;
if (p.parent == null)
root = replacement;
else if (p == p.parent.left)
p.parent.left = replacement;
else
p.parent.right = replacement; // Null out links so they are OK to use by fixAfterDeletion.
p.left = p.right = p.parent = null; // Fix replacement
if (p.color == BLACK)
fixAfterDeletion(replacement);
} else if (p.parent == null) { // return if we are the only node.
root = null;
} else { // No children. Use self as phantom replacement and unlink.
if (p.color == BLACK)
fixAfterDeletion(p); if (p.parent != null) {
if (p == p.parent.left)
p.parent.left = null;
else if (p == p.parent.right)
p.parent.right = null;
p.parent = null;
}
}
}
4.3 改：put函数----修改元素
参见4.1中的put函数，可以将相同key的value覆盖。
4.4 查：get和getEntry方法----查找元素
/**
* Returns the value to which the specified key is mapped,
* or {@code null} if this map contains no mapping for the key.
*
* <p>More formally, if this map contains a mapping from a key
* {@code k} to a value {@code v} such that {@code key} compares
* equal to {@code k} according to the map's ordering, then this
* method returns {@code v}; otherwise it returns {@code null}.
* (There can be at most one such mapping.)
*
* <p>A return value of {@code null} does not <em>necessarily</em>
* indicate that the map contains no mapping for the key; it's also
* possible that the map explicitly maps the key to {@code null}.
* The {@link #containsKey containsKey} operation may be used to
* distinguish these two cases.
*
* @throws ClassCastException if the specified key cannot be compared
* with the keys currently in the map
* @throws NullPointerException if the specified key is null
* and this map uses natural ordering, or its comparator
* does not permit null keys
*/
public V get(Object key) {
Entry<K,V> p = getEntry(key);
return (p==null ? null : p.value);
}
getEntry方法参见4.2中的getEntry。
五、总结
由TreeMap我们可以知道其底层的数据结构为红黑树，并且可以使用用户自定义的比较器来实现比较逻辑。红黑树还是难了点，插入之后的旋转看着还是头晕，以后有时间在好好研究。
参考资料：
https://www.cnblogs.com/leesf456/p/5255370.html
https://www.cnblogs.com/xrq730/p/6867924.html