1.java集合是什么?
java集合实际上是一种经常被运用到的java类库,其中提供了已经实现的的数据结构,省去了程序员再次编写数据结构的事情.在Leetcode中经常会被用到,有很重要的作用.
集合体系
我们发现,无论是Set和List都是继承于Collection
接口,实现Collection
之中的方法,而他们又衍生出了HashSet
,LinkedList
等等我们经常使用的数据结构.
但是真相并不是如此的简单.
对于Collection
接口的实现,其实是由AbstractCollection
类完成的.
此类提供了
Collection
接口的骨干实现,从而最大限度地减少了实现此接口所需的工作。
Collection
中需要实现的的方法:
AbstractCollection
类实现的方法:
出了一个hashcode
方法,AbstractCollection
类实现了几乎所有的功能.
而AbstractCollection
类又有三个不同的子类AbstractList
, AbstractQueue
,AbstractSet
.我们从名字就可以知道,这就是三种不同的数据结构.于是这样基本就可以分析出来.
所有的集合都是依靠这种方式构建的,用一个抽象类实现接口,然后再用集合类去实现这些抽象类,来完成构建集合的目的.
这是完整的构建图.
这其实是为了大家有一个思想,就是在Collection实现的方法,在继承实现他的各个集合中也都会实现.
如下是本文的目录:
(一) Iterator接口–迭代器
这几个方法有着很重要的意义:
- 所有实现
Collection
接口(也就是大部分集合)都可以使用forEach功能. - 通过反复调用
next()
方法可以访问集合内的每一个元素. - java迭代器查找的唯一操作就是依靠调用next,而在执行查找任务的同时,迭代器的位置也在改变.
- Iterator迭代器remove方法会删除上次调用next方法返回的元素.这也意味之remove方法和next有着很强的依赖性.如果在调用remove之前没有调用next是不合法的.
这个接口衍生出了,java集合的迭代器.
java集合的迭代器使用
下面是迭代器的一个小栗子:
当然你也会有点好奇,为什么remove
方法前面必须跟着一个next方法.其实这个只能这么解释.
迭代器的next方法的运行方式并不是类似于数组的运行方式.
当然,这张图主要是让你理解一下.
数组的指针指向要操作的元素上面,而迭代器却是将要操作的元素放在运动轨迹中间.
本质来讲,迭代器的指针并不是指在元素上,而是指在元素和元素中间.
假设现在调用remove().被删除的就是2号元素.(被迭代器那个圆弧笼盖在其中的那个元素).如果再次调用,就会报错,因为圆弧之中的2号元素已经消失,那里是空的,无法删除.
(二) Collection接口
这个对象是一个被LIst
,Set
,Queue
的超类, 这个接口中的方法,构成了集合中主要的方法和内容.剩下的集合往往都是对这个接口的扩充.
方法如下:
其实我们并不一定要把这些方法都记住
我们只要记住Collection对象实现了这些种类的方法就可以了(可以现查API,不是..
但是确实,这些方法记住了有很大的用处.
java集合的泛型使用
到这里我们还要讲解一个问题,就是除了Map
的集合类型(看看上面的继承表,map是单独一个分支)都可以传入Collection为参数的函数里面去.
java集合中使用泛型的好处
为什么在java集合中经常使用泛型.除了为了防止输入错误的数据,更重要的是如果用了泛型也会让操作更加的方便,省去了强制转化的过程.
以下两个是准备
所以使用泛型有很大的好处.
(三) List
List是一个有序集合,元素会增加到容器中特定的位置,可以采用两种方式访问元素:使用迭代器访问或者使用一个整数索引访问.后一种方式称为随机访问.
为此List接口多定义了一些方法,来实现这一点
我们知道实现LIST接口的类中有一个类叫做AbstractList
,他的两个子类分别是LinkedList和ArrayList这两种.那么问题是链表可不可以使用这个add方法.
答案是可以的.实际上链表使用随机访问,只不过是慢了点而已.如果有可能,还是使用迭代器为好.
LIST主要有两种类.一个是LinkedList一个是ArrayList.
LinkedList
我们就从一个程序看一看LinkedList到底怎么用.
实际上LinkedList有非常多的方法,因为LinkedList是被用来实现多中数据结构的.不但可以实现队列,甚至还有可以实现栈的相关方法.
我们对此进行分类:
栈相关的操作方法:
队列操作方法:(LinkedList实现了Queue的接口,所以说可以操作用来构建队列)
注意队列是FIFO(先进先出)队列,所以按照实现,从普通队列是从队列的尾部插入,从头部移除,.
所以方法如下:
一般来讲集合中的方法在移除方法都会有一个为空的时候返回null的方法,和一个为空的时候返回null的方法.类似于pool()和remove()
我们一会到Queue的时候还会将这些再将一次.
ArrayList
我们也从一个程序来看这个
这个比较适合非顺序存储.
(四)(五)Set
Set实际上也是一种映射关系的集合和Map比较像.但是它实现的依然是Collection的接口.
而且Set中的方法和Collection的方法几乎完全一样.
唯一的区别在于add方法不允许增加重复的元素.在调用equal时,如果两个Set中的元素都相等,无论两者的顺序如何,这两个Set都会相等.
set
的特性
当然Set最主要的工作就是判断存在性,目的是看一个元素到底存不存在这个集合之中.
下面放上两个Set的例子:
SortedSet(TreeSet)
HashSet
这里要讲一下HashSet。HashSet不在意元素的顺序,根据属性可以快速的访问所需要的对象。散列表为每个对象计算一个整数,成为散列码…散列码是实例产生的一个整数。
散列表(HashSet)散列表用链表数组实现。每个列表称为通。想要查找表中对象的位置就计算它的散列码。然后与通的总数取余,得到的数就是保存这个元素的通的索引。
但是桶总有被沾满的一刻。
为了应对这种情况,需要用新对象与桶中所有对象比较,看是否存在。
为了控制性能就要能定义初始桶数,设置为要插入元素的75%-150%,最好为素数。
这个时候就要执行再散列,让这个散列表获得更多的内容。
再散列:
需要创建一个桶数更多的表,并将全部元素插入这个新表中。装填因子绝对什么时候在执行,如果装填因子为0.75那么就是在表中75%的位置被沾满时,表会给如双倍的桶数自动散列。
Queue
队列是数据结构中比较重要的一种类型,它支持 FIFO,尾部添加、头部删除(先进队列的元素先出队列),跟我们生活中的排队类似。
但是在集合中的Queue并没有单独的实现类,而是用LinkedList实现的。其实你只要看一眼LinkedList的方法就知道,他完全可以实现队列的操作。
Queue主要有两种不同的类型.
分别是优先级队列和Deque队列
PriorityQueue
优先级队列中元素可以按照任意的顺序插入,却按照目标排序的顺序进行检索,也就是无论什么时候调用remove移除的都是当前最小的元素。
优先级使用了一种堆,一个可以自我调节的二叉树,对树进行执行添加和删除。它可以让最小的元素移动到跟,而不必花时间对其排序。
当然,你也可以自己对其进行排序.
小栗子:
Deque
deque也有些复杂,它可以用ArrayDeque实现,也可以用LinkedList实现.
线性集合,支持两端的元素插入和移除。Deque是
double ended queue
的简称,习惯上称之为双端队列。大多数Deque 实现对它们可能包含的元素的数量没有固定的限制,但是该接口支持容量限制的deques以及没有固定大小限制的deque。作者:我是吸血鬼
链接:https://www.jianshu.com/p/d78a7c982edb
来源:简书
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
因为本身也是LinkedList实现的,所以其本身的方法和LinkedList差不了多少.
小栗子:
Stack
stack的名字大家都知道,就是栈.一个先进后出的数据结构,这里我并不认为应该使用java集合中提供的栈集合.
而是应该使用LinkedList来构建集合:
一个小任务:
用LinkedList实现栈
这样做有一个好处,就是这样的栈可以有更多种的方法,可以采用更多种的方式.无疑这样的栈会更好一些.
所以我推荐大家用栈的时候,用LinkedList来实现.
MAP
讲了Collection接口实现的各种集合,我们就要讲讲非Collection的集合.这意味着你在Collection中记住的方法在这个里面完全用不到了.
我们知道一些键的信息,想要知道与之对应的元素.映射结构就是为此设计的,映射用来存放键值对,如提供了键就能查到值.
和Set一样,HashMap要比TreeMap要快上一些,但是TreeMap有序.这与Set很相似,毕竟Set其实也是映射结构.
每当往映射加入对象是,必须同时提供一个键.
键是唯一的,不能对同一个键放两个值.如果对同一个键调用两次put方法,第二次调用会取代第一个.
要想处理所有的键和值,那就应该使用foreach
列子如下:
下面还有一个HashMap使用的例子
本文来自投稿,不代表程序员编程网立场,如若转载,请注明出处:http://www.cxybcw.com/197085.html