文档章节

集合框架

凯哥学堂
 凯哥学堂
发布于 2017/07/29 14:07
字数 3370
阅读 5
收藏 1

公孙少典

1.链表集合

什么链表集合? 链表集合分为单链集合和双链集合,其中这里的“链”字表示引用的意思,那单链也可以叫单引用集合?双链也可以叫双引用集合?这说明链表里面除了存值以外还存了引用吗?那这个引用是什么的引用呢? 为啥要搞链表集合? 我们知道数组存值是有长度限制的,但是我们的数组集合已经解决了无限制长度问题,且能存所有的对象了,为啥还要链表集合? 数组集合虽然能够无限制存储,不停的扩展存储来实现无限制,但是它是不太方便在头、尾、中间进行删除、插入、修改等操作,这就是数组集合的缺点了,修改不灵活,虽然数组集合的添加、修改的速度快一点,但是不灵活,所以我们想做一种可以灵活修改,想加长就加长、想缩短就缩短,能随意的在头、尾、中间进行插入、删除、修改操作的一个集合,也就是为了搞一个灵活的集合出来。 链表集合很灵活,但是修改的速度稍微比数组集合慢一丢丢。 链表的算法的实现:同样离不开数组的,链表可以想象成链条,链条的优点:想加长就加长、想缩短就缩短,想更换其中某个坏的就随意【学Java,到凯哥学堂kaige123.com】更换其中的坏的节点。 单链集合实现原理:

image

单链集合的实现是使用长度为2的数组,分别存储数据和引用,其中这个引用是对下家数组的引用,单链集合只能从上家找下家,无法从下家找上家。 双链集合原理:

image

双链集合既可从上家找下家,也可从下家找到上家,在集合的头部、尾?imageMogr2/blur/1x0/quality/75|watermark/1/image/aHR0cDovL29zNzhmNGhueS5ia3QuY2xvdWRkbi5jb20vd2F0ZXJtYXJrLnBuZw==/dissolve/50/gravity/SouthEast/dx/10/dy/10|imageslim部、中间插入、删除、修改都很方便。 双链代码实现:

image

由上可知,我们用长度为3的数组来存储对象,链表这个东西是要有头部和尾部的,定义两个Object[]数组,分别为头部和尾部节点,其中头部应该存第一次存入的对象,且它应该是保持不动的,而尾部,则会随着一个个不断存入的对象而往下移动。

image

第一次存入第一个对象的时候,head是null的,建一个数组,值为要存的obj,此时上家和下家的引用都不知道,都是null,然后呢因为只有一个值,所以head和tail都是指向这个数组的。 当后续存入的值的时候,head就不是null了,此时要新建一个长度为3的数组来存新的值,新建的数组为objs,它的值是obj,此时可以知道它的上家是tail,而它的下家不知道则是null,此外,还知道tail的下家是新存入的objs,所以tail[2]=objs,把这两层引用关系表达出来后呢,因为新存入了对象,所以尾部是要往下移动的,所以tail=objs,新存入的对象就成了新的尾部了。这就完成了。 链表的实现,最重要的就是搞清楚各个节点之间的引用关系,当一个对象失去了引用的时候,也就相当于被删除了,gc会回收它的。 关于LinkedList和ArrayList的效率问题,可以使用飞行器来检测的,ArrayList的修改速度是要比LinkedList快的,但是LinkedList更加灵活,至于内存消耗和cpu消耗相差不大,linkedList的cpu消耗会稍微少点。 向后添加的方法addLast(Object obj) 这个方法实现的话就可以直接调用add方法了,因为add就是向后添加的啊:

image

添加到前面的方法addFirst(Object obj) 这个方法是在头部的地方加入一个值,实现代码如下:

image

向前添加的方法,如果是第一次存入对象,则向前添加和add的性质一样,直接调用add方法,如果不是第一次存入对象,则要新建一个数组objs存值,并且放在头部的前面,此时知道的引用关系为:objs的下家是head,head的上家是objs,把两层关系表达完后,objs成为新的头部,完成。 向前删除:removeFirst()

image

向前删除的时候,看是不是里面没有值,没有值就抛异常,再看看是不是只有一个值,只有一个值的话我们很轻松的把头部和尾部一起置为空,就删除了,如果不止一个值,我们要删除一个头部的话,就要断了所有的其他数组对它的引用,当然这里只有一个下家数组对它有一个向上的引用,而且删了头部,则头部下家就成了新的头部。所以让头部下家成为新的头部,然后再把新的头部的向上引用断开(置空),这样就完成了。 向后删除代码实现:removeLast()

image

向后删除的时候,我们先看是不是没有值,没有值就抛异常,再看是不是只有一个值,只有一个值的话,我们就把头部和尾部一起置空,当不止一个值的时候,要删除尾部,我们知道只有尾部的上家对尾部有一个向下的引用,我们的目标是断掉这个引用,可以先把尾部上家变成新的尾部,然后再把新的尾部的向下引用置空,这就完成了。 中间插入方法:add(int index,Object obj)

image

中间指定下标插入一个对象的时候,我们要先定位,确定在哪个元素的前面插入一个新元素,定位好后,要续上4条引用,然后就算完成,定位需要新建一个数组来存一个个取出来的值,采用while循环,因为不确定次数,需要看条件index0,在一个一个找的时候,如果出现取出来的objsnull说明,取值的时候,把值取完了,说明index太大了,那就要抛异常了。 当定位完了之后,我们取出来的值(存在objs中),我们是要在objs前面插入一个对象,那我们要再新建一个数组objs1存要新插入的对象,它的数据对象obj,此时我们知道两条引用关系:就是objs1的上家是objs的上家objs[0],objs1的下家是objs,所以:Object[] objs1=new Object[]{objs[0],obj,objs};续完这两条引用关系,再续另外两条,我们还知道,objs的上家的新下家是objs1了,并且objs的新上家也是objs1了,把这两条引用续上,那就完成了。 按下标删除方法remove(int index,Object obj):

image

按下标删除,像这种要进行删除的方法(包括向前删除、向后删除),最先考虑的是这个链表是不是空的,是的话就抛异常,然后既然不是空的,就看下标是不是删头部,如果是,就调用现存的向前删除,如果不是删头部,就要定位了,定位从头部开始往下撸,所以把head交给申请的暂存取出来的元素的object数组,然后while循环,不知道具体的次数,只能靠条件index==0来进行循环跳出。在循环里面一直把下家取出来,取出下家后,要看看是不是null,如果取着取着变成空了,就要抛异常了,当撸到index为0的时候,我们就成功定位到了我们要删除的元素了,这是要看它是不是尾部,如果是尾部,调用现存的向后删除,如果不是尾部,我们则要先把要删除的元素的上下家取出来,然后把上下家对这个将被删除的引用断开,要断开的引用分别是上家对它的向下引用和下家对它的向上引用,当然这里用不着置空,直接把下家向上引用给上家,上家的向下引用给下家,就把这个元素越过去了,也就完成了。 hasNext()和next()方法,这两个方法用来把链表的所有值打印出来:

image

hasNext方法和next方法是用来把整个链表打印出来的方法,next用来返回值,hasNext用来判断取出来的对象数组是不是空,不是空就是有值的,我们先看链表是不是空,如果是空,直接false,如果不是空,要看是不是取第一个,取第一个直接把头部给过去,若不是取第一个,则取下家,取出来的下家要防止它是空的,是空的就要false,那剩下的情况就是true了。 ArrayList集合的优点是添加速度很快,LinkedList集合的优点是修改非常灵活,每个集合都有各自的优点的,再使用的时候可以组合起来使用。 链表的好处:由于它的修改非常方便、灵活,而且尽然有删头部,删尾部,头部添加,尾部添加这样的方法,就使得它可以运用到队列中去,可以用来进行排队(队列中的执行顺序是:先来先执行,后来后执行)。 对于队列模式下:队列中如果有非常多的任务,要让任务排队不停的执行,我们可以使用linkedlist来处理,在任务队列中的头部的地方使用removeFirst()方法,不停的把执行完了的任务删除掉,在任务队列的尾部使用addLast方法,不停的往任务队列中添加新的任务,这样我们就可以不停的把任务压入到任务队列中,让任务一个一个不停的去执行。

image

添加的任务从后面进来,删除的任务从前面出去,这就是一个队列的模型。链表集合的存储方式非常擅长制作队列数据。 2.哈希集合 哈希集合的好处:我们要弄出哈希集合来是有原因的,它是专门做检索的,它的检索的速度非常快,这是它最大的优点,检索速度相当快,非常快能查找到数据。它的缺陷是,添加速度比较慢一些。 检索就是给你一个值,看这个值是否存在这个集合里面。检索的专长就是检索。

检索速度展示:

image

相比之下,ArrayList的检索速度就慢了很多了

image

这就是为啥说HashSet的专长是检索了。

原理图:

image

哈希为什么会有这么快的检索速度呢?原来是原因的,因为它在把值存入数组中时就做了手脚,当然在检索的时候也是有窍门的。 比如,要把”AAA”/”BBB”/”CCC”这三个值存入到一个长度为18的数组中,它就会进行一个处理了它把要存入的所有数据进行一次区域划分,用对象的hashCode值去对数组长度进行取余运算,取余运算得出来的结果是多少就把值挂到相应的下标下面,这样就能保证每个要存入的数据都是在数组长度的范围呢,比如,这里数组长度为18,我们hashCode()%18,这样结果就是0-17,刚好对应数组的所有下标,就相当于把所有要存入的数据进行了一次区域划分,但是要存入的数据有很多个啊?就有可能会导致不同的值算出来的hashCode()%18结果是一样的,那就把不同的值挂到同一个数组下标下面去了。其实不同的值挂到同一个下标下面去也没有关系,它会把后面【学Java,到凯哥学堂kaige123.com】挂过来的值挂到前面的值的下家,形成一个单链,其中第一个值是长度为3的数组存储,它第0个放值,第1个放下家引用,第2个放单链最后一个对象的引用,而后面的值都是长度为2的数组存储,第0个放值,第1个放下家的引用。这样就相当于数组里面存储的是单链集合了。 那哈希检索的时候也是有手段的,比如“BBB”需要进行检索,它会取出“BBB”的hashCode值,去%18,得到一个结果,然后用这个结果直接到对应的区域上去找了,相当于进行了精确定位,但是数组集合来检索的话,他就要从头到尾一个一个去询问的了,这就是为啥数组集合检索这么慢的原因了。 代码实现: 我们首先要申请一个数组,来存值,实际上,真正的哈希集合的数组是可以自动变长的。

image

© 著作权归作者所有

凯哥学堂
粉丝 18
博文 316
码字总数 284948
作品 0
东城
程序员
私信 提问

暂无文章

一、docker 入坑(win10和Ubuntu 安装)

前言 终究还是绕不过去了,要学的知识真的是太多了,好在我们还有时间,docker 之前只闻其声,不曾真正的接触过,现在docker 越来越火,很多公司也都开始使用了。所以对于我们程序员而言,又...

quellanan2
2分钟前
2
0
AutoCompleteTextView

小技巧按菜单键 当菜单打开之前会调用onMenuOpened(int featereId,Menu menu),可以重写这个方法,弹出对话框或者Popmenu 再布局中添加控件AutoCompleteTextView. <AutoCompleteTextVie...

逆天游云
6分钟前
2
0
谷歌软件商店:推出5美元会员 可用数百个软件

腾讯科技讯,谷歌和苹果是全球两大智能手机操作系统的运营者,两家公司旗下分别拥有占据行业垄断地位的谷歌软件商店和苹果软件商店。据外媒最新消息,手机软件商店的商业模式正在发生一些变化...

linuxCool
28分钟前
1
0
RocketMQ 多副本前置篇:初探raft协议

Raft协议是分布式领域解决一致性的又一著名协议,主要包含Leader选举、日志复制两个部分。 温馨提示: 本文根据raft官方给出的raft动画进行学习,其动画展示地址:http://thesecretlivesofda...

中间件兴趣圈
28分钟前
1
0
elasticsearch 6.8.0 添加认证

1. 修改elasticsearch-6.8.0/config/elasticsearch.yml 最后添加一行:xpack.security.enabled: true 2. 初始化用户和密码 ./bin/elasticsearch-setup-passwords interactive 我这里初始化为......

coord
30分钟前
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部