欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

07、容器

程序员文章站 2022-07-08 15:39:13
一、数据结构分类物理结构:数组链表逻辑结构:由数组跟链表组成的8种数据结构(数组、队列、链表、散列表、栈、树、图)java的数据结构如下,其中Queue为后面加入,专为高并发设计二、多线程环境下容器衍化的过程Map角度:Hashtable是jdk1.0遗留下来的产物,所有方法都带了synchronize,采用的this锁。目前很少使用HashMap和SynchronizedHashMapMap m = Collections.synchro...

一、数据结构分类

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

07、容器

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

Map角度:
  1. Hashtable

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

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

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

final Object mutex;        // Object on which to synchronize

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

  1. 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,多线程环境下,写时效率低,读时效率高
,适合写少读多的环境

  1. SynchronizedList:获取方式类似于上面SynchronizedHashMap
  2. ConcurrentLinkedQueue:如上
  3. BlockingQueue
    分为*限的LinkedBlockingQueue和有界限的ArrayBlockingQueue
BlockingQueue<String> strs = new LinkedBlockingQueue<>()

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

  1. PriorityQueue:内部会自动按从小到大排序,内部相当于一个最小堆排序的树
  2. 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());
		}
	}
}

  1. 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());
	}
}
  1. 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