Java集合框架4TreeMap

2017-04-11 本文已影响0人 paulpaullong

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.

Java集合框架4TreeMap

TreeMap定义

TreeMap特点

HashMap与TreeMap的区别

猜你喜欢

热点阅读