欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

Java基础篇——集合浅谈

程序员文章站 2022-03-30 21:51:48
原创不易,如需转载,请注明出处 "https://www.cnblogs.com/baixianlong/p/10703558.html" ,否则将追究法律责任!!! Set(基于Map来实现的,不细说) HashSet(不重复、无序、非线程安全的集合) 底层实现,源码如下: public clas ......

原创不易,如需转载,请注明出处,否则将追究法律责任!!!

set(基于map来实现的,不细说)

hashset(不重复、无序、非线程安全的集合)

  • 底层实现,源码如下:

      public class hashset<e> extends abstractset<e> implements set<e>, cloneable, java.io.serializable {
    
          static final long serialversionuid = -5024744406713321676l;
          //卖个关子,这里为啥要用transient关键字? 评论区见哦!
          private transient hashmap<e,object> map;
          private static final object present = new object();
    
          public hashset() {
              map = new hashmap<>();
          }
          public boolean add(e e) {
              return map.put(e, present)==null;
          }
          ...
      }

    不用多说,是不没想到,原来hashset是基于hashmap实现的,元素都存到hashmap键值对的key上面,而value时有一个统一的值private static final object present = new object();

  • 注意:
    1. 对于hashset中保存的对象,主要要正确重写equals方法和hashcode方法,以保证放入set对象的唯一性
    2. hashset没有提供get()方法,愿意是同hashmap一样,set内部是无序的,只能通过迭代的方式获得

treeset(不重复、有序、非线程安全的集合)

  • 底层实现,源码如下:

      public class treeset<e> extends abstractset<e> implements navigableset<e>, cloneable, java.io.serializable {
    
          private transient navigablemap<e,object> m;
          private static final object present = new object();
          treeset(navigablemap<e,object> m) {
              this.m = m;
          }
    
          public treeset() {
              this(new treemap<e,object>());
          }
          public boolean add(e e) {
              return m.put(e, present)==null;
          }
      }
    我去,又是这个尿性,基于treemap来实现的
  • 注意:
    1. 首先要正确重写equals方法和hashcode方法,以保证放入set对象的唯一性
    2. 需要实现comparable接口,从而实现有序存储

linkedhashset(不重复、位置有序、非线程安全的集合)

  • 底层实现,源码如下:

      public class linkedhashset<e> extends hashset<e> implements set<e>, cloneable, java.io.serializable {
    
          private static final long serialversionuid = -2851667679971038690l;
    
          public linkedhashset(int initialcapacity, float loadfactor) {
              super(initialcapacity, loadfactor, true);
          }
          public linkedhashset(int initialcapacity) {
              super(initialcapacity, .75f, true);
          }
          public linkedhashset() {
              super(16, .75f, true);
          }
          public linkedhashset(collection<? extends e> c) {
              super(math.max(2*c.size(), 11), .75f, true);
              addall(c);
          }
      }
    都是super,实现了把hashset中预留的构造方法启用了,因而可以实现有序插入(linkedhashmap再谈究竟)
  • 注意:
    1. 首先要正确重写equals方法和hashcode方法,以保证放入set对象的唯一性
    2. 内部实现了有序插入,所以使用时不需要考虑

map

hashmap(无序、线程不安全)

  • jdk1.7数据存储结构(采用数组+链表)

    Java基础篇——集合浅谈
    Java基础篇——集合浅谈

  • jdk1.8数据存储结构(采用数组+链表+红黑树)

    Java基础篇——集合浅谈

    注意:在链表长度大于8后,查询复杂度由o(n)变为o(logn),将链表存储转换成红黑树存储(也就是treemap)

  • 红黑树r-b tree简介(本质其实是2-3-4树):

    Java基础篇——集合浅谈

    二叉树特性:
    (1)左字数上所有的节点的值都小于或等于他的根节点上的值
    (2)右子树上所有节点的值均大于或等于他的根节点的值
    (3)左、右子树也分别为二叉树
    红黑树特点(一种平衡二叉树):
    (1)每个结点要么是红的要么是黑的。
    (2)根结点是黑的。 
    (3)每个叶结点(叶结点即指树尾端nil指针或null结点)都是黑的。 
    (4)如果一个结点是红的,那么它的两个儿子都是黑的。 
    (5)对于任意结点而言,其到叶结点树尾端nil指针的每条路径都包含相同数目的黑结点
    节点操作:
    (1)左旋
    (2)右旋
    (3)变色

treemap(有序、线程不安全)

  • 底层就是红黑二叉树

linkedhashmap(有序、线程不安全)

  • 底层实现,源码如下:

    static class entry<k,v> extends hashmap.node<k,v> {
        //这里维护了一个before和after的entry, 见名思意, 就是每个entry<k,v>都维护它的上一个元素和下一个元素的关系。这也是linkedhashmap有序的关键所在。
        entry<k,v> before, after;
        entry(int hash, k key, v value, node<k,v> next) {
            super(hash, key, value, next);
        }
    }

    linkedhashmap是继承hashmap, 也就是说linkedhashmap的结构也是和hashmap那样(数组+链表)

    注意:linkedhashmap分为插入的顺序排列和访问的顺序排列两种方式,通过accessorder参数来控制

hashtable(线程安全)

  • 底层数据结构同hashmap。线程安全,效率低,没什么卵用,需要使用线程安全的map可以使用concurrenthashmap

list

arraylist(位置有序、可重复、线程不安全)

  • 底层数据结构是数组,查询快

linkedlist(有序、线程不安全)

  • 底层数据结构是双向链表,查询慢,增删快

vector(有序、线程安全)

  • 底层数据结构是数组,查询快,增删慢

并发集合

concurrenthashmap(线程安全)

  • 利用了锁分段的思想提高了并发度,把map分成了n个segment,每个segment相当于hashtable

copyonwritearraylist(线程安全)

  • 读写分离,写时复制出一个新的数组,完成插入、修改或者移除操作后将新数组赋值给array

queue

非阻塞队列

  • priorityqueue :实质上维护了一个有序列表
  • concurrentlinkedqueue :基于链接节点的、线程安全的队列

阻塞队列

  • arrayblockingqueue :一个由数组支持的有界队列。
  • linkedblockingqueue :一个由链接节点支持的可选有界队列。
  • priorityblockingqueue :一个由优先级堆支持的*优先级队列。
  • delayqueue :一个由优先级堆支持的、基于时间的调度队列。
  • synchronousqueue :一个利用 blockingqueue 接口的简单聚集(rendezvous)机制。

总结

  • 本来想详细的总结一下各种集合的使用和底层实现,但发现说来说去还是数据结构的事,你要能把数组、链表、二叉树、红黑树等数据结构弄明白,这些所谓的集合也就是不同的实现而已。
  • 以后有机会还是直接来搞数据结构、算法吧!

个人博客地址:

csdn:
cnblogs:
segmentfault:
github: