java2集合框架的一些个人分析和理解(四)

HashMap预先指定空间的方式,增加1000次,耗费时间=1

增加10000次

HashMap自动扩容的方式,增加10000次,耗费时间=15

HashMap预先指定空间的方式,增加10000次,耗费时间=6

增加100000次

HashMap自动扩容的方式,增加100000次,耗费时间=25

HashMap预先指定空间的方式,增加100000次,耗费时间=21

增加1000000次

HashMap自动扩容的方式,增加1000000次,耗费时间=1707

HashMap预先指定空间的方式,增加1000000次,耗费时间=1611

增加10000000次

HashMap自动扩容的方式,增加10000000次,耗费时间=21054

HashMap预先指定空间的方式,增加10000000次,耗费时间=17820

HashMap大约就说这么多，再说说TreeMap。TreeMap是种红黑树的结构，能够对元素排序(红黑树、 数据库的B树、B+树，还有冒泡算法、快速排序算法这些算法领域的，现在还真是不那么掌握牢固)。为了保证排序，提供了两种方式：一种是Key对象实现Comparable接口，另外一种方式是单独提供Comparator实现类

public TreeMap(Comparator< super K> comparator) {

this.comparator = comparator;

}

如果本身Key对象的排序是确定的，比如Integer按大小排序，String按照字典排序，这些是无疑义的，所以它们都实现了Comparable接口，但假如说Person对象，有时需要按年龄排序，有时需要按身高排序，有时需要按薪酬排序，所以就没办法使用Comparable接口了，此时可以根据不同排序方式创建相应的Comparator类。

既然是按照顺序排列的树，那自然就需要提供一些数据结构方面的方法，所以TreeMap有了firstKey()、lastKey()、pollFirstEntry()、lowerEntry(K)、floorEntry(K)、headMap(K)、tailMap(K)、desendintMap()这样的方便方法。

相比HashMap，TreeMap还有个很大的不同，就是它不仅是继承AbstractMap，还实现了NavigableMap，NavigableMap继承自SortedMap，SortedMap继承自Map。SortedMap定义了什么？firstkey()、lastKey()、headMap(K)、tailMap(K)、subMap(K,K),NavigableMap定义了pollFirstEntry()、lowerEntry(K)、floorEntry(K)等方法。为什么这么设计？SortedMap是好理解的，针对可以排序的Map单独设一个接口，但为什么要NavigableMap呢？它的lowerEntry(K)之类的方法为什么不能合并到SortedMap里去？个人觉得这应该是两个版本时期导致的，NavigableMap是JDK1.6时加入的，此时已经有了不少SortedMap的子类，不是很有必要让子类也去实现这些方法，所以新加了个NavigableMap类，在需要lower的时候实现它即可，不需要时就直接实现SortedMap。也就是设计这种类库接口时的粒度问题，基本的方法在上一级接口定义，虽然另外一些方法也是正常使用，但根据它的频率、约束性有所不同可以下放，同时又要考虑不能使接口数量太多加大复杂性。

理解了Map，再来看Set就很简单了。HashSet内部完全是以Set元素为key，new Object()为value的HashMap

// Dummy value to associate with an Object in the backing Map

private static final Object PRESENT = new Object();

它的一些如size()、contain()方法都是直接调用map的方法。

public int size() {

return map.size();

}

public boolean add(E e) {

return map.put(e, PRESENT)==null;

}

TreeSet也是一样，且也有相配套的NavigableSet、SortedSet。

从整体来说，感觉Set设计地不是太好，其大多数功能和List很像，仅非重复这个频率并不高的场景不足以单独列这一套接口，而其实现上又基本上完全依托于Map。如果开发者真有这种场景，完全可以自行用HashMap来代替。

集合框架中还有两个很有用的辅助类，分别是Collections和Arrays，这两个就不多介绍了。Collections提供了一系列synchronized集合、unmodified集合以及很少用的Checked集合(类型检查的)，以及toArray(toArray(T[] a)更好用，因为能指定返回数组的元素类型)、binarySearch(快速查找算法，需要参数列表元素能排序，否则结果就不准确)。而Arrays提供了一些如sort、merge、binarySearch、copyOf、asList这样有效的方法，注意这里的asList返回的Arrays内部实现的一个ArrayList，有些方法不支持，比如add、remove，除了set之外基本上就是一个只读列表，如果需要可add/remove，还是需要使用集合的相应构造函数或者Collections的copy方法)。

最后两个需要说的是虽然是在java.util根目录下，但基本是为java.util.concurrent准备的，就是Queue(队列)和Deque(双向队列)。Queue的一系列子类如DelayQueue、LinkedBlockQueue更多地是和并发有关，这放到将来的JUC框架时再讲吧。