(55) 容器类总结 / 计算机程序的思维逻辑

38节54节,我们介绍了多种容器类,本节进行简要总结,我们主要从三个角度进行总结:

  1. 用法和特点
  2. 数据结构和算法
  3. 设计思维和模式

用法和特点

我们在52节展示过一张图,其中包含了容器类主要的接口和类,我们还是用这个图总结一下:

容器类有两个根接口,分别是Collection和Map,Collection表示单个元素的集合,Map表示键值对的集合。

Collection表示的数据集合有基本的增、删、查、遍历等方法,但没有定义元素间的顺序或位置,也没有规定是否有重复元素。

List是Collection的子接口,表示有顺序或位置的数据集合,增加了根据索引位置进行操作的方法。它有两个主要的实现类,ArrayListLinkedList,ArrayList基于数组实现,LinkedList基于链表实现,ArrayList的随机访问效率很高,但从中间插入和删除元素需要移动元素,效率比较低,LinkedList则正好相反,随机访问效率比较低,但增删元素只需要调整邻近节点的链接。

Set也是Collection的子接口,它没有增加新的方法,但保证不含重复元素。它有两个主要的实现类,HashSetTreeSet,HashSet基于哈希表实现,要求键重写hashCode方法,效率更高,但元素间没有顺序,TreeSet基于排序二叉树实现,元素按比较有序,元素需要实现Comparable接口,或者创建TreeSet时提供一个Comparator对象。HashSet还有一个子类LinkedHashSet可以按插入有序。还有一个针对枚举类型的实现类EnumSet,它基于位向量实现,效率很高。

Queue是Collection的子接口,表示先进先出的队列,在尾部添加,从头部查看或删除。Deque是Queue的子接口,表示更为通用的双端队列,有明确的在头或尾进行查看、添加和删除的方法。普通队列有两个主要的实现类,LinkedListArrayDeque,LinkedList基于链表实现,ArrayDeque基于循环数组实现,一般而言,如果只需要Deque接口,ArrayDeque的效率更高一些。

Deque还有一个特殊的实现类PriorityQueue,它表示优先级队列,内部是用实现的,堆除了用于实现优先级队列,还可以高效方便的解决很多其他问题,比如求前K个最大的元素、求中值等。

Map接口表示键值对集合,经常根据键进行操作,它有两个主要的实现类,HashMapTreeMap。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>>。

数据结构和算法

在容器类中,我们看到了如下数据结构的应用:

  • 动态数组:ArrayList内部就是动态数组,HashMap内部的链表数组也是动态扩展的,ArrayDeque和PriorityQueue内部也都是动态扩展的数组。
  • 链表:LinkedList是用双向链表实现的,HashMap中映射到同一个链表数组的键值对是通过单向链表链接起来的,LinkedHashMap中每个元素还加入到了一个双向链表中以维护插入或访问顺序。
  • 哈希表:HashMap是用哈希表实现的,HashSet, LinkedHashSet和LinkedHashMap基于HashMap,内部当然也是哈希表。
  • 排序二叉树:TreeMap是用红黑树(基于排序二叉树)实现的,TreeSet内部使用TreeMap,当然也是红黑树,红黑树能保持元素的顺序且综合性能很高。
  • 堆:PriorityQueue是用堆实现的,堆逻辑上是树,物理上是动态数组,堆可以高效地解决一些其他数据结构难以解决的问题。
  • 循环数组:ArrayDeque是用循环数组实现的,通过对头尾变量的维护,实现了高效的队列操作。
  • 位向量:EnumSet是用位向量实现的,对于只有两种状态,且需要进行集合运算的数据,使用位向量进行表示、位运算进行处理,精简且高效。

每种数据结构中往往包含一定的算法策略,这种策略往往是一种折中,比如:

  • 动态扩展算法:动态数组的扩展策略,一般是指数级扩展的,是在两方面进行平衡,一方面是希望减少内存消耗,另一方面希望减少内存分配、移动和拷贝的开销。
  • 哈希算法:哈希表中键映射到链表数组索引的算法,算法要快,同时要尽量随机和均匀。
  • 排序二叉树的平衡算法:排序二叉树的平衡非常重要,红黑树是一种平衡算法,AVL树是另一种,平衡算法一方面要保证尽量平衡,另一方面要尽量减少综合开销。

Collections实现了一些通用算法,比如二分查找、排序、翻转列表顺序、随机化重排、循环移位等,在实现大部分算法时,Collections也都根据容器大小和是否实现了RandomAccess接口采用了不同的实现方式。

设计思维和模式

在容器类中,我们也看到了Java的多种语言机制和设计思维的运用:

  • 封装:封装就是提供简单接口,并隐藏实现细节,这是程序设计的最重要思维。在容器类中,很多类、方法和变量都是私有的,比如迭代器方法,基本都是通过私有内部类或匿名内部类实现的。
  • 继承和多态:继承可以复用代码,便于按父类统一处理,但我们也说过,继承是一把双刃剑。在容器类中,Collection是父接口,List/Set/Queue继承自Collection,通过Collection接口可以统一处理多种类型的集合对象。容器类定义了很多抽象容器类,具体类通过继承它们以复用代码,每个抽象容器类都有详细的文档说明,描述其实现机制,以及子类应该如何重写方法。容器类的设计展示了接口继承、类继承、以及抽象类的恰当应用。
  • 组合:一般而言,组合应该优先于继承,我们看到HashSet通过组合的方式使用HashMap,TreeSet通过组合使用TreeMap,适配器和装饰器模式也都是通过组合实现的。
  • 接口面向接口编程是一种重要的思维,可降低代码间的耦合,提高代码复用程度,在容器类方法中,接受的参数和返回值往往都是接口,Collections提供的通用算法,操作的也都是接口对象,我们平时在使用容器类时,一般也只在创建对象时使用具体类,而其他地方都使用接口。
  • 设计模式:我们在容器类中看到了迭代器、工厂方法、适配器、装饰器等多种设计模式的应用。

小结

本节我们从用法和特点、数据结构和算法、以及设计思维和模式三个角度简要总结了之前介绍的各种容器类。到此为止,关于容器类我们就介绍完了。

到目前为止,我们还没有接触过文件处理,而我们在日常的电脑操作中,接触最多的就是各种文件了,让我们从下一节开始,一起探讨文件操作。

原文发布于微信公众号 - 老马说编程(laoma_shuo)

原文发表时间:2016-11-14

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏分布式系统和大数据处理

C#理解泛型(译)

Visual C# 2.0 的一个最受期待的(或许也是最让人畏惧)的一个特性就是对于泛型的支持。这篇文章将告诉你泛型用来解决什么样的问题,以及如何使用它们来提高...

793
来自专栏有趣的Python

算法与数据结构(四)堆排序:优先队列实现

堆排序 排序次要的,接触新的数据结构;堆 堆和优先队列 Heap and Priority Queue 什么是优先队列? 普通队列:先进先出;后进后出 优先队...

4245
来自专栏Java Web

数据结构与算法(4)——优先队列和堆什么是优先队列?堆和二叉堆LeetCode相关题目整理

听这个名字就能知道,优先队列也是一种队列,只不过不同的是,优先队列的出队顺序是按照优先级来的;在有些情况下,可能需要找到元素集合中的最小或者最大元素,可以利用优...

3481
来自专栏小怪聊职场

从数组、链表开始聊聊HashMap的实现原理,据说是阿里面试必问的题(小怪的Java群话题讨论内容)

1K6
来自专栏xingoo, 一个梦想做发明家的程序员

Java程序员的日常 —— 《编程思想》持有对象

集合框架可以说是Java里面必备的知识点了,日常的使用中也会遇到各种情况需要使用到集合。下面就简单介绍下各种集合的使用场景: ? List List可以看...

2168
来自专栏闻道于事

Java基础类库

3246
来自专栏菩提树下的杨过

javascript:双链表-插入排序

数组存储前提下,插入排序算法,在最坏情况下,前面的元素需要不断向后移,以便在插入点留出空位,让目标元素插入。 换成链表时,显然无需做这种大量移动,根据每个节点的...

22810
来自专栏java工会

java集合详解

23810
来自专栏一英里广度一英寸深度的学习

线性排序算法-堆排序 (2)

在学数据结构的时候,链表、堆栈、树三种数据结构印象最深刻。当时理解有误区,堆栈被当成一种结构,可能因为堆栈有同样的特性——只关心堆顶或栈顶的元素。

1613
来自专栏大数据钻研

Java 集合框架 HashSet 和 HashMap 源码剖析

总体介绍 之所以把HashSet和HashMap放在一起讲解,是因为二者在Java里有着相同的实现,前者仅仅是对后者做了一层包装,也就是说HashSet里面有一...

3006

扫码关注云+社区