从38节到54节,我们介绍了多种容器类,本节进行简要总结,我们主要从三个角度进行总结:
用法和特点
我们在52节展示过一张图,其中包含了容器类主要的接口和类,我们还是用这个图总结一下:
容器类有两个根接口,分别是Collection和Map,Collection表示单个元素的集合,Map表示键值对的集合。
Collection表示的数据集合有基本的增、删、查、遍历等方法,但没有定义元素间的顺序或位置,也没有规定是否有重复元素。
List是Collection的子接口,表示有顺序或位置的数据集合,增加了根据索引位置进行操作的方法。它有两个主要的实现类,ArrayList和LinkedList,ArrayList基于数组实现,LinkedList基于链表实现,ArrayList的随机访问效率很高,但从中间插入和删除元素需要移动元素,效率比较低,LinkedList则正好相反,随机访问效率比较低,但增删元素只需要调整邻近节点的链接。
Set也是Collection的子接口,它没有增加新的方法,但保证不含重复元素。它有两个主要的实现类,HashSet和TreeSet,HashSet基于哈希表实现,要求键重写hashCode方法,效率更高,但元素间没有顺序,TreeSet基于排序二叉树实现,元素按比较有序,元素需要实现Comparable接口,或者创建TreeSet时提供一个Comparator对象。HashSet还有一个子类LinkedHashSet可以按插入有序。还有一个针对枚举类型的实现类EnumSet,它基于位向量实现,效率很高。
Queue是Collection的子接口,表示先进先出的队列,在尾部添加,从头部查看或删除。Deque是Queue的子接口,表示更为通用的双端队列,有明确的在头或尾进行查看、添加和删除的方法。普通队列有两个主要的实现类,LinkedList和ArrayDeque,LinkedList基于链表实现,ArrayDeque基于循环数组实现,一般而言,如果只需要Deque接口,ArrayDeque的效率更高一些。
Deque还有一个特殊的实现类PriorityQueue,它表示优先级队列,内部是用堆实现的,堆除了用于实现优先级队列,还可以高效方便的解决很多其他问题,比如求前K个最大的元素、求中值等。
Map接口表示键值对集合,经常根据键进行操作,它有两个主要的实现类,HashMap和TreeMap。HashMap基于哈希表实现,要求键重写hashCode方法,操作效率很高,但元素没有顺序。TreeMap基于排序二叉树实现,要求键实现Comparable接口,或提供一个Comparator对象,操作效率稍低,但可以按键有序。
HashMap还有一个子类LinkedHashMap,它可以按插入或访问有序。之所以能有序,是因为每个元素还加入到了一个双向链表中。如果键本来就是有序的,使用LinkedHashMap而非TreeMap可以提高效率。按访问有序的特点可以方便的用于实现LRU缓存。
如果键为枚举类型,可以使用专门的实现类EnumMap,它使用效率更高的数组实现。
需要说明的是,我们介绍的各种容器类都不是线程安全的,也就是说,如果多个线程同时读写同一个容器对象,是不安全的。如果需要线程安全,可以使用Collections提供的synchronizedXXX方法对容器对象进行同步,或者使用线程安全的专门容器类。
此外,容器类提供的迭代器都有一个特点,都会在迭代中间进行结构性变化检测,如果容器发生了结构性变化,就会抛出ConcurrentModificationException,所以不能在迭代中间直接调用容器类提供的add/remove方法,如需添加和删除,应调用迭代器的相关方法。
在解决一个特定问题时,经常需要综合使用多种容器类。比如要统计一本书中出现次数最多的前10个单词,可以先使用HashMap统计每个单词出现的次数,再使用47节介绍的TopK类用PriorityQueue求前十个10单词,或者使用Collections提供的sort方法。
在之前各节介绍的例子中,为简单起见,容器中的元素类型往往是简单的,但需要说明的是,它们也可以是复杂的自定义类型,也可以是容器类型。比如在一个新闻应用中,表示当天的前十大新闻可以用一个List表示,形如List<News>,而为了表示每个分类的前十大新闻,可以用一个Map表示,键为分类Category,值为List<News>,形如Map<Category, List<News>>,而表示每天的每个分类的前十大新闻,可以在Map中使用Map,键为日期,值也是一个Map,形如Map<Date, Map<Category, List<News>>。
数据结构和算法
在容器类中,我们看到了如下数据结构的应用:
每种数据结构中往往包含一定的算法策略,这种策略往往是一种折中,比如:
Collections实现了一些通用算法,比如二分查找、排序、翻转列表顺序、随机化重排、循环移位等,在实现大部分算法时,Collections也都根据容器大小和是否实现了RandomAccess接口采用了不同的实现方式。
设计思维和模式
在容器类中,我们也看到了Java的多种语言机制和设计思维的运用:
小结
本节我们从用法和特点、数据结构和算法、以及设计思维和模式三个角度简要总结了之前介绍的各种容器类。到此为止,关于容器类我们就介绍完了。
到目前为止,我们还没有接触过文件处理,而我们在日常的电脑操作中,接触最多的就是各种文件了,让我们从下一节开始,一起探讨文件操作。