Collection

• List,Queue,Set都是继承Collection接口；
  • Set：Set不允许包括重复元素，其他的和collection相同；
  • List：代表一个元素有序、可重复的集合，集合中每个元素都有其对应的顺序索引。List集合允许使用重复元素，可以通过索引来访问指定位置的集合元素 。
  • List集合：代表一个元素有序、可重复的集合，集合中每个元素都有其对应的顺序索引。List集合允许使用重复元素，可以通过索引来访问指定位置的集合元素 。队列的头部是在队列中存放时间最长的元素，队列的尾部是保存在队列中存放时间最短的元素。新元素插入（offer）到队列的尾部，访问元素（poll）操作会返回队列头部的元素。通常，队列不允许随机访问队列中的元素。
• Collection定义了多种方法供子类调用。
  • 添加:add,addAll
  • 删除:clear(),remove(),removeAll()

List

wiki

• Interface List<E>
• 由浅入深理解java集合(三)——集合 List
• https://juejin.im/post/5ab548f75188257ddb0f8fa2

ArrayList

学习要点

• 列表的增，删，改，查的各种方法；
• 列表遍历，扩容的机制；

ArrayList的结构图

• ArrayList 继承了AbstractList，实现了List。它是一个数组队列，提供了相关的添加、删除、修改、遍历等功能。

• ArrayList 实现了RandmoAccess接口，即提供了随机访问功能。RandmoAccess是java中用来被List实现，为List提供快速访问功能的。

• 在ArrayList中，我们即可以通过元素的序号快速获取元素对象；这就是快速随机访问。稍后，我们会比较List的“快速随机访问”和“通过Iterator迭代器访问”的效率。

• ArrayList 实现了Cloneable接口，即覆盖了函数clone()，能被克隆。

• ArrayList 实现java.io.Serializable接口，这意味着ArrayList支持序列化，能通过序列化去传输。

• 和Vector不同，ArrayList中的操作不是线程安全的！所以，建议在单线程中才使用ArrayList，而在多线程中可以选择Vector或者CopyOnWriteArrayList。

ArrayList的定义

Java ArrayList的自动扩容机制

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
        {

        }

what：ArrayList的本质-ArrayList的构造函数

• ArrayList是用数组实现，元素放在elementData数组中；

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
transient Object[] elementData;

public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; // 返回一个空数组的引用
}

public ArrayList(int initialCapacity) { //如果指定List长度，返回对应长度的Object数组
    if (initialCapacity > 0) {
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    }
}

public ArrayList(Collection<? extends E> c) { //使用其他的集合作为参数
    elementData = c.toArray();
    if ((size = elementData.length) != 0) {
        // c.toArray might (incorrectly) not return Object[] (see 6260652)
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
        // replace with empty array.
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

ArrayList扩容机制：ensureCapacityInternal()

private void ensureCapacityInternal(int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }

    ensureExplicitCapacity(minCapacity);
}

如果数组为空数组，则将数组扩充为DEFAULT_CAPACITY = 10大小的数组

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

在扩充数组的时候，modCound会自动加1；

private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    elementData = Arrays.copyOf(elementData, newCapacity);
}

可以看出，新的容量会是max[1.5*oldCapacity, minCapacity],容量最大为Integer.MAX_VALUE；

总结：扩容时modCount自动加1，新的容量是max[1.5*oldCapacity, minCapacity]，容量的最大值为Integer.MAX_VALUE

遍历集合的方式

• 通过Iterator遍历

  public static void main(String[] args)
  {
      List<String> list = new ArrayList<>();
      list.add("uranus");
      list.add("leon");
      list.add("test");
  
      Iterator iter = list.iterator();
  
      while(iter.hasNext())
      {
          System.out.println(iter.next());
      }
  }
  

• 通过foreach方式

  public static void main(String[] args)
  {
      List<String> list = new ArrayList<>();
      list.add("uranus");
      list.add("leon");
      list.add("test");
  
      for (String str : list)
      {
          System.out.println(str);
      }
  }
  

• 通过索引方式

  public static void main(String[] args)
  {
      List<String> list = new ArrayList<>();
      list.add("uranus");
      list.add("leon");
      list.add("test");
  
      for (int i = 0; i < list.size(); i++)
      {
          System.out.println(list.get(i));
      }
  }
  

foreach遍历本质和Iterator遍历是一样的，通过编译后的代码可以看出

// foreach 方式编译结果
public static void main(String args[])
{
    List list = new ArrayList();
    list.add("uranus");
    list.add("leon");
    list.add("test");
    String str;
    for(Iterator iterator = list.iterator(); iterator.hasNext(); System.out.println(str))
        str = (String)iterator.next();
}

拷贝集合：浅拷贝和深拷贝

• clone()方法的误区

List<String> list1 = new ArrayList<>();
ArrayList list2 = (ArrayList) list.clone(); //编译报错

ArrayList<String> list3 = new ArrayList<>();
ArrayList list4 = (ArrayList) list.clone(); //编译不会报错

list1指向的是ArrayList类型的实例，为什么调用clone的时候不是调用ArrayList中的clone方法，而是在List中寻找clone方法，导致报错？

Error:(11, 43) java: 找不到符号
  符号:   方法 clone()
  位置: 类型为java.util.List<java.lang.String>的变量 list

• 浅拷贝

  public class ListBasic {
      public static void main(String[] args)
      {
          List<Student> list = new ArrayList<>();
  
          list.add(new Student("uranus", 001));
          list.add(new Student("test", 002));
          list.add(new Student("uranus", 001));
  
          ArrayList<Student> list2 = (ArrayList<Student>) ((ArrayList<Student>) list).clone();
  
          System.out.println(list.get(0).getName());
          list2.get(0).setName("uranusleon");
          System.out.println(list.get(0).getName()); // 输出 uranusleon
      }
  }
  
  class Student
  {
      private String name;
      private int stuNo;
  
      public Student(String name, int stuNo)
      {
          this.name = name;
          this.stuNo = stuNo;
      }
  
      public void setName(String name)
      {
          this.name = name;
      }
  
      public String getName() {
          return this.name;
      }
  }
  

  ArrayList本质上是一个数组在维护，数组的元素都是引用。list2拷贝list后数组中的元素和list中的相同，所以对list2数组中引用的对象的修改会引起list的变化。比如将list2中第一个元素对应的对象的名字改为"uranusleon"，list.get(0).getName()会输出"uranusleon".

• 深拷贝

ArrayList中的Iterator

1. ArrayList是通过内部私有类Itr实现Iterator

2. 定义的类变量

   int cursor;       // index of next element to return
   int lastRet = -1; // index of last element returned; -1 if no suc
   

3. Itr.hasNext()判断列表是否有下一个元素

   public boolean hasNext() {
       return cursor != size; //比较cursor和size，因为数组是从0开始计数的，如果相同则说明列表没有下一个元素；
   }
   

4. Itr.next()返回下一个元素

   public E next() {
       checkForComodification();
       int i = cursor;
       if (i >= size)
           throw new NoSuchElementException();
       Object[] elementData = ArrayList.this.elementData;
       if (i >= elementData.length)
           throw new ConcurrentModificationException();
       cursor = i + 1; //
       return (E) elementData[lastRet = i]; //返回cursor对应的元素，lastRet加一；
   }
   

5. Itr.remove()

   public void remove() {
       if (lastRet < 0)
           throw new IllegalStateException();
       checkForComodification();
   
       try {
           ArrayList.this.remove(lastRet);
           cursor = lastRet;
           lastRet = -1;
           expectedModCount = modCount;
       } catch (IndexOutOfBoundsException ex) {
           throw new ConcurrentModificationException();
       }
   }
   

   ArrayList可以利用Itr.remove()在遍历的时候将元素全部删除。

   public static void main(String[] args)
   {
       List<Student> list = new ArrayList<>();
   
       list.add(new Student("uranus", 001));
       list.add(new Student("test", 002));
       list.add(new Student("uranus", 001));
   
       Iterator iter = list.iterator();
       while(iter.hasNext())
       {
           iter.next();
           iter.remove();
       }
   }
   

Map

Map集合与Set集合、List集合的关系

1.与Set集合的关系
如果 把Map里的所有key放在一起看，它们就组成了一个Set集合（所有的key没有顺序，key与key之间不能重复），实际上Map确实包含了一个keySet()方法，用户返回Map里所有key组成的Set集合。
2.与List集合的关系
如果把Map里的所有value放在一起来看，它们又非常类似于一个List：元素与元素之间可以重复，每个元素可以根据索引来查找，只是Map中索引不再使用整数值，而是以另外一个对象作为索引。

作者：Ruheng

链接：https://www.jianshu.com/p/589d58033841

來源：简书

简书著作权归作者所有，任何形式的转载都请联系作者获得授权并注明出处。