image.png

集合分类

image.png

Collection接口（单列集合）

  • List接口： 特性 继承collection集合，排列有序且可重复

    • LinkedList 接口实现类：链表实现，适用于插入删除型链表，线程不安全
    • ArrayList接口实现类：数组实现，适用于随机访问型链表，线程不安全
    • Vector接口实现类：数组实现，线程安全。

  • Set接口： 特性 继承collection集合，排列无序且不可重复

    • HashSet接口实现类：适用hash表（数组）存储元素。

      • LinkedHashSet 继承HashSet，实现Set,链表维护元素的插入次序。

    • TreeSet接口实现类：二叉树实现，元素有序。

Map接口（双列集合）

  • HashTable 接口实现类，线程安全。

  • HashMap 接口实现类，线程不安全。

    • LinkedHashMap 双向链表和哈希实现类。
    • WeakHashMap

  • TreeMap 红黑树对所有的key进行排序。

  • IdentifyHashMap

总结

Map和List、Set的区别

  • Map是接口，而List和Set是Collection的子接口
  • Map是双列集合，而List和set是单列集合

List和set的区别

  • List 是排列有序且可重复得集合，而且可以通过索引查询集合中的元素。
  • Set 排列无序且不可重复，没有索引，当然，Set中的实现类LinkedHshSet是通过链表维护着插入顺序的。

List集合

有序列表，允许存放重复元素；其实现类由三个：

  • ArrayList：数组实现，查询快，增删慢，轻量级；(线程不安全)
  • LinkedList：双向循环链表实现，增删快，查询慢 (线程不安全)
  • Vector：数组实现，重量级 (线程安全、使用少)

List的四种遍历方式

 public class ListTest {
     public static void main(String[] args) {
         List<Integer> list=new ArrayList<>();
         list.add(1);
         list.add(2);
         list.add(3);
         //方法一，使用for循环（这种方法Set集合不适用）
         for (int i = 0; i <list.size() ; i++) {
             System.out.println(list.get(i));
         }
 
         //方法二：增强for循环
         for(Integer elem:list){
             System.out.println(elem);
         }
 
         //方法三：迭代器实现遍历（第一种和第二种的底层也是使用迭代器实现
         Iterator<Integer> integerIterator=list.iterator();
         while (integerIterator.hasNext()){
             Integer elem=integerIterator.next();
             System.out.println(elem);
         }
         //方法四：Lambda表达式+流式编程
         list.forEach((elem)->System.out.println(elem));
         //使用方法引用输出
         list.forEach(System.out::println);
     }
 }

ArrayList自动扩充机制

源码：

 private void add(E e, Object[] elementData, int s) {
     // 判断元素个数是否等于当前容量
     if (s == elementData.length)
         elementData = grow();
     elementData[s] = e;
     size = s + 1;
 }
 private Object[] grow() {
     return grow(size + 1);
 }
 
 private Object[] grow(int minCapacity) {
     // 获取老容量，也就是当前容量
     int oldCapacity = elementData.length;
     // 如果当前容量大于0 或者 数组不是DEFAULTCAPACITY_EMPTY_ELEMENTDATA
     if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
         int newCapacity = ArraysSupport.newLength(oldCapacity,
                 minCapacity - oldCapacity, /* minimum growth */
                 oldCapacity >> 1           /* preferred growth */);
         return elementData = Arrays.copyOf(elementData, newCapacity);
     // 如果 数组是DEFAULTCAPACITY_EMPTY_ELEMENTDATA（容量等于0的话，只剩这一种情况了）
     } else {
         return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];
     }
 }

扩容可分为两种情况：

第一种情况，当ArrayList的容量为0时，此时添加元素的话，需要扩容，三种构造方法创建的ArrayList在扩容时略有不同：

1.无参构造，创建ArrayList后容量为0，添加第一个元素后，容量变为10，此后若需要扩容，则正常扩容。

2.传容量构造，当参数为0时，创建ArrayList后容量为0，添加第一个元素后，容量为1，此时ArrayList是满的，下次添加元素时需正常扩容。

3.传列表构造，当列表为空时，创建ArrayList后容量为0，添加第一个元素后，容量为1，此时ArrayList是满的，下次添加元素时需正常扩容。

第二种情况，当ArrayList的容量大于0，并且ArrayList是满的时，此时添加元素的话，进行正常扩容，每次扩容到原来的1.5倍。

ArrayList的线程安全解决方案

  1. 用victor代替；List list = new Vector<>();

  2. 用Colections：List list = Collections.synchronizedList(new ArrayList);

  3. List list = CopyOnWriteArrayList<>();

LinkedList

采用双向循环链表实现，可以用来实现stack，queue，双向队列，但是哟实现的时候需要遵循实现结构的特性，比如实现栈的时候不能提供不是栈顶的元素出栈的方法，实现对列的时候需要遵循先进先出原则。

vector

和ArrayList类似，但是其实重量级组件，同时也是线程安全的，适用于高并发的场景。

List常用方法

  • void add(int index, Object element) ：添加对象element到位置index上

  • boolean addAll(int index, Collection collection) ：在index位置后添加容器collection中所有的元素

  • Object get(int index) ：取出下标为index的位置的元素

  • int indexOf(Object element) ：查找对象element 在List中第一次出现的位置

  • int lastIndexOf(Object element) ：查找对象element 在List中最后出现的位置

  • Object remove(int index) ：删除index位置上的元素

  • ListIterator listIterator(int startIndex) ：返回一个ListIterator 跌代器，开始位置为startIndex

  • List subList(int fromIndex, int toIndex) ：返回一个子列表List ,元素存放为从 fromIndex 到toIndex之前的一个元素