JavaCore学习-集合-Collection

Java集合分单列集合和双列集合，单列集合的顶层接口是Collection，双列集合的顶层接口是Map

单列集合

1. ArrayList
   • 实现List接口，顺序容器，即元素存放的数据与放进去的顺序相同，允许放入null元素，底层基于数组实现，默认初始容量为10，jdk1.8调用add()时进行初始化容量；扩容则调用grow()；存储的元素时有序的，有索引的，为访问元素提供了方便
   • 在多线程情况下使用时线程不安全的
   • 添加和删除元素时需要操作下标，所以ArrayList的插入和删除操作效率低，查找效率高
   • Github代码演示-线程不安全
2. LinkedList

   • 链表介绍
     链表是一种物理存储单元上非连续，非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列节点(链表中每一个元素称为节点)组成，节点可以在运行时动态生成。每个节点包括两个部分：一是存储数据元素的数据域、另一个是存储下一个节点的指针域。
     双向链表是链表的一种，由节点组成，每个数据节点中都有两个指针，分别指向上一个和下一个节点。

     // 插入元素到尾部
     void linkLast(E e) {
         final Node<E> l = last;
         // new Node = l(上一个节点), e(新添加的元素),null(下一个节点)
         final Node<E> newNode = new Node<>(l, e, null);
         // 设置新节点是最后一个节点
         last = newNode;
         // 判断链表是否为空，如果为空那么设置头元素为当前元素
         if (l == null)
             first = newNode;
         else
             // 设置原尾部节点的下一个节点为当前节点
             l.next = newNode;
         size++;
         modCount++;
     }
     

     // 按坐标查找一个元素
     Node<E> node(int index) {
         // 判断查找的元素在前半段或后半段
         if (index < (size >> 1)) {
             // 结果节点
             Node<E> x = first;
             // 一直获取下一个节点一直获取到指定索引
             for (int i = 0; i < index; i++)
                 x = x.next;
             return x;
         } else {
             Node<E> x = last;
             for (int i = size - 1; i > index; i--)
                 x = x.prev;
             return x;
         }
     }
     

   • 实现了List接口允许有null元素

   • 在多线程使用下是不安全的。

   • LinkedList的查询效率相比较是效率低的

3. Vector
   • 内部实现等于ArrayList
   • 线程安全，使用synchronized实现。默认扩容方式为原来的2倍
4. HashSet
   • 实现了Set接口，不允许出现重复元素，不保证集合中元素的顺序
   • 允许包含值为null的元素，但最多只能一个
5. TreeSet
   • 实现了Set接口，可以实现排序等功能，内部比较器
   • TreeSet内部通过Comparator接口中的compare() 比较，默认是升序。外部比较器：实现Comparable接口，重写compareTo()进行排序
   • TreeSet是基于TreeMap实现的

Set和List的区别

1. Set接口实例存储的是无序的，不重复的数据。List接口实例存储的是有序的，可以重复的数据。
2. Set检索效率低下，删除和插入效率高，插入和删除不会引起元素位置改变
3. List和数组类似，可以动态增长，根据实际存储的数据的长度自动增长list的长度，查找元素效率高，插入删除效率低，因为会引起其他元素位置改变