【Java】集合补充

常见基础集合汇总

数据结构：栈

数据结构分为：

（1）逻辑结构：--》思想上的结构--》卧室，厨房，卫生间 ---》线性表（数组，链表），图，树，栈，队列

（2）物理结构：--》真实结构--》钢筋混凝土+牛顿力学------》紧密结构（顺序结构），跳转结构（链式结构）

栈：

特点：后进先出（LIFO - last in first out）：

实际应用：

（1）内存分析：形参，局部变量放入栈中。放入的那个区域的数据结构就是按照栈来做的。

（堆：利用完全二叉树的结构来维护一组数据）

（2）网络浏览器多会将用户最近访问过的网址组织为一个栈。这样，用户每访问一个新页面，其地址就会被存放至栈顶；而用户每按下一次“后退”按钮，即可沿相反的次序访问此前刚访问过的页面。

（3）主流的文本编辑器也大都支持编辑操作的历史记录功能（ctrl + z：撤销，ctrl + y：恢复），用户的编辑操作被依次记录在一个栈中。一旦出现误操作，用户只需按下“撤销”按钮，即可取消最近一次操作并回到此前的编辑状态。

Stack

package com.star.test01;
import java.util.Stack;
/**
* @author : Starshine
*/
public class Test {
//这是main方法，程序的入口
public static void main(String[] args) {
/*
Stack是Vector的子类，Vector里面两个重要的属性：
Object[] elementData;底层依然是一个数组
int elementCount;数组中的容量
*/
Stack s = new Stack();
s.add("A");
s.add("B");
s.add("C");
s.add("D");
System.out.println(s);//[A, B, C, D]
System.out.println("栈是否为空：" + s.empty());
System.out.println("查看栈顶的数据，但是不移除：" + s.peek());
System.out.println(s);
System.out.println("查看栈顶的数据，并且不移除：" + s.pop());
System.out.println(s);
s.push("D");//和add方法执行的功能一样，就是返回值不同
System.out.println(s);
}
}

同步类容器

比如ArrayList，HashMap，线程不安全，现在想把线程不安全的集合转换为线程安全的集合：

public class Test01 {
//这是main方法，程序的入口
public static void main(String[] args) {
//ArrayList为案例：从线程不安全转为线程安全：
List list = Collections.synchronizedList(new ArrayList());
}
}

试试ArrayList的线程不安全：

package com.star.test02;
import java.util.ArrayList;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
/**
* @author : Starshine
*/
public class Demo {
//这是main方法，程序的入口
public static void main(String[] args) {
//创建一个ArrayList集合：
ArrayList list = new ArrayList();
//创建一个线程池：线程池定长100
ExecutorService es = Executors.newFixedThreadPool(100);
//并发向集合中添加10000个数据：
for (int i = 0; i < 10000; i++) {
//每个线程处理任务：run方法中的内容就是线程单元，任务，实际线程执行的部分
es.execute(new Runnable() {
@Override
public void run() {
list.add("aaa");
}
});
}
//关闭线程池：
es.shutdown();
//监控线程是否执行完毕：
while(true){
//线程都执行完以后返回true
if(es.isTerminated()){
System.out.println("所有的子线程都执行完毕了！");
//执行完毕以后看一下集合中元素的数量：
System.out.println(list.size());
if(list.size() == 10000){
System.out.println("线程安全！");
}else{
System.out.println("线程不安全！");
}
//线程执行完以后，while循环可以停止：
break;
}
}
}
}

结果：

利用同步类容器解决：

package com.star.test02;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
/**
* @author : Starshine
*/
public class Demo {
//这是main方法，程序的入口
public static void main(String[] args) {
//创建一个ArrayList集合：
ArrayList oldlist = new ArrayList();
List list = Collections.synchronizedList(oldlist);
//创建一个线程池：线程池定长100
ExecutorService es = Executors.newFixedThreadPool(100);
//并发向集合中添加10000个数据：
for (int i = 0; i < 10000; i++) {
//每个线程处理任务：run方法中的内容就是线程单元，任务，实际线程执行的部分
es.execute(new Runnable() {
@Override
public void run() {
list.add("aaa");
}
});
}
//关闭线程池：
es.shutdown();
//监控线程是否执行完毕：
while(true){
//线程都执行完以后返回true
if(es.isTerminated()){
System.out.println("所有的子线程都执行完毕了！");
//执行完毕以后看一下集合中元素的数量：
System.out.println(list.size());
if(list.size() == 10000){
System.out.println("线程安全！");
}else{
System.out.println("线程不安全！");
}
//线程执行完以后，while循环可以停止：
break;
}
}
}
}

结果：

源码解析：

ConcurrentMap并发容器

JDK5.0之后提供了多种并发类容器可以替代同步类容器，提升性能、吞吐量

ConcurrentHashMap替代HashMap、HashTable

ConcurrentSkipListMap替代TreeMap

简单原理：

并发情况下，验证提高性能：

ConcunrrentHashMap :

public class Test {
//这是main方法，程序的入口
public static void main(String[] args) {
//选择一个容器：
ConcurrentHashMap<String,Integer> map = new ConcurrentHashMap<>();
//创建10个线程：
for (int i = 0; i < 10; i++) {
new Thread(new Runnable() {
@Override
public void run() {
long startTime = System.currentTimeMillis();
for (int j = 0; j < 1000000; j++) {
map.put("test" + j , j);
}
long endTime = System.currentTimeMillis();
System.out.println("一共需要的时间：" + (endTime - startTime));
}
}).start();
}
}
}

结果：

Hashtable：

package com.star.test03;
import java.util.Hashtable;
import java.util.concurrent.ConcurrentHashMap;
/**
* @author : Starshine
*/
public class Test {
//这是main方法，程序的入口
public static void main(String[] args) {
//选择一个容器：
//ConcurrentHashMap<String,Integer> map = new ConcurrentHashMap<>();
Hashtable map = new Hashtable();
//创建10个线程：
for (int i = 0; i < 10; i++) {
new Thread(new Runnable() {
@Override
public void run() {
long startTime = System.currentTimeMillis();
for (int j = 0; j < 1000000; j++) {
map.put("test" + j , j);
}
long endTime = System.currentTimeMillis();
System.out.println("一共需要的时间：" + (endTime - startTime));
}
}).start();
}
}
}

结果：

HashMap：

package com.star.test03;
import java.util.HashMap;
import java.util.Hashtable;
import java.util.concurrent.ConcurrentHashMap;
/**
* @author : Starshine
*/
public class Test {
//这是main方法，程序的入口
public static void main(String[] args) {
//选择一个容器：
//ConcurrentHashMap<String,Integer> map = new ConcurrentHashMap<>();
//Hashtable map = new Hashtable();
HashMap map = new HashMap();
//创建10个线程：
for (int i = 0; i < 10; i++) {
new Thread(new Runnable() {
@Override
public void run() {
long startTime = System.currentTimeMillis();
for (int j = 0; j < 1000000; j++) {
map.put("test" + j , j);
}
long endTime = System.currentTimeMillis();
System.out.println("一共需要的时间：" + (endTime - startTime));
}
}).start();
}
}
}

线程安全的HashMap：

package com.star.test03;
import java.util.Collections;
import java.util.HashMap;
import java.util.Hashtable;
import java.util.Map;
import java.util.concurrent.ConcurrentHashMap;
/**
* @author : Starshine
*/
public class Test {
//这是main方法，程序的入口
public static void main(String[] args) {
//选择一个容器：
//ConcurrentHashMap<String,Integer> map = new ConcurrentHashMap<>();
//Hashtable map = new Hashtable();
HashMap oldmap = new HashMap();
Map map = Collections.synchronizedMap(oldmap);
//创建10个线程：
for (int i = 0; i < 10; i++) {
new Thread(new Runnable() {
@Override
public void run() {
long startTime = System.currentTimeMillis();
for (int j = 0; j < 1000000; j++) {
map.put("test" + j , j);
}
long endTime = System.currentTimeMillis();
System.out.println("一共需要的时间：" + (endTime - startTime));
}
}).start();
}
}
}

结果：

总结：

ConcurrentHashMap：性能高，线程安全

Hashtable: 线程安全，性能低

HashMap:线程不安全，性能高

线程安全的HashMap：线程安全，性能低

COW并发容器

【1】COW类并发容器，全称：Copy On Write容器，写时复制容器。（读写分离容器）

【2】原理：

向容器中添加元素时，先将容器进行Copy复制出一个新容器，然后将元素添加到新容器中，再将原容器的引用指向新容器。

并发读的时候不需要锁定容器，因为原容器没有变化，所以可以读取原容器中的值，使用的是一种读写分离的思想。

【3】这种设计的好处是什么呢？

注意上面的操作arr数组本身是无锁的，没有锁，在添加数据的时候，做了额外的复制，

此时如果有线程来读数据，那么读取的是老arr的数据，此时arr的地址还没有改呢，在我添加元素的过程中，

无论有多少个线程来读数据，都是读的原来的arr，不是新的arr

所以性能很高，读写分离。提高了并发的性能。如果再读再复制...

【4】注意：

CopyOnWrite容器只能保证数据的最终一致性，不能保证数据实时一致性。

所以如果你希望写入的的数据，马上能读到，请不要使用CopyOnWrite容器。

【5】适合特定场合：

这个应用场景显而易见，适合读多写少的情况。如果一万个线程都添加操作，都在集合中添加数据，那数组不断复制，长度不断+1，

那JVM肯定一直往上飙升，你用的时候肯定要评估使用场景的。

由于每次更新都会复制新容器，所以如果数据量较大并且更新操作频繁则对内存消耗很高，建议在高并发读的场景下使用。

【6】主要讲解：

COW容器有两种一种是CopyonWriteArrayList，一种是CopyOnWriteArraySet

一个是替代ArrayList，一个是代替Set

CopyOnWriteArrayList

【1】代码：

package com.star.test04;
import java.util.concurrent.CopyOnWriteArrayList;
/**
* @author : Starshine
*/
public class Test {
//这是main方法，程序的入口
public static void main(String[] args) {
CopyOnWriteArrayList<Integer> list = new CopyOnWriteArrayList<>();
//添加方法：
list.add(1);
list.add(2);
list.add(3);
list.add(4);
System.out.println(list);//[1, 2, 3, 4]
list.add(3);//add方法无论元素是否存在，都可以添加进去--》添加重复的元素
System.out.println(list);//[1, 2, 3, 4, 3]
//adj. 缺席的；缺少的；心不在焉的；茫然的
list.addIfAbsent(33);//添加不存在的元素--》不可以添加重复的数据
System.out.println(list);//[1, 2, 3, 4, 3, 33]
}
}

【2】源码分析：

public class CopyOnWriteArrayList<E>{
//底层基于数组实现的
private transient volatile Object[] array;
public CopyOnWriteArrayList() {
setArray(new Object[0]);
}
final void setArray(Object[] a) {
array = a; // array = new Object[0]
}
//add方法：
public boolean add(E e) {
final ReentrantLock lock = this.lock;
lock.lock();
try {
//返回底层array数组,给了elements
Object[] elements = getArray();
//获取elements的长度---》获取老数组的长度
int len = elements.length;
//完成数组的复制，将老数组中的元素复制到新数组中，并且新数组的长度加1操作
Object[] newElements = Arrays.copyOf(elements, len + 1);
//将e元素放入新数组最后位置
newElements[len] = e;
//array数组的指向从老数组变为新数组
setArray(newElements);
return true;
} finally {
lock.unlock();
}
}
final Object[] getArray() {
return array;//返回底层数组
}
private boolean addIfAbsent(E e, Object[] snapshot) {
final ReentrantLock lock = this.lock;
lock.lock();
try {
//取出array数组给current
Object[] current = getArray();
int len = current.length;
if (snapshot != current) {
// Optimize for lost race to another addXXX operation
int common = Math.min(snapshot.length, len);
//遍历老数组：
for (int i = 0; i < common; i++)
//eq(e, current[i])将放入的元素和老数组的每一个元素进行比较，如果有重复的元素，就返回false，不添加了
if (current[i] != snapshot[i] && eq(e, current[i]))
return false;
if (indexOf(e, current, common, len) >= 0)
return false;
}
//完成数组的复制，将老数组中的元素复制到新数组中，并且新数组的长度加1操作
Object[] newElements = Arrays.copyOf(current, len + 1);
//将e元素放入新数组最后位置
newElements[len] = e;
//array数组的指向从老数组变为新数组
setArray(newElements);
return true;
} finally {
lock.unlock();
}
}
}

CopyOnWriteArraySet

【1】代码：

/**
* @author : Starshine
*/
public class Test02 {
//这是main方法，程序的入口
public static void main(String[] args) {
//创建一个集合：
CopyOnWriteArraySet<Integer> set = new CopyOnWriteArraySet<>();
//在这里也体现出Set和List的本质区别，就在于是否重复
//所以add方法直接不可以添加重复数据进去
set.add(1);
set.add(2);
set.add(2);
set.add(7);
System.out.println(set);//[1, 2, 7]
}
}

【2】源码：

public class CopyOnWriteArraySet<E>{
//CopyOnWriteArraySet底层基于CopyOnWriteArrayList
private final CopyOnWriteArrayList<E> al;
public CopyOnWriteArraySet() {
al = new CopyOnWriteArrayList<E>();
}
//添加方法：
public boolean add(E e) {
return al.addIfAbsent(e);//底层调用的还是CopyOnWriteArrayList的addIfAbsent
}
}

总结：

由上面的源码看出，每次调用CopyOnWriteArraySet的add方法时候，其实底层是基于CopyOnWriteArrayList的addIfAbsent，

每次在addIfAbsent方法中每次都要对数组进行遍历，所以CopyOnWriteArraySet的性能低于CopyOnWriteArrayList