Java基础篇——集合浅谈

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

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数据存储结构（采用数组+链表）

  
  

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

  

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

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

  

  二叉树特性：
  （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: