最新消息:从今天开始,做一个有好习惯的人。

java里集合这些事情-Collection

java体系 迷路的老鼠 5345浏览 6评论

本文将详细的聊一下Collection 相关的一些细节

前面说到了Collection包含List、Set等(queue这里不详谈),前面也说到了List是有序可重复,Set是无序不重复,这是两个特点。那我们就先这两个点总结一下,是怎么实现这两个特点的。

List最常用的是ArrayList/LinkList,ArrayList通过数组的新增进行排序,LinkList通过线性双向线链表实现排序(1.7以前是通过环形的双向链表)

Set最常用的HashSet和LinkedHashSet是通过Hash散列保证唯一性,但是link通过链表的方式实现了Set的有序性,这个是个体的差异,还有一个TreeSet,也是一个个体差异,通过红黑树实现有序和唯一性。

下面详细说一下ArrayList和LinkList的一些特点和区别

ArrayList和LinkList最大的区别就是数据结构,ArrayList是数组,LinkList是链表。从数据结构上看,ArrayList的查询会快一点,因为LinkList的查询走的是链表,需要逐个去查找,而数组本身具有下标索引。

网上说的ArrayList相对新增、删除会慢一点,目前主要的依据是数组结构的新增和删除是用过copy来实现的(保证内存连续),而链表是通过上一个元素的指向实现。但是有人做过实测证明,在高版本的jdk中体现并不是很明显。所以这个说法是有待商榷的。

ArrayList的扩容:

  • 新增扩容,如需扩容,则在原有容量的基础上扩容1.5倍,再把原对象复制过去,再讲需要新增的对象放入N+1的位置;
  • 删除降容,将需要删除的下标的位置标记为N,将N+1到数组长度的所有元素复制到N到数组长度-1的位置,然后删除最后一个位置的数据(如果是根据对象删除则需要遍历数组,效率会比较低,所以尽量走下标删除)

LinkList的一些特点

LinkList是线性双线链表(1.7及以上),每一个LinkList节点对象都包含 first头结点和last尾结点

添加节点时,会调用 linkLast 在尾节点处新增一个节点,如果是按照下标新增节点,需要额外修改上一个节点的下节点指向。

删除节点时,都会统一调用 unlink 方法来释放上一个节点的下节点指向和下一个节点的上节点指向。

值得一提的是,LinkList也实现了 queue ,因为他的数据结构和队列比较类似,都有首节点和尾结点标记,也可以作为队列来使用。

然后来说说Set,HashSet是依靠hashCode和equels来实现唯一性,首先会根据对象的hashCode进行一次重复性校验,如果发现重复,再对对象的equals进行一次校验,如果两次校验都表明重复,那就重复了。在做对象比较和去重实,很多情况都是针对对象的个别或特定的几个属性值去重,这时,我们就需要重写hashCode和equals(如果不重写,那判断的是两个对象的内存地址)。

如上所述,HashSet其实质是一个初始化容量为16的、key和value相同的 HashMap 。其值存在HashMap的key上。 LinkedHashSet 其实质是一个同样的LinkedHashMap。

TreeSet,它的数据结构是红黑树,也就是二叉树(弱平衡二叉树,绝对平衡二叉树性能相对低一点),所以它是有序的,它的有序是使用比较器实现,如不自定义比较器,将按照默认排序。 TreeSet对象的类必须实现Comparable接口。

转载请注明:迷路的老鼠 » java里集合这些事情-Collection

发表我的评论
取消评论

表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

网友最新评论 (6)

  1. 抢第一哈哈哈哈哈
    迷你涛哥5年前 (2019-09-29)回复
    • 感觉写的思维有点混乱
      迷路的老鼠5年前 (2019-09-29)回复
  2. 喔~HashSet存储的对象不能重复
    wa5年前 (2019-09-30)回复
    • 你确定你是认真的吗?
      迷路的老鼠5年前 (2019-09-30)回复
      • 好吧,外行人士发表了不当评论……囧
        wa5年前 (2019-09-30)回复
        • 要相信自己,就算是瞎说
          迷路的老鼠5年前 (2019-09-30)回复