目录
1、Java集合概况
从下图可以看出: Iterable是Collection的父接口，除实现Map集合相关的类之外，其他类都有实现Collection
1.1、Iterable
1.1.1、Iterable源码分析
1、Iterable是一个接口，接口里有一个方法 Iterator<T> iterator();可以返回一个迭代器对象
java定义了一个Iterator接口，里面定义了对迭代器操作的方法，下面图片是各个List实现类的对迭代器方法的重写
1、ArrayList的迭代器的实现类: Itr
2、Vector的迭代器实现类: Itr
3、LinkedList的迭代器实现类: ListItr。它先调用抽象父类AbstractSequentialList的iterator()方法，该方法返回一个listIterator()方法的调用，listIterator()该方法最终返回一个new ListItr(index)对象。
1.1.2、Iterator接口常用方法
1、Iterator<T> iterator();//返回一个迭代器对象
2、hasNext(): //判断该集合对象中的元素是否为空
3、next(): //如果集合对象中的元素不为空，取出某下标的元素，并把指针向下移动一个下标。
4、remove(): //删除指定集合对象中的元素
1.2、Collection（单列集合）
1.2.1、Collection源码分析
1.因为Collection接口继承于Iterable父接口，故Collection下的所有实现类都可以通过重写Iterable的iterator()方法来动态调用自身的该iterator()方法，得到一个不一样的迭代器
1.2.2、Collection常用方法
| 方法名 | 方法含义 |
|---|---|
| int size() | 获取集合对象元素的个数 |
| boolean isEmpty(); | 判断集合是否为空 |
| boolean contains(Object o) | 判断对象o是否存在集合中 |
| Iterator |
获取一个迭代器对象 |
| Object[] toArray() | 集合对象转换成数组对象 |
| boolean add(E e) | 往集合里添加单一元素 |
| boolean remove(Object o) | 删除集合里指定元素 |
| boolean containsAll(Collection<?> c) | 判断当前集合里是否包含集合c中的所有元素 |
| boolean addAll(Collection<? extends E> c) | 往集合里添加集合c的所有元素 |
| boolean removeAll(Collection<?> c) | 删除在集合c中的所有元素 |
| boolean retainAll(Collection<?> c) | 判断集合中是否存在集合c的元素 |
| void clear() | 清空所有元素 |
1.3、List、Set、Map的底层数据结构
1.3.1、List（单列集合）
1、List强调元素存取有序，元素可以重复，可以存多个null
1、ArrayList
1、ArrayList:
1、 源码：
1、private static final int DEFAULT_CAPACITY = 10;
解释: 当使用无参的ArrayList(){}构造器时，默认该集合的元素容量为10
2、private static final Object[] EMPTY_ELEMENTDATA = {};
解释: 用于默认大小的空实例的共享空数组实例
3、transient Object[] elementData;
解释:1、transient该修饰用于使Object[]数组不参与序列化操作，保证该数组中元素的安全
2、elementData是一个用于存储ArrayList集合元素的Object类型的动态数组
2、扩容源码:
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);
}
解释：1、当时使用无参构造器时，容量默认为10，下次扩容就是10+10/2=15
2、当使用有参构造器时，下次扩容量就是传入的容量*1.5倍
2、LinkedList
1、LinkedList源码:
1、transient int size = 0;
解释：表示LinkedList的结点元素默认为0个元素
2、transient Node<E> first;
解释：这是LinkedList的头结点
3、transient Node<E> last;
解释：这是LinkedList的尾结点
4、这是LinkedList结点的构造器:
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
解释：该结点的构造器由元素item、前驱prev、后继next组成，前驱prev指向前一个结点的后继，后继next指向后一个结点的前驱，item元素默认为o个
5、LinkedList的扩容:
解释：因为它用的是双向链表，没有初始值，也不需要扩容
6、头结点插入：
private void linkFirst(E e) {
final Node<E> f = first;
final Node<E> newNode = new Node<>(null, e, f);
first = newNode;
if (f == null)
last = newNode;
else
f.prev = newNode;
size++;
modCount++;
}
7、尾结点插入：
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
3、Vector
1、Vector源码:
1、protected Object[] elementData;
解释：存放元素的动态数组，跟ArrayList一样
2、protected int elementCount;
解释：elementCount为元素计数，等同于数组里元素存放的实际个数
3、protected int capacityIncrement;
public Vector() {
this(10);
}
解释：它的容量直接在无参构造器里默认为10;
4、Vector的扩容机制：
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
capacityIncrement : oldCapacity);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
elementData = Arrays.copyOf(elementData, newCapacity);
解释：1、如果是调用无参构造，Vector的容量默认初始值为10，下次扩容为10*2
2、如果调用有参构造，每次扩容为之前容量的2倍
1.3.2、Set（单列集合）
1、它具有元素唯一性(前提必须重写hashcode和equals方法)，不可重复，最多只能有一个null
2、它是无序的，即你添加元素的顺序和存入容器后元素的位置顺序是不一致的
3、继承了Collection接口，拥有所有Collection方法，也可以使用迭代器来遍历元素，也可以用增强for循环遍历元素
4、它没有索引，即不能用索引方式获取元素
1.3.3、Map（双列集合）
1.4、为什么要有集合？
答：当我们想用一个容器去保存同类型数据时，马上会想到用Arrays数组容器，随着后续存储的数据类型多样化后，Arrays数组弊端明显。 不支持存储不同类型的数据和对象，容量不能动态扩充等问题，这时集合就应运而生，并解决了这些问题！
1.5、项目中如何去选用集合？
1、如果你想使用双列键值对的形式去存储和读数据时，可以使用Map接口下的集合; 需要排序的话用TreeMap; 不需要排序的话用HashMap，效率高些; 需要线程安全的话使用JUC并发包下的ConcurrentHashMap。
2、如果只是存储单个值的话，可用Collection接口下的集合; 需要保证数据唯一性，可用Set集合下HashSet或TreeSet; 不需要的话用List接口下的实现类ArrayList和LinkedList都行，改查操作多就用ArrayList，增删操作多就用LinkedList。
2、List
2.1、ArrayList
2.1.1、ArrayList源码
ArrayList属性由以上字段组成
2.1.2、ArrayList的扩容机制
1、第一步先从构造器说起：ArrayList有三种构造器进行初始化：
1、无参构造器
//默认初始化容量值10
rivate static final int DEFAULT_CAPACITY = 10;
private static final Object[] EMPTY_ELEMENTDATA = {};
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
transient Object[] elementData;
//默认构造一个空数组，这里还没有加容量，默认容量10会在调用add()方法加第一个元素时进行扩容
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
2、有参构造器
/**
*1、对传入参数进行防护判断，大于0，创建一个容量为传参值的Object数组
*2、=0，返回一个空容量数组； 小于0，报错
*/
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
3、有参构造器
**
*构造包含指定collection元素的列表，这些元素利用该集合的迭代器按顺序返回
*如果指定的集合为null，throws NullPointerException。
*/
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;
}
}
2、add ( ) 方法
1、add（）；
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
//索引通过不断自增，移动数组下标来进行赋值
elementData[size++] = e;
return true;
}
# ensureCapacityInternal方法
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
# 主要是判断是否要调用扩容方法
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
//这里得到minCapacity=10，此时 elementData.length=0，并与当前存储元素的数组长度进行比较，调用grow(minCapacity=10)。
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
# calculateCapacity方法
private static int calculateCapacity(Object[] elementData, int minCapacity) {
//这里其实是判断一下你之前是不是用的无参构造器,是的话，我就给你一个DEFAULT_CAPACITY=10的容量，这里minCapacity=10，并传给ensureExplicitCapacity方法
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
//不是add第一个元素的话就返回你原有的数组容量
return minCapacity;
}
//扩容方法grow，获取newCapacity=10；
private void grow(int minCapacity) {
// 此时oldCapacity=0，下一次扩容直接在这里扩容，通过位运算，左移a位为2的a次方，右移a位为n/2的a次方，效率非常高
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
//这里把10赋值给了新容量newCapacity，添加下一个元素就不会走这里
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);
}
上述方法调用顺序:add ---> ensureCapacityInternal ---> calculateCapacity ---> grow ---> ensureExplicitCapacity ---> ensureCapacityInternal ---> add
2.1.3、ArrayList新增常用方法
| 新增方法名 | 方法含义 |
|---|---|
| E get(int index) | 通过index获取元素 |
| E set(int index, E element) | 用element去替换index对应的元素 |
| int indexOf(Object o) | 获取0对象的下标，如果不存在，返回-1， |
| int lastIndexOf(Object o) | 获取0对象的下标，如果不存在，返回-1， |
2.1.4、ArrayList特点
1、ArrayList底层是由Oject类型动态数组组成，故可以通过下标获取对应的元素，元素顺序存取，可重复。
2、它的查和改操作效率相对较高。因为可以通过元素之间的间隔距离*间隔个数直接定位到该元素,时间复杂度近乎O(1); 而它的增加和删除效率相对较低，默认是增加到尾部，增加和删除操作需要把删除元素后面的元素都向前挪，时间复杂度近乎O(n)
3、线程不安全。底层的方法没有被synchronized修饰，线程不同步。
4、内存利用率相对较低。因为扩容机制，它的尾部总会占用一部分的空间无法利用
2.2、LinkedList
2.2.1、LinkedList源码
2.2.3、LinkedList常用方法
| 方法名 | 方法含义 |
|---|---|
| 增 | |
| add(E e)：add(int index, E e) | 1、增加元素 2、在指定下标插入元素 |
| addAll(Collection) | 1、增加元素，可以是集合 |
| addFirst(E e) | 在链表头部增加元素 |
| addLast(E e) | 在链表尾部增加元素 |
| 删 | |
| remove() , remove(E e) | 1、删除第一个元素，2、删除指定元素 |
| removeFirst( E e) | 删除头结点，获取元素并删除 |
| removeLast( E e) | 删除尾结点，获取元素并删除 |
| pollFirst() | 删除头结点 |
| pollLast() | 删除尾结点 |
| clear() | 清空 |
| 改 | |
| set(int index, E element) | 修改指定位置的元素 |
| 查 | |
| get(int index) | 获取指定下标的元素 |
| getFirst() | 获取第一个元素 |
| getLast() | 获取最后一个元素 |
2.2.4、LinkedList特点
1、LinkedList底层是用双向链表存储数据，元素是顺序存取，可以重复
2、增加和删除操作效率相对较高。因为双向链表，添加元素和删除元素无需挪动剩余元素，插入新元素和删除元素的时间复杂度近乎O(1)，查找和修改时间复杂度近乎O(n)
3、线程不安全。底层的方法没有被synchronized修饰,线程不同步。
4、内存占用相对较大。每个节点都由前驱prev+元素+后继next组成,prev需要存储前一结点的后继信息，next需要存储后一结点的前驱信息，内存消耗较大。
2.3、Vector
2.3.1、Vector源码
容量初始值为10
2.3.2、Vector的扩容机制
1、扩容机制跟ArrayList类似，不太的是Vector每次扩容量为原容量的两倍
2.3.3、Vector常用方法
| 方法名 | 方法含义 |
|---|---|
| insertElementAt(E obj, int index) | 将元素插入指定位置 |
| removeElementAt(int index) | 删除指定位置元素 |
| addElement(E obj) | 添加元素 |
| indexOf(Object o) | 获取元素的下标 |
| firstElement() | 获取第一个元素 |
| lastElement() | 获取最后一个元素 |
| setElementAt(E obj, int index) | 替换指定位置的元素 |
2.3.4、Vector特点
1、线程安全。多数方法使用synchronized修饰，现场同步。
2、底层使用动态数组，特性跟ArrayList类似，效率相对较低，现在不建议使用了
3、Set
3.1、HashSet
3.1.1、HashSet源码
1、HashSet的构造器:
public HashSet() {
map = new HashMap<>();
}
# 他的底层其实是HashMap对象