请选择 进入手机版 | 继续访问电脑版
尚学堂集团旗下品牌:尚学堂速学堂百战程序员云数学院[切换校区]

java世界一日游之集合访谈 隐藏

0 1662
回帖奖励 10 学堂币回复本帖可获得 10 学堂币奖励! 每人限 1 次
本帖最后由 当你老了 于 2018-10-26 17:11 编辑

大家好,我是你们的老朋友了,还记得上次咱们共同参观的美丽java世界吗,我们认识了暖男catch、懒汉员工throws和霸道总裁finally等等有趣的灵魂和好看的皮囊。而我这个实习导游也正式转正了。快,恭喜我!好了,话不多说,今天我再带领大家去认识一些新朋友--容器or集合。

也许有人会想说:“噢,容器我知道,装东西的嘛,我家的杯子就是容器,可是这有啥好说的呢?难道这个容器有啥特殊本领吗?”
别说,还真有。在我们java世界中需要装载的东西只有一种,那就是数据。容器就负责存储数据了。说句不负责任的话,可以说容器掌握着我们java世界的经济脉搏了。

在容器中有个最高接口,也就是你们人类常说的最高领导人了,他就是Collection接口,坐镇中军,统领大局。他还有两个干儿子List接口和Set接口,一文一武。大儿子List有序且不唯一,小儿子Set无序且唯一。
让我给大家介绍下啥叫有序,啥叫唯一吧。

有序就是存储的数据按照索引的顺序存进List集合中,可不是说数据小的就能排前面。至于唯一性就是说这个数据的内容只能在Set集合中存一个。比如有1231是个数据,那么只有123能存进Set集合中,最后一个1是放不进去了,因为之前已经有一个1Set集合里了。
怎么样,很智能吧。咱java世界中还是有很多能人异士的,嘿嘿。

这个大儿子List有两个实现类分别是ArrayListLinkedList。我们常见的集合就是ArrayList了,ArrayList可是非常强大的,他由一个Object数组蜕变而成。
看到这里,想必大家也能大致明白到ArrayList的一个特点了,没错,他能存下任意类型的数据,简直就是一个大胃王。他还有一个数组没有的功能,我们都知道数组的长度是固定的,不能改变的,但是ArrayList就突破了古老的限制,做到了长度可变化,实现了自动扩容。那么他是如何做到的呢?

接下来,就由在下给大家揭开他那神秘的面纱。
其实这个扩容规则也挺简单的,就是先初始化一个长度为10Object数组,然后只要每次存了数据,这个数组的长度就会加1,当数组的长度等于10,这个时候ArrayList就会创建一个新的数组,新数组的长度就在原数组的基础上乘以1.5ok了,然后再把原数组的内容复制到新数组里,这样就实现了自动扩容。怎么样,是不是很神奇啊!
由于ArrayList底层是数组的原因,所以他的根据索引查找元素的效率很快,但是根据内容查找元素的效率就相对较低了,而且删除,插入元素的效率也会慢一些,因为数组每删一个元素就意味着要把每一个数组往前挪一位。

但是这并不影响我们对ArrayList的优良性能的评价,毕竟人无完人,类无完类嘛。

说完了ArrayList我再给大家介绍下LinkedList,这次底层不是数组了,而是一个双向链表。有些人可能不了解啥是链表。举个栗子吧,相信火车大家都很熟悉吧,毕竟是大家日常出远门的交通工具嘛。将链表比作火车的7号车厢,链表的头结点就是火车头,尾节点就是火车尾,前驱结点顾名思义就是上一个节点嘛,也就是6号车厢,那后继节点自然就是8号车厢了,每一个节点都包含了三部分数据,指向上一个节点的引用,存储的数据和指向下一个节点的引用。这个引用就像是火车之间各车厢连接的挂钩,他将每一列火车都连接起来,指引我们从火车头走到火车尾。所以,LinkedList插入和删除元素的效率就比较高了,因为这个不需要大量移动元素,而是将前后的引用拆掉给新的节点连接上就好了。

说完List再来聊聊Set吧,Set旗下也有两名大将分别是HashSetTreeSet。先谈谈TreeSet吧,TreeSet底层使用的是红黑树,何谓红黑树呢?

红黑树有五个性质:
1. 节点是红色或者黑色;
2. 根节点是黑色;
3. 每个叶子节点都是黑色的
4. 每个红色节点的两个子节点都是黑色
5. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点
正是因为这些特性的存在,红黑树就得通过旋转和变色才能保持平衡。变色就是将红的变成黑的,黑的变成红的,跟画画似得,可好玩了。

左旋:
左旋.png
右旋:
    右旋.png
以及当新增节点n的时候,红黑树是如何保持平衡的。
        A、n是p左子节点,p是g的左子节点。        右旋然后变色
      1.png

       B、n是p右子节点,p是g的右子节点。        左旋然后变色
2.png
       C、n是p左子节点,p是g的右子节点。        右旋再左旋然后变色

3.png
       D、n是p右子节点,p是g的左子节点。        左旋再右旋然后变色
4.png
       2、叔父节点u是红色时,上面的那4种情况就会起冲突,因为每次旋转后,u都会变成p的右子节点,这样就出现了两个连续的红色节点,
        如果直接变色的话,当g的父节点gp也是红色的话也会起冲突这个时候就需要从插入节点n向根节点root进行回溯两次,第一次回溯处理所有两个红色节点的兄弟节点变成黑色,他两的父节点变成红色,第二次回溯就专门处理连续的红色节点冲突,这个时候叔父节点就是黑色的了,和上面四种情况一样处理。

回溯前直接变色:
5.png
第二次回溯后:
6.png
各位,我看今日天色也不早了,不如今天的java世界游玩就到这里吧,欢迎大家下次再来玩,下次我再给大家好好介绍一下神奇的Map集合。


分享到 :
人收藏 回复 使用道具
*滑动验证:
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

返回顶部