注意：虚线对应的是接口，实线对应的是实现类
顶层的接口：Collection 和 Map接口是为了提供方法
Collection接口表示存储的是单个数据组成的集合；
Map接口表示存储的是key-value键值对的集合。
public class CollectionTest {
public static void main(String[] args) {
//ArrayList是Collection的实现类:存储的是单一元素
ArrayList arrayList = new ArrayList();
arrayList.add(23);
arrayList.add(45);
//HashMap是Map接口实现类：key-value键值对
HashMap hashMap = new HashMap();
hashMap.put("k1","v1");
}
}
1：Collection的三个子接口：
List：允许存储重复的元素的集合；
Set:不允许存储重复的元素的集合（去重）；
Queue:主要是用于存储数据，模拟队列（先进先出）模拟栈（先进后出）、优先级队列；可以重复；
2：Map接口：存储的是键值对
SortMap:对于元素进行排序
1：List接口的实现类:
ArrayList：查询速度快，底层基于数组来存储元素，封装一个动态的Object[]数组，是一种顺序存储的集合（插入有序）；
ListedList:增删速度快，线程不安全，底层是一个双向链表实现，元素也是插入有序；
Vector:线程安全。查询增删速度慢，已经被ArrayList替代。
2：Set接口的实现类：
HashSet:底层数据结构是基于HashMap实现的，线程不安全，不保证集合中元素顺序，即不能保证数据和插入顺序一致
linkedSet:底层数据结构是基于linkedHashMap实现,线程不安全，能保证数据和插入顺序一致
TreeSet:基于TreeMap集合实现，线程不安全，数据是有序的（按照属性的特征排序）
3：Map接口的实现类：存储的是键值对
HashMap:底层是一个哈希表结构，线程不安全，允许Key-Value为null，key不能重复（哈希表结构相关）
HashTable:和HashMap类似，底层是哈希表接口，线程安全，Key-Value不能为null
linkedHashMap:是HashMap的子类，可以保证数据插入是有序的
TreeMap:底层是二叉树：红黑树，线程不安全，数据可以基于属性特征排序
ArrayListarrayList = new ArrayList (); arrayList.add(23); arrayList.add(45); ArrayList list = new ArrayList<>(); list.add(12); list.add(15); list.add(17); HashSet hashSet = new HashSet<>(); hashSet.add(55); hashSet.add(78); arrayList.addAll(hashSet); for (Integer i : arrayList) { System.out.print(i + " "); } System.out.println(); System.out.println("------"); // arrayList.clear(); // for (Integer i:arrayList) { // System.out.print(i+" "); // } boolean b = arrayList.contains(55); System.out.println(b); boolean empty = arrayList.isEmpty(); System.out.println(empty); Iterator iterator = arrayList.iterator(); while (iterator.hasNext()) { Integer value = iterator.next(); System.out.print(value+" "); } System.out.println(); System.out.println("-----"); for (Integer n:arrayList ) { System.out.print(n+" "); } System.out.println(); // // boolean remove1 = arrayList.remove(Integer.valueOf(23)); // System.out.print("删除数据1："+ remove1); // System.out.println(); // // Integer remove = arrayList.remove(1); // System.out.print("删除的数据："+ remove); // // System.out.println("-----"); // for (Integer a:arrayList // ) { // System.out.print(a+" "); // // } // System.out.println("-----"); // ArrayList list1 = new ArrayList<>(); list1.add(45); list1.add(2); list1.add(78); list1.add(56); for (Integer n:list1 ) { System.out.print(n+" "); } System.out.println(); System.out.println("----"); // boolean a =arrayList.retainAll(list1); // System.out.println(a); int size = arrayList.size(); System.out.println(size); for (Integer n:arrayList ) { System.out.print(n+" "); }
练习：
ArrayList a = new ArrayList ();
a.add(1);
a.add(2);
a.add(3);
ArrayList b = new ArrayList ();
b.add(3);
b.add(4);
b.add(5);
//并集
a.addAll(b);
//交集
a.retainAll(b);
//差集
a.removeAll(b);
ArrayList工作原理及实现
特点、需要通过源码底层实现查看实现逻辑
①ArrayList集合的使用及特点：
**特点：**1、元素存放和插入顺序一致
2、数据是可以重复的
3、可以存储null
4、底层数据结构是数组
5、可以动态扩容的，默认容量是10
6、扩容是按照原大小的1.5倍进行扩容
构造函数：
//无参构造
ArrayList list = new ArrayList();
//通过指定集合容量大小来实例化
ArrayList list1 = new ArrayList<>(100);
//通过Collection集合实例来实例化一个集合
ArrayList list2 = new ArrayList<>(list);
通过JDK源码来研究ArrayList的实现
1.关注继承关系
2.属性和默认值
3.构造函数
4.扩容机制、扩容时机
5.底层数据结构（数组、链表、队列、栈、哈希表…）
6.常见方法实现原理（add,remove,get…）
ArrayList:
继承关系：
public class ArrayListextends AbstractList implements List , RandomAccess, Cloneable, java.io.Serializable
继承自AbstractList，AbstractList是一个抽象类，是实现了List接口，他是一个数组队列，提供了相关的添加、删除、修改、遍历等基本功能实现，方法子类对方法复用，如果子类有特殊功能可以重写父类的方法；
ArrayList实现了List接口，list接口继承自collection接口，在collection接口提供的方法基础上，有一些新的方法提供，比如get、set、add等特有的方法；
ArrayList实现了RandomAccess接口，即提供了随机访问功能，为list提供快速访问的功能；
ArrayList实现了Cloneable接口，即包含了函数clone（），能被克隆；
ArrayList实现了Serializable接口，意味着ArrayList支持序列化去传输（IO).
属性和默认值：
//默认初始容量是10
private static final int DEFAULT_CAPACITY = 10;
//空数组实例
private static final Object[] EMPTY_ELEMENTDATA = {};
//存储数据使用的是数组，数组存储的数据类型是Object
private transient Object[] elementData;
//用来记录存放数据的个数
private int size;
ArrayList底层存储元素是使用数组
数组 elementData.length: 表示当前数组容量，最大存储的数据个数
*size:*实际存放的数据个数
构造函数：
//有参构造函数：通过指定初始容量initialCapacity来实例化ArrayList
public ArrayList(int initialCapacity) {
super();
//参数校验
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+initialCapacity);
//实例化一个大小为initialCapacity数组并将数组赋值给elementData
this.elementData = new Object[initialCapacity];
}
//无参构造函数
public ArrayList() {
super();
//给定空的数组
this.elementData = EMPTY_ELEMENTDATA;
//将默认值的赋值在add中完成
}
//通过集合实例来实例化ArrayList
public ArrayList(Collection c) {
//将集合转化为数组，直接赋值给 elementData
elementData = c.toArray();
//将集合中已有元素的大小赋值给size
size = elementData.length;
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)
//完成数据拷贝
elementData = Arrays.copyOf(elementData, size, Object[].class);
}
常见方法源码解析：
add:添加元素
public boolean add(E e) {
//考虑扩容
ensureCapacityInternal(size + 1); // Increments modCount!!
//将新增元素插入elementData数组尾部，并对size+1
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
//当数组为空时，获取当前容量值
if (elementData == EMPTY_ELEMENTDATA) {
//在添加第一个元素时，当无参构造的实例时，第一次会进入该if方法
//在未指定集合容量时，默认情况下数组初始化大小为10
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
//数据空间不足，考虑扩容
if (minCapacity > elementData.length )
grow(minCapacity);
}
//扩容点
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
//扩容大小 oldCapacity >> 1 => oldCapacity/2 即1.5倍
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);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
modCount是版本控制器，也是ArrayList中的属性（继承自AbstractList中的属性），和业务无关，仅仅是做版本控制，在集合进行变更（增删改）时会自增1
扩容机制和扩容时机：当要插入数据的个数大于数组容量，需要扩容，按照原数组大小的1.5倍扩容，需要将原集合数据拷贝到新数组中
add过程：
1、如果存储数组为空，获取默认的大小值是10
2、如果需要大小超过数组大小、考虑扩容，按照原数组大小的1.5倍扩容
3、通过创建新数组，将元素组大小拷贝到新数组中
4、将新增元素插入最后的size位置并对size进行加1操作
get：获取元素
public E get(int index) {
//检查查询位置的合法性 index < size
rangeCheck(index);
return elementData(index);
}
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
E elementData(int index) {
return (E) elementData[index];
}
remove：删除元素
public boolean remove(Object o) {
//删除操作判断区分是否为null值，如果为null，判断相等使用== 如果不为null，判断相等用equals
if (o == null) {
//元素为空时
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
fastRemove(index);
return true;
}
} else {
//不为空
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
}
//将index后续的数据前移一位
private void fastRemove(int index) {
modCount++;
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
//Arrays.copyof()拷贝和System.arraycopy拷贝
//将最后一个位置置为null，并将size-1
elementData[--size] = null; // clear to let GC do its work
}
Arrays.copyof()拷贝和System.arraycopy拷贝：
1、使用 Arrays.copyOf() 方法对数组进行拷贝时，不需要目标数组的信息，只需要源数组和拷贝数据的长度信息，返回的新数组的长度也就是拷贝数据的长度；
2、使用 System.arraycopy() 方法对数组进行拷贝时，需要目标数组的信息，同时需要原始数组、原始数组的拷贝位置，目标数组的拷贝位置和拷贝长度信息；
3、Arrays.copyOf() 底层也有调用 System.arraycopy() 。
