Java 集合与数据类型
一. Java 集合和数据类型
Java 集合系列文章
Java 数据类型系列文章
String进阶之StringBuilder与StringBuffer
二. 集合框架
Java 集合框架一些列的接口和类来实现很多常见的数据结构和算法,例如 LinkedList
就是集合框架提供的实现了双向链表的数据结构,关于这一篇文章建议大家收藏,我会不断地完善和扩充它的内容,例如最下面的系列文章我以后也会对它进行不断的更新
集合框架的接口
集合框架提供了很多接口,这些接口都包含了特定的方法来实现对集合上的特定操作
我们将要学习这些接口以及子接口和它们的各种实现类,在开始之前我们先简单学习一下这些广泛运用的接口,可以看到整个集合框架,总共有三个顶级接口 Collection 和 Map 以及 Iterator,首先上面这图你需要记住,因为这张图你记住了,那你至少对整个 Java 集合框架是有了一个框架上的认识,接下来就是慢慢的将它填充,使其更加具体和细化
Collections Framework 和 Collection Interface 的区别
很多人可能对这二者感到困惑,Collection
interface 是 Collections Framework 的顶级接口,集合框架提供可一些列的实现了数据结构和算法的接口和实现类,顶级的接口除了Collection
还有Map
和 Iterator
.
Collections Framework 的意义
前面说到了集合框架实现了数据和算法的实现,它们可以被直接使用,,对使用者而言有两方面的意义
1、 我们不需要自己去写代码去实现这些数据结构和算法
2、即使我们实现了这些代码,我们也要面临如何去优化这些代码使其变得更加高效
除此之外集合框架还还允许我们针对特殊的数据使用不同的数据集合,例如
1、如果你想要数据是去重的,或者是唯一的,你可易使用Set
集合
2、如果你想存储 key/value 对,你可以使用 Map
集合
3、 ArrayList
提供了动态扩容的数组
Map 接口
在 Java 中, Map
接口允许元素以 key-value 对的形式存储,其中 key 作为获取特定元素的唯一方法,每个 key 都有和其对应的 value,也就是说 Map 中的元素是以 key-value 对存储的
Iterator 接口
在 java 中,Iterator 接口是用来访问集合中的元素的,并且它有一个子接口ListIterator
所有的 java 集合都有iterator()
方法,这个方法返回一个 iterator 实例,用来遍历集合中的全部元素
Collection 接口
Collection
接口是 Java collections framework 的顶级接口,整个 java 集合框架中也没有 Collection
接口的直接实现,Java 集合框架中提供的是它的子接口的实现,就像List
, Set
和 Queue
例如 java 的ArrayList
类就是实现了List
接口,而List
接口就是Collection
接口的子接口
Collection 的子接口
就像前面提到的,在 java 中有很多Collection
接口的子接口的实现类
1.List Interface
List
interface 是一个有序的集合,允许像数组一样添加或者删除元素
List 接口的方法
2.Set Interface
Set
接口允许我们将元素存储在不同的集合中,类似于数学中的集合,它不能有重复的元素
Set 的实现类
Set 的子接口
Set 接口的方法
3.Queue Interface
Queue
接口主要用在当我们想要 以 First In, First Out(FIFO) 的方式存储和访问集合中的元素的时候,在队列中元素从队尾添加,从队头删除
Queue 的主要实现类
Queue 的子接口
Queue 的主要方法
Collection 接口的方法
The Collection
interface includes various methods that can be used to perform different operations on objects. These methods are available in all its subinterfaces.
add()
- inserts the specified element to the collectionsize()
- returns the size of the collectionremove()
- removes the specified element from the collectioniterator()
- returns an iterator to access elements of the collectionaddAll()
- adds all the elements of a specified collection to the collectionremoveAll()
- removes all the elements of the specified collection from the collectionclear()
- removes all the elements of the collection
三. List 体系
首先上面的框架图可以表明顺序的关联关系,但并不全面,如 ArrayList 在继承了 AbstractList 抽象类的同时还实现了 List 接口。
List 是一个接口,继承了 Collection,同时 Collection 继承了 Iterable,表明 List 的实现类都是可用迭代遍历的;
AbstractList 是一个抽象类,实现了 List 接口,同时继承了 AbstractCollection,针对一些常用方法,如 add(),set(),remove(),给了默认实现,当然在具体的实现类中基本都重写了,该类中没有 get(),size()方法。
AbstractSequentialList 是一个抽象类,继承了 AbstractList 抽象类,实现了很多双向链表中根据索引操作的方法。
ArrayList、Vector、LinkedList、Stack 都是具体的实现类。
1 . ArrayList 和 Vector 对比分析
Vertor 扩容方法:
2. ArrayList 和 LinkedList 对比分析
上述的对比都是基于大数据量的情况下,如果只是几个元素或几十个元素,它们之间并没有多大区别。
问:插入效率为何说正常情况下 ArrayList 低,LinkedList 高呢?
答:我们清楚 ArrayList 之所以插入效率低,有两个原因会造成时间的消耗。
第一,当底层数组空间不足时需要扩容,扩容后需进行数组拷贝
第二,当不在数组末尾插入数据,那么就需要移动数组元素
知道了其插入效率低的原因后,那么很明显,数据扩容及拷贝只有在数组空间不足时才发生,如果我们正确使用,就像《阿里巴巴 Java 开发手册》中提到我们在创建集合对象时,就传递参数预先设置好数组大小,那么插入效率是非常高的;而 90%的情况下我们在添加元素时都调用的是 add(E e),直接在末尾添加元素,很少调用 add(int index, E e)在数组中部添加元素,这样其实移动数组元素就很少发生,因此插入效率也很高。
问:删除效率为何说正常情况下 ArrayList 低,LinkedList 高呢?
答:因为删除效率高、低不是绝对的。其实删除操作可以分为两部分。
第一:找到要删除的元素,这个通过索引找,ArrayList 的执行效率要远高于 LinkedList 的执行效率;通过 equals 找则需要遍历整个集合,ArrayList 和 LinkedList 执行效率基本一致。
第二:删除元素及后续操作,这个如果删除是最后一个元素,执行效率基本一致;如果是删除的中间元素,那么 ArrayList 需进行数组元素移动,而 LinkedList 只需搭建起该元素的上一个节点和下一个节点的关系即可,LinkedList 执行效率高于 ArrayList。
因此,需根据实际情况才可判断实际的执行效率。
问:遍历效率这个问题怎么说?
答:ArrayList 通过数组实现,天然可以通过数组下标读取数据,顺序遍历、随机遍历效率都非常高;LinkedList 通过双向链表实现,顺序遍历时,可直接通过本节点.next()直接找到相关联的下一个节点,效率很高,而如果 LinkedList 随机遍历时,首先需判断(传递的索引值与集合长度/2)的大小,来确定接下来是应该从第一个节点开始找还是最后节点开始找,越是靠近集合中部、集合越大,随机遍历执行效率越低。
ArrayList 也是有顺序的
##四. Map 体系
capacity 集合可以容纳的元素个数(capacity 是 8 意味着可以容纳 8 个元素)
loadFactor 加载因子主要指的是当集合容纳集合的百分之多少的元素就需要扩容(loadFactor 0.75 就是说当容纳集合大小的 75%之后,就需要扩容了)
Map 接口的主要实现类
Map 接口的子接口
HashMap 、TreeMap 、LinkedHashMap 对比
一般情况下,使用最多的是 HashMap。在 Map 中进行常规的插入、删除和定位元素时就使用 HashMap,需要按自然顺序或自定义顺序遍历键的情况下使用 TreeMap
五. Set 体系
Set 接口的实现类
1. LinkedHashSet 和 HashSet 对比
2. LinkedHashSet 和 TreeSet 对比
六. 总结
我们知道一般情况下我们划分内存的标准是连续或者不连续,在这种划分方式下诞生出了两种数据结构,一种是数组以使用连续内存为代表的一种是链表可以使用非连续内存的代表,接下来我们从这二者的角度去看一下集合的对比
评论