LinkedList<Integer> lists = new LinkedList<>(); lists.addFirst(1); lists.push(2); lists.addLast(3); lists.add(4); lists.addFirst(5); lists.forEach(System.out::println); // 5 2 1 3 4 复制代码
addFirst
和 addLast
方法很清楚 ,
push
方法的话 ,默认是 andFirst
实现
add
方法默认是 addLast
实现 ....
所以上面总结一下就是 add和last , push和first ,
其实我们要明白一下 , 链表相对于数组来说, 链表的添加和删除速度很快 , 是 顺序添加删除 很快,因为一个linkedList会保存第一个节点和最后一个节点,时间复杂度为 O(1)
, 但是你要指定位置添加 add(int index, E element)
, 那么此时他会先遍历, 然后找到改位置的节点, 将你的节点添加到他前面 , 此时时间复杂度最大值为 O(n)
,
数组呢 , 我们知道ArrayList底层实现就是数组 , 数组优点就是由于内存地址是顺序的, 属于一块整的 , 此时遍历起来很快 , 添加删除的话 ,他会复制数组, 当数组长度特别大时,所消耗的时间会很长
这是一张图 , 大家可以看一下 ,
List<Integer> integers = Arrays.asList(1, 2, 3, 4, 5); integers.set(2, 5); // 这个操作可以 //integers.add(6); 这个会抛出异常 integers.forEach(System.out::println); // 1 2 5 4 5 1. 很显然我们是可以修改 list集合的 可以使用set方法 2. 但是当我们尝试去使用add() 方法时,会抛出 java.lang.UnsupportedOperationException 的异常, 不支持操作的异常 3.当我们使用 java9+时 可以使用 List.of()方法 ,他就是彻彻底底的不可修改的 复制代码
1. 使用 Collections这个工具类 List<Integer> integers1 = Collections.synchronizedList(integers); 2. java5+ 变成 CopyOnWriteArrayList CopyOnWriteArrayList<Integer> integers2 = (CopyOnWriteArrayList<Integer>) integers; 3. java9+ ,使用 List.of() 变成只读对象 复制代码
1. 创建一个安全的空集合,防止NullPointerException异常 List<String> list = Collections.<String>emptyList(); 2. 拷贝集合 Collections.addAll(list, 2,3, 4, 5, 6); 3. 构建一个安全的集合 List<Integer> safeList = Collections.synchronizedList(list); 4. 二分查找 Collections.binarySearch(list, 2); 5.翻转数组 Collections.reverse(list); 复制代码
翻转有很多方法 java.util.Collections
, 可以去学一下, 有学习能力的可以去学习一下 Google的 Guava
很强的工具类 , 里面很多
HashMap
实现的 ,其中的元素没有按顺序排列. TreeMap
** HashMap
和双向链表的集合,但它同时维护了一个双链表来记录插入的顺序,基本方法的复杂度为O(1)。 TreeSet的元素必须是实现了 java.lang.Comparable<T>
接口 , 所以他是根据此个接口的方法 compareTo
方法进行判断重复的, 当返回值一样的时,认定重复
我们看源码 会发现 他里面有一个 HashMap ,那为什么要用(用transient关键字标记的成员变量不参与序列化过程。) 为什么呢 ,因为 HashMap 已经实现了Serializable,
怎么实现一个 ConcurrentHashSet
package com.alibaba.dubbo.common.utils; import java.util.AbstractSet; import java.util.ConcurrentModificationException; import java.util.Iterator; import java.util.Set; import java.util.concurrent.ConcurrentHashMap; import java.util.concurrent.ConcurrentMap; public class ConcurrentHashSet<E> extends AbstractSet<E> implements Set<E>, java.io.Serializable { private static final long serialVersionUID = -8672117787651310382L; private static final Object PRESENT = new Object(); private final ConcurrentMap<E, Object> map; public ConcurrentHashSet() { map = new ConcurrentHashMap<E, Object>(); } public ConcurrentHashSet(int initialCapacity) { map = new ConcurrentHashMap<E, Object>(initialCapacity); } ............... } 复制代码
很显然跟我说的好像 一模一样 ,哈哈哈 ,我也是看别人学的,只是看你用的巧不巧,他继承了AbstractSet这个抽象类,重写了 他部分想要改的方法, 同时也实现了 set接口
public CopyOnWriteArraySet() { al = new CopyOnWriteArrayList<E>(); } 复制代码
很显然翻源码我们发现 他实现了 CopyOnWriteArrayList();
HashTable容器使用synchronized来保证线程安全,但在线程竞争激烈的情况下HashTable的效率非常低下。因为当一个线程访问HashTable的同步方法时,其他线程访问HashTable的同步方法时,可能会进入阻塞或轮询状态。如线程1使用put进行添加元素,线程2不但不能使用put方法添加元素,并且也不能使用get方法来获取元素,所以竞争越激烈效率越低。
其中部分信息咱们还能聊聊,不会的我就算了
内部节点分为 Node<K,V>
和 TreeNode<K,V>
, 都直接间接的实现与 Map.Entry<K,V>
, 后者所占用的空间较大,所以是一种空间换时间的想法 , 前者只要保存两个节点信息, 后者需要保存四个
存储结构是 数组+链表
或者 数组+ 红黑树
实现,有个阈值,当链表长度大于8,大于8的话把链表转换为红黑树,
当小于等于6时会自动转成链表
原因: (反正我看不懂,只是解决碰撞概率的问题,数学问题这个是)
红黑树的平均查找长度是log(n),长度为8,查找长度为log(8)=3,链表的平均查找长度为n/2,当长度为8时,平均查找长度为8/2=4,这才有转换成树的必要;链表长度如果是小于等于6,6/2=3,虽然速度也很快的,但是转化为树结构和生成树的时间并不会太短。
还有选择6和8的原因是:
中间有个差值7可以防止链表和树之间频繁的转换。假设一下,如果设计成链表个数超过8则链表转换成树结构,链表个数小于8则树结构转换成链表,如果一个HashMap不停的插入、删除元素,链表个数在8左右徘徊,就会频繁的发生树转链表、链表转树,效率会很低。
Node[] table的初始化长度length(默认值是16),LoadFactor为负载因子(默认值是0.75), 例如为1,虽然减少了空间开销,提高了空间利用率,但同时也增加了查询时间成本;加载因子过低,例如0.5,虽然可以减少查询时间成本,但是空间利用率很低,同时提高了rehash操作的次数
实现链接,大家不会写可以看看
HashMap是非synchronized ,线程不安全
大家可以看看高能讲解:
队列在于你走向高级工程师必须走的一步 . 一开始我们对于他并不了解,但是你会发现并发包里面一堆关于队列的类,你就知道了他的关键所在,先进先出的使用场景很常见的 通过我这段时间的学习,我发现在线程池这块,还有这消息队列,还有在数据库连接池这块都需要队列.这些中间件对于队列的依赖性太过于强烈. 所以学会队列是很重要的一步.这些内容我会慢慢补充的.
我们都知道 队列 (Queue)是一种 先进先出 (FIFO)的数据结构,Java中定义了 java.util.Queue
接口用来表示队列。Java中的 Queue
与 List
、 Set
属于同一个级别接口,它们都是实现了 Collection
接口。注意: HashMap没有实现 Collection
接口
LinkedList
是链表结构,队列呢也是一个列表结构,继承关系上 , LinkedList实现了Queue , 所以对于Queue来说 ,
添加是 offer(obj)
, 删除是 poll()
, 获取队头(不删除)是 peek()
.
public static void main(String[] args) { Queue<Integer> queue = new LinkedList<>(); queue.offer(1); queue.offer(2); queue.offer(3); System.out.println(queue.poll()); System.out.println(queue.poll()); System.out.println(queue.poll()); } // 1, 2 , 3 复制代码
PriorityQueue维护了一个有序列表,插入或者移除对象会进行Heapfy操作, 默认情况下可以称之为小顶堆 。当然,我们也可以给它指定一个实现了 java.util.Comparator
接口的排序类来指定元素排列的顺序。
PriorityQueue 是一个无界队列 , 当你设置初始化大小还是不设置 , 都不影响他继续添加元素
ConcurrentLinkedQueue
是基于链接节点的并且线程安全的队列。因为它在队列的尾部添加元素并从头部删除它们,所以只要不需要知道队列的大小 ConcurrentLinkedQueue
对公共集合的共享访问就可以工作得很好。收集关于队列大小的信息会很慢,需要遍历队列。
ArrayBlockingQueue 是有界队列
LinkedBlockingQueue 看构造方法区分 , 默认构造方法最大值是 2^31-1
但是当 take 和 put操作时 ,ArrayBlockingQueue速度要快于 LinkedBlockingQueue原因是什么
1.队列中的锁的实现不同 ArrayBlockingQueue中的锁是没有分离的,即生产和消费用的是同一个锁; LinkedBlockingQueue中的锁是分离的,即生产用的是putLock,消费是takeLock 2.在生产或消费时操作不同 ArrayBlockingQueue基于数组,在生产和消费的时候,是直接将枚举对象插入或移除的,不会产生或销毁任何额外的对象实例; LinkedBlockingQueue基于链表,在生产和消费的时候,需要把枚举对象转换为Node进行插入或移除,会生成一个额外的Node对象,这在长时间内需要高效并发地处理大批量数据的系统中,其对于GC的影响还是存在一定的区别。
LinkedBlockingQueue的消耗是ArrayBlockingQueue消耗的10倍左右,
即LinkedBlockingQueue消耗在1500毫秒左右,而ArrayBlockingQueue只需150毫秒左右。
我们测试的是 ArrayBlockingQueue 会比 LinkedBlockingQueue性能好 , 好差不多50%起步 ,
BlockingQueue
可以是限定容量的。
BlockingQueue
实现主要用于生产者-使用者队列,但它另外还支持collection接口。
BlockingQueue
实现是线程安全的
BlockingQueue
是阻塞队列 (看你使用的方法) , ConcurrentLinkedQueue
是非阻塞队列
LinkedBlockingQueue 是一个线程安全的阻塞队列,基于链表实现,一般用于生产者与消费者模型的开发中。采用锁机制来实现多线程同步,提供了一个构造方法用来指定队列的大小,如果不指定大小,队列采用默认大小(Integer.MAX_VALUE,即整型最大值)。
ConcurrentLinkedQueue 是一个线程安全的非阻塞队列,基于链表实现。java并没有提供构造方法来指定队列的大小,因此它是无界的。为了提高并发量,它通过使用更细的锁机制,使得在多线程环境中只对部分数据进行锁定,从而提高运行效率。他并没有阻塞方法,take和put方法.注意这一点
有一个是 JDK1.7才加入的, 所以常见的就六个
构造函数必须传入指定大小, 所以他是一个有界队列
分为两种情况 , 第一种构造函数指定大小, 他是一个有界队列 , 第二种情况,不指定大小他可以称之为无界队列, 队列最大值为 Integer.MAX_VALUE
他是一个无界队列 , 不管你使用什么构造函数 ..
一个内部由优先级堆支持的、基于时间的调度队列。队列中存放Delayed元素,只有在延迟期满后才能从队列中提取元素。当一个元素的getDelay()方法返回值小于等于0时才能从队列中poll中元素,否则poll()方法会返回null。
这个队列类似于Golang的channel , 也就是chan ,跟无缓冲区的chan很相似. 比如take和put操作就跟chan一模一样. 但是区别在于他的poll和offer操作可以设置等待时间.
如果你学过golang的话. 应该理解 . 我写个例子
func main() { ch := make(chan int, 0) start := time.Now().UnixNano() go func() { time.Sleep(time.Millisecond * 500) ch <- 1 }() x := <-ch fmt.Printf("msg : %d , spend : %dms/n", x, (time.Now().UnixNano()-start)/1e6) } // 输出 // msg : 1 , spend : 500ms 复制代码
那么换而言之 , Java呢
public class TestSync { public static void main(String[] args) throws InterruptedException { SynchronousQueue<Integer> queue = new SynchronousQueue<>(); long start = System.currentTimeMillis(); new Thread(() -> { try { Integer poll = queue.take(); System.out.printf("receive : %d , spend : %dms./n", poll, System.currentTimeMillis() - start); } catch (InterruptedException e) { e.printStackTrace(); } }).start(); new Thread(() -> { try { //sleep 2000ms TimeUnit.SECONDS.sleep(2); queue.put(1); } catch (InterruptedException e) { e.printStackTrace(); } }).start(); } } // 输出 //receive : 1 , spend : 2060ms. 复制代码
但是他和chan不同的是, 他的poll操作吧, (类似于golang的 select case 操作) , 等不到放弃, 返回一个null.
但是唯一不同的是 他可以指定等待时间.超过等待时间再放弃.
Integer poll = queue.poll(1000,TimeUnit.MILLISECONDS); 复制代码
这个就是等待1000ms , 等不到放弃了 .
像线程池中用 SynchronousQueue
使用的是 offer(obj)
操作, 也就是说干脆插入不进去.因为他懒得等 , 但是offer可以指定等待时间的.
总结一下. take 和 put 一对,是死等待
, poll和offer灵活, 活着来
Java延迟队列提供了在指定时间才能获取队列元素的功能,队列头元素是最接近过期的元素。没有过期元素的话,使用poll()方法会返回null值,超时判定是通过getDelay(TimeUnit.NANOSECONDS)方法的返回值小于等于0来判断。延时队列不能存放空元素。
添加的元素必须实现 java.util.concurrent.Delayed
接口
@Test public void testLinkedList() throws InterruptedException { DelayQueue<Person> queue = new DelayQueue<>(); queue.add(new Person()); System.out.println("queue.poll() = " + queue.poll(200,TimeUnit.MILLISECONDS)); } static class Person implements Delayed { @Override public long getDelay(TimeUnit unit) { // 这个对象的过期时间 return 100L; } @Override public int compareTo(Delayed o) { //比较 return o.hashCode() - this.hashCode(); } } 输出 : queue.poll() = null 复制代码
JDK1.7 加入的无界队列 , 亮点就是无锁实现的,性能高 .
Doug Lea 说这个是最有用的 BlockingQueue 了 , 性能最好的一个 . Doug Lea说 从功能角度来讲,LinkedTransferQueue实际上是ConcurrentLinkedQueue、SynchronousQueue(公平模式)和LinkedBlockingQueue的超集。
他的核心方法其实就是 xfer()方法
,基本所有方法都是围绕着这个进行的 , 一般就是 SYNC ,ASYNC,NOW ,来区分状态量. 像put,offer,add 都是 ASYNC
, 所以不会阻塞. 下面几个状态对应的变量.
private static final int NOW = 0; // for untimed poll, tryTransfer(不阻塞) private static final int ASYNC = 1; // for offer, put, add(不阻塞) private static final int SYNC = 2; // for transfer, take(阻塞) private static final int TIMED = 3; // for timed poll, tryTransfer (waiting) 复制代码
小顶堆是什么 : 任意一个非叶子节点的权值,都不大于其左右子节点的权值
PriorityQueue是非线程安全的,PriorityBlockingQueue是线程安全的
两者都使用了堆,算法原理相同
PriorityQueue 的逻辑结构是一棵完全二叉树,就是因为完全二叉树的特点, 他实际存储确实可以为一个数组的, 所以他的 存储结构其实是一个数组 。
1. 首先java 中的 PriorityQueue 是优先队列,使用的是小顶堆实现
/** * 构建一个 大顶堆 * * @param tree * @param n */ static void build_heap(int[] tree, int n) { // 最后一个节点 int last_node = n - 1; // 开始遍历的位置是 : 最后一个堆的堆顶 , (以最小堆为单位) int parent = (last_node - 1) / 2; // 递减向上遍历 for (int i = parent; i >= 0; i--) { heapify(tree, n, i); } } /** * 递归操作 * @param tree 代表一棵树 * @param n 代表多少个节点 * @param i 对哪个节点进行 heapify */ static void heapify(int[] tree, int n, int i) { // 如果当前值 大于 n 直接返回了 ,一般不会出现这种问题 ..... if (i >= n) { return; } // 子节点 int c1 = 2 * i + 1; int c2 = 2 * i + 2; // 假设最大的节点 为 i (父节点) int max = i; // 如果大于 赋值给 max if (c1 < n && tree[c1] > tree[max]) { max = c1; } // 如果大于 赋值给 max if (c2 < n && tree[c2] > tree[max]) { max = c2; } // 如果i所在的就是最大值我们没必要去做交换 if (max != i) { // 交换最大值 和 父节点 的位置 swap(tree, max, i); // 交换完以后 , 此时的max其实就是 i原来的数 ,就是最小的数字 ,所以需要递归遍历 heapify(tree, n, max); } } // 交换操作 static void swap(int[] tree, int max, int i) { int temp = tree[max]; tree[max] = tree[i]; tree[i] = temp; } 复制代码
栈结构属于一种先进者后出,类似于一个瓶子 , 先进去的会压到栈低(push操作) , 出去的时候只有一个出口就是栈顶 , 返回栈顶元素,这个操作称为pop ,
stack 继承自 Vector
, 所有方法都加入了 sync 修饰, 使得效率很低 ,线程安全.
@Test public void testStack() { Stack<Integer> stack = new Stack<>(); // push 添加 stack.push(1); stack.push(2); // pop 返回栈顶元素 , 并移除 System.out.println("stack.pop() = " + stack.pop()); System.out.println("stack.pop() = " + stack.pop()); } 输出 : 2 , 1 复制代码
但是LInkedList很好的实现了这个 , 同时他是个线程不安全的类.
@Test public void testStack() { LinkedList<Integer> stack = new LinkedList<>(); stack.push(1); stack.push(2); System.out.println("stack.pop() = " + stack.pop()); System.out.println("stack.pop() = " + stack.pop()); } 输出 2 , 1 复制代码