07、容器

一、数据结构分类

• 物理结构：数组链表
• 逻辑结构：由数组跟链表组成的8种数据结构（数组、队列、链表、散列表、栈、树、图）
• java的数据结构如下，其中Queue为后面加入，专为高并发设计

二、多线程环境下容器衍化的过程

Map角度：

1. Hashtable

是jdk1.0遗留下来的产物，所有方法都带了synchronize，采用的this锁。目前很少使用

2. HashMap和SynchronizedHashMap

Map<UUID, UUID> m = Collections.synchronizedMap(new HashMap<UUID, UUID>());

HashMap默认是线程不安全的，但可通过上面方法得到线程安全的SynchronizedHashMap。

final Object mutex;        // Object on which to synchronize

SynchronizedHashMap采用的是对象锁，相比于没有锁住整个类，相比于Hashtable细化了锁的颗粒度

3. ConcurrentHashMap

Map<UUID, UUID> m = new ConcurrentHashMap<>();

ConcurrentHashMap是线程安全的，使用CAS无锁优化实现，适用于高并发多线程场景。他的主要优势是读的时候特别快

可参考：
java1.5新特性 ConcurrentHashMap、Collections.synchronizedMap、Hashtable讨论

List角度：

Vector（this锁）——》ArrayList（无锁）——》Queue（CAS）

• ConcurrentLinkedQueue：用链表实现，没有长度限制

Queue<String> clQueue= new ConcurrentLinkedQueue<>();

Queue和Array的区别：添加了很多对线程友好的api（3、4、5）

1. clQueue.size() 返回元素个数
2. clQueue.add() 添加元素，如果添加失败抛出异常
3. clQueue.offer() 添加元素，成功返回true，失败返回false
4. clQueue.poll() 取出元素，并且remove
5. clQueue.peek() 取出元素，但不remove

三、常用的多线程容器

1. ConcurrentHashMap如上
2. ConcurrentSkipListMap：适用于多线程情况下，有序对的map存储。跳表（SkipList）及ConcurrentSkipListMap源码解析
   
3. CopyOnWriteArrayList

List<String> lists = new CopyOnWriteArrayList<>()

写时复制容器 copy on write，多线程环境下，写时效率低，读时效率高
，适合写少读多的环境

4. SynchronizedList：获取方式类似于上面SynchronizedHashMap
5. ConcurrentLinkedQueue：如上
6. BlockingQueue
   分为*限的LinkedBlockingQueue和有界限的ArrayBlockingQueue

BlockingQueue<String> strs = new LinkedBlockingQueue<>()

阻塞的队列实现，当队列为空时strs.take()会阻塞，当队列为满时strs.put(i)会阻塞 。是天生的生产者消费者模型

7. PriorityQueue：内部会自动按从小到大排序，内部相当于一个最小堆排序的树
8. DelayQueue：PriorityQueue的升级版，实现需自定义Delay的排序规则。按紧迫时间排序，一般用于按时间进行任务调度
   例如

public class T07_DelayQueue {

	static BlockingQueue<MyTask> tasks = new DelayQueue<>();

	static Random r = new Random();
	
	//实现Delayed接口
	static class MyTask implements Delayed {
		String name;
		long runningTime;
		
		MyTask(String name, long rt) {
			this.name = name;
			this.runningTime = rt;
		}

		//实现比较方法
		@Override
		public int compareTo(Delayed o) {
			if(this.getDelay(TimeUnit.MILLISECONDS) < o.getDelay(TimeUnit.MILLISECONDS))
				return -1;
			else if(this.getDelay(TimeUnit.MILLISECONDS) > o.getDelay(TimeUnit.MILLISECONDS)) 
				return 1;
			else 
				return 0;
		}

		//实现getDelay方法
		@Override
		public long getDelay(TimeUnit unit) {
			
			return unit.convert(runningTime - System.currentTimeMillis(), TimeUnit.MILLISECONDS);
		}
		
		
		@Override
		public String toString() {
			return name + " " + runningTime;
		}
	}

	public static void main(String[] args) throws InterruptedException {
		long now = System.currentTimeMillis();
		MyTask t1 = new MyTask("t1", now + 1000);
		MyTask t2 = new MyTask("t2", now + 2000);
		MyTask t3 = new MyTask("t3", now + 1500);
		MyTask t4 = new MyTask("t4", now + 2500);
		MyTask t5 = new MyTask("t5", now + 500);
		
		tasks.put(t1);
		tasks.put(t2);
		tasks.put(t3);
		tasks.put(t4);
		tasks.put(t5);
		
		System.out.println(tasks);
		
		for(int i=0; i<5; i++) {
			System.out.println(tasks.take());
		}
	}
}

9. SynchronousQueue：不用来装元素。用来让一个线程给另外一个线程下达任务。实现了一个线程在等待某个变量，另一个线程传值给他的场景

public class T08_SynchronusQueue { //容量为0
	public static void main(String[] args) throws InterruptedException {
		BlockingQueue<String> strs = new SynchronousQueue<>();
		new Thread(()->{
			try {
				//阻塞。知道strs被赋值
				System.out.println(strs.take());
			} catch (InterruptedException e) {
				e.printStackTrace();
			}
		},"t1").start();

		strs.put("aaa"); //t1继续执行，主线程也继续执行
		System.out.println(strs.size());
	}
}

10. LinkedTransferQueue：SynchronousQueue的升级版，能传输多个元素，可以把他想象成一个篮子。然后传递给一个线程之后本线程也会阻塞，等该元素被取走后再继续执行

public class T09_TransferQueue {
	public static void main(String[] args) throws InterruptedException {
		LinkedTransferQueue<String> strs = new LinkedTransferQueue<>();
		
		new Thread(() -> {
			try {
				System.out.println(strs.take());
			} catch (InterruptedException e) {
				e.printStackTrace();
			}
		}).start();

		//传递给一个线程之后阻塞，等该元素被取走后再继续执行
		strs.transfer("aaa");
		System.out.println("data has be get");
	}
}

本文地址：https://blog.csdn.net/qq_41567223/article/details/114259499