Collection

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

boolean	add(E e)Ensures that this collection contains the specified element (optional operation).
boolean	addAll(Collection<? extends E> c)Adds all of the elements in the specified collection to this collection (optional operation).
void	clear()Removes all of the elements from this collection (optional operation).
boolean	contains(Object o)Returns true if this collection contains the specified element.
boolean	containsAll(Collection<?> c)Returns true if this collection contains all of the elements in the specified collection.
boolean	equals(Object o)Compares the specified object with this collection for equality.
int	hashCode()Returns the hash code value for this collection.
boolean	isEmpty()Returns true if this collection contains no elements.
Iterator<E>	iterator()Returns an iterator over the elements in this collection.
default Stream<E>	parallelStream()Returns a possibly parallel Stream with this collection as its source.
boolean	remove(Object o)Removes a single instance of the specified element from this collection, if it is present (optional operation).
boolean	removeAll(Collection<?> c)Removes all of this collection's elements that are also contained in the specified collection (optional operation).
default boolean	removeIf(Predicate<? super E> filter)Removes all of the elements of this collection that satisfy the given predicate.
boolean	retainAll(Collection<?> c)Retains only the elements in this collection that are contained in the specified collection (optional operation).
int	size()Returns the number of elements in this collection.
default Spliterator<E>	spliterator()Creates a Spliterator over the elements in this collection.
default Stream<E>	stream()Returns a sequential Stream with this collection as its source.
Object[]	toArray()Returns an array containing all of the elements in this collection.
<T> T[]	toArray(T[] a)Returns an array containing all of the elements in this collection; the runtime type of the returned array is that of the specified array.

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

來源：简书

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