TreeMap定义
- 1 以jdk7为准进行说明
package java.util;
public class TreeMap<K,V>
extends AbstractMap<K,V>
implements NavigableMap<K,V>, Cloneable, java.io.Serializable{
}
public interface NavigableMap<K,V> extends SortedMap<K,V>{}
TreeMap继承AbstractMap，实现NavigableMap、Cloneable、Serializable三个接口。其中AbstractMap表明TreeMap为一个Map即支持key-value的集合， NavigableMap则意味着它支持一系列的导航方法，具备针对给定搜索目标返回最接近匹配项的导航方法。
- 2 成员属性
private final Comparator<? super K> comparator; //比较器
private transient Entry<K,V> root = null; //TreeMap红-黑节点，为TreeMap的内部类
private transient int size = 0; //容器大小
private transient int modCount = 0; //TreeMap修改次数
private static final boolean RED = false; //红黑树的节点颜色–红色
private static final boolean BLACK = true; //红黑树的节点颜色–黑色
对于实体节点Entry是TreeMap的内部类，是通过红黑树实现的。
红黑树顾名思义就是节点是红色或者黑色的平衡二叉树，它通过颜色的约束来维持着二叉树的平衡。对于一棵有效的红黑树二叉树而言我们必须增加如下规则：
1）每个节点都只能是红色或者黑色
2）根节点是黑色
3）每个叶节点（NIL节点，空节点）是黑色的。
4）如果一个结点是红的，则它两个子节点都是黑的。也就是说在一条路径上不能出现相邻的两个红色结点。
5）从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
- 3 这些约束强制了红黑树的关键性质: 从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。
- 4 结果是这棵树大致上是平衡的。因为操作比如插入、删除和查找某个值的最坏情况时间都要求与树的高度成比例，这个在高度上的理论上限允许红黑树在最坏情况下都是高效的，而不同于普通的二叉查找树。所以红黑树它是复杂而高效的，其检索效率O(log n)。
TreeMap特点
- 1 TreeMap是非线程安全的。
可以采用这种方式将TreeMap设置为同步的：
Map m = Collections.synchronizedSortedMap(new TreeMap(…));
- 2 TreeMap是用键来进行升序顺序来排序的。通过Comparable 或 Comparator来排序。
public class Person1 implements Comparable<Person1>
{
private int age;
private String name;
public Person1(String name, int age)
{
this.name = name;
this.age = age;
}
@Override
public int compareTo(Person1 o)
{
return this.age-o.age;
}
@Override
public String toString()
{
return name+":"+age;
}
}
测试代码
Map<Person1,Integer> map = new TreeMap<>();
Person1 person1 = new Person1("zzh",18);
Person1 person2 = new Person1("jj",17);
Person1 person3 = new Person1("qq",19);
map.put(person1, 1);
map.put(person2, 2);
map.put(person3, 3);
for(Entry<Person1, Integer> entry:map.entrySet())
{
System.out.println(entry.getKey()+":"+entry.getValue());
}
运行结果
jj:17:2
zzh:18:1
qq:19:3
- 3 TreeMap是SortedMap接口的基于红黑树的实现。此类保证了映射按照升序顺序排列关键字， 根据使用的构造方法不同，可能会按照键的类的自然顺序进行排序，或者按照创建时所提供的比较器（自定义）进行排序。
public final class Person2
{
private int age;
private String name;
public Person2(String name, int age)
{
this.name = name;
this.age = age;
}
@Override
public String toString()
{
return name+":"+age;
}
//getter and setter方法省略....
}
测试代码
Map<Person2,Integer> map2 = new TreeMap<>(new Comparator<Person2>(){
@Override
public int compare(Person2 o1, Person2 o2)
{
if(o1 == null || o2 == null)
return 0;
return o1.getAge()-o2.getAge();
}
});
Person2 p1 = new Person2("zzh",18);
Person2 p2 = new Person2("jj",17);
Person2 p3 = new Person2("qq",19);
map2.put(p1, 1);
map2.put(p2, 2);
map2.put(p3, 3);
for(Entry<Person2, Integer> entry:map2.entrySet())
{
System.out.println(entry.getKey()+":"+entry.getValue());
}
运行结果：
jj:17:2
zzh:18:1
qq:19:3
- 4 返回的迭代器都是快速失败的
这点和HashMap一样，所谓快速失败就是在并发集合中，其进行迭代操作时，若有其他线程对其结构性的修改，这是迭代器会立马感知到，并且立刻抛出ConcurrentModificationException异常，而不是等待迭代完成之后才告诉你已经出错。 - 5 和HashMap一样，如果插入重复的元素，后面的元素会覆盖前面的。
- 6 键不可以为null（如果比较器对null做了处理，就可以为null）,但是值可以为null。
- 7 TreeMap提供了很多方法方便大小使用，譬如containsKey, get, put,remove，entrySet等Map通用的方法，也包括fisrtEntry, firstKey, cellingKey, lowerKey等方法。
HashMap与TreeMap的区别
- 1 实现方式
HashMap:基于哈希表实现。使用HashMap要求添加的键类明确定义了hashCode（）和equals（）[可以重写hashCode（）和equals（）],为了优化HashMap空间的使用，您可以调优初始容量和负载因子。
1）HashMap（）： 构建一个空的哈希映像
2）HashMap（Map m）： 构建一个哈希映像，并且添加映像m的所有映射
3）HashMap（int initialCapacity）： 构建一个拥有特定容量的空的哈希映像
4）HashMap（int initialCapacity, float loadFactor）： 构建一个拥有特定容量和加载因子的空的哈希映像
TreeMap:基于红黑树实现。TreeMap没有调优选项，因为该树总处于平衡状态。
1）TreeMap（）：构建一个空的映像树
2）TreeMap（Map m）： 构建一个映像树，并且添加映像m中所有元素
3）TreeMap（Comparator c）： 构建一个映像树，并且使用特定的比较器对关键字进行排序
4）TreeMap（SortedMap s）： 构建一个映像树，添加映像树s中所有映射，并且使用与有序映像s相同的比较器排序 - 2 用途
1）HashMap：适用于在Map中插入、删除和定位元素。
2）TreeMap：适用于按自然顺序或自定义顺序遍历键（key)。
3）HashMap通常比TreeMap快一点（树和哈希表的数据结构使然），建议多使用HashMap,在需要排序的Map时候才用TreeMap.
