JAVA集合学习和源码分析

源码分析"/>

JAVA集合学习和源码分析

一、结构

List和Set继承了Collection接口，Collection继承了Iterable

Object类是所有类的根类，包括集合类，集合类中的元素通常是对象，继承了Object类中的一些基本方法，例如toString()、equals()、hashCode()。

Collection的增强for底层就是简化版本的迭代器遍历，可以DEBUG看到过程。

对集合的遍历：

二、List

1、ArrayList

• 线程不安全

• 有序（添加和取出顺序一致），可重复，可以添加多个null

• 默认大小是10，扩容是1.5倍

• 每个元素都有对应的顺序索引，即支持索引。get()体现。

常用方法：

• add()/addAll()

• set()

• get()

• remove()

• size()

• isEmpty()

• indexOf()

• contains()

• replaceAll()

• subList()

底层：

• ArrayList维护一个Object类型的数组elementData，就是一个空数组

• 当创建ArrayList对象时，如果使用的是无参构造器，初始容量是0，第一次添加扩容到10，如果再扩容是1.5倍

• 如果是指定大小的构造器，初始是指定大小，再次扩容是1.5倍

transient避免序列化

（1）无参构造

确认最小容量，赋值为10

modCount记录集合被修改的次数，此时minCapacity是10，但是elementData是空，就需要扩容

向右移动一位，就是除以2，比如初始化是个空数组，那么在newCapacity的时候还是0，所以第一次扩容不是直接扩，是在第一个if才扩容赋值为10，copyOf后都是null

（2）有参构造

同上

2、Vector

• 线程安全的，操作方法带有synchronized

• 默认10，扩容是2倍

底层：

（1）扩容

确定是否需要扩容

int类型初始化是0，所以newCapacity是两倍

（2）克隆

实现了Cloneable接口

调用 Object 类的 clone 方法，创建一个浅拷贝，对于数组元素，使用 Arrays.copyOf 方法进行深拷贝，重置副本的修改次数

3、LinkedList

• 线程不安全

• 双向链表和双端队列

• 添加元素可重复，可添加null

LinkedList维护了两个属性first和last指向首节点和尾节点，每个节点对象，又维护了prev、next、itm三个属性，通过prev指向前一个，next指向后一个节点，实现双向链表。

常用方法：

【带有first和last就是实现了Deque，常用的是实现Queue】

add(E e)：实现了List接口。在链表后添加一个元素；

addFirst(E e)/push(E e)、addLast(E e)：实现了Deque接口。在链表头部/尾部插入一个元素；

offerFirst(E e)、offerLast(E e)：实现了Deque接口。在链表头部插入一个元素，成功返回true，失败false

offer(E e)：实现了Queue接口。将指定的元素插入到队列的末尾，成功返回true，失败false

peek()：获取第一个元素，但是不移除；

poll()：查询并移除第一个元素 ；

remove() ：移除链表中第一个元素;

底层：

（1）add

first = null, last = null

第一个节点加入的时候，first和last都指向newNode，prev=next=null

再加入一个节点， l指向第一个节点的last，再将l赋值到newNode的prev，将第一个节点的last指向newNode，此时l指向的是第一个节点不为空，将l的next指向newNode，完成链表，size=modCount=2

（2）removeFirst

4、比较

	ArrayList	LinkedList	Vector
底层结构	可变数组	双向链表	可变数组
线程安全	不安全(Collections.synchronizedList)	不安全	安全(synchronized)
初始值	10，扩容1.5倍	10，扩容2倍	空链表
	有序，可重复，多个null	有序，可重复，多
效率	增删较低，查找快(索引)	增删较高，查找慢(顺序遍历)	低
适用	大部分	频繁插入和删除

5、拓展【synchronizedList】

Collections.synchronizedList方法接受一个普通的List作为参数，并返回一个具有同步方法的List。可以使用这个同步的List在多线程环境中进行操作。尽管synchronizedList提供了一些基本的同步，但在复合操作（例如迭代和修改）时，仍然需要手动同步以确保线程安全。

.html

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
​
public class ManualSynchronizationExample {public static void main(String[] args) {// 创建一个普通的ArrayListList<String> normalList = new ArrayList<>();
​// 使用Collections.synchronizedList方法创建线程安全的ListList<String> synchronizedList = Collections.synchronizedList(normalList);
​// 创建两个线程，一个线程向列表中添加元素，另一个线程遍历列表Thread addThread = new Thread(() -> {for (int i = 0; i < 1000; i++) {addElement(synchronizedList, "Element" + i);}});
​Thread iterateThread = new Thread(() -> {iterateList(synchronizedList);});
​// 启动线程addThread.start();iterateThread.start();
​// 等待两个线程执行完成try {addThread.join();iterateThread.join();} catch (InterruptedException e) {e.printStackTrace();}}
​// 使用 synchronized 关键字确保对列表的安全添加操作private synchronized static void addElement(List<String> list, String element) {list.add(element);}
​// 使用 synchronized 关键字确保对列表的安全遍历操作private synchronized static void iterateList(List<String> list) {for (String element : list) {// 在迭代过程中对列表进行操作System.out.println(element);}}
}