学习笔记
一、数组
1.数组:在计算机存储中是一段连续的地址,每个地址都可以通过内存管理器直接访问,数组的索引表达的是offset的语意,对任何一个元素,都可以使用y = x + b(y是元素地址,x是偏移量,b是数组首元素地址)计算得到任意元素的地址,所以数组访问任意位置元素的时间是一样的。引用@mo-xun
优点:随机访问的时候时间复杂度O(1)
缺点:插入、删除元素的时候时间复杂度O(n)
2.相对于JDK中是 ArrayList 的结构,在 add 的时候会判断容量是否足够,不够的话会会扩容2倍 ensureCapacity,期间扩容和后移/前移操作都是System.arraycopy 来拷贝
3.数组基本操作时间复杂度
prepend O(1)
append O(1)
lookup O(1)
insert O(n)
delete O(n)
二、链表
1.链表:由一个一个节点连接一起,相比于数组对于频繁插入、删除的时候我们会使用链表
优点:插入、删除时间复杂度都O(1)
缺点:顺序访问的时间复杂度O(n)
Node包含value/next/previous是双向链表,头指针用Head表示、尾指针用Tail表示,最后一个next指向null
2.相对于JKD中是 LinkedList 的结构,它的结构是双向链表,在Entry中有一个Entry next和Entry previous,在外层成员变量维护这first和last头尾指针和size这个链表的大小
3.链表基本操作时间复杂度
prepend O(1)
append O(1)
lookup O(n)
insert O(1)
delete O(1)
三、跳表
1.跳表:在Redis中有应用,跳表是为了优化链表的随机访问的缺陷而产生的
2.如何给链表加速?
方法一:添加头尾指针,这样在查询头尾节点的时候O(1)时间就可以拿出
方法二:中心**就是升维,空间来换取时间,基于方法一就可以扩展了,我多添加一些指针
3.通过给链表加速,我们不断给中间插入指针,中间的中间.....持续下去(所以每层索引遍历的节点个数是3),那么第一级索引就建立出来了,原始链表速度是1,一级索引速度就是2,然后同理建立二级索引相对于原始链表跨4个元素,速度是4,以此类推增加多级索引
4.一共有n个元素,需要增加log2^n-1个级索引证明,跳表查询时间时间复杂度等于层数所以为log2^n
证明推理:链表有n个第一级索引是n/2个元素,第二级是n/4,第h级是n/2^h
假设索引有h级,最高的索引有2个节点则有 n/2^h = 2 退出 h=log2^n-1,同理假设最高层索引有一个则需要建立 log2^n层索引
5.跳表空间复杂度
原始链表大小为n,每2个结点抽1个,每层索引的结点数: n/2,n/4,n/8...4,2
原始链表大小为n,每3个结点抽1个,每层索引的结点数: n/3,n/9,n/27...4,2
空间复杂度为O(n) 数量级是n 收敛起来还是n
四、缓存
1.缓存:这里说的缓存是一种广义的概念,在计算机存储层次结构中,低一层的存储器都可以看做是高一层的缓存。缓存之所以有效是因为程序和数据的局部性(locality),程序会按固定的顺序执行,数据会存放在连续的内存空间并反复读写。
2.LRU-Cache最近最少使用(LRU,Least Recently Used)
简书:LRU实现 hashmap+双向链表 https://www.jianshu.com/p/b1ab4a170c3c
3.为什么Redis用跳表而不用红黑树
并发场景下红黑树要锁多个节点比较复杂
排序集合通常使用zrange和zrevrange
便于实现、调试
dubbo LinkedList 实现LRU-Cache
五、栈
Stack:先入后出;添加、删除都是O(1);查询是O(n)
基本方法:
boolean empty():判断这个栈是否为空
E peek():查看栈顶元素
E pop():删除栈顶元素
E push(E item) :从栈顶入栈
int search(Object o):查询一个元素在stack的下标
六、队列
Queue:先入先出;添加、删除都是O(1),在Java中是接口下面的子类有很多如:LinkedList、LinkedBlockingQueue、DelayQueue、PriorityQueue等
基本方法:
插入 抛异常的add(e)/返回特殊值的 offer(e)
删除 抛异常的remove()/返回特殊值的poll()
访问元素 抛异常的element()/返回特殊值peek()
七、双端队列
Deque(Double-ended Queue):双端队列,可以从前后添加和删除元素;添加、删除都是O(1) 查询O(n),在Java中实现有ArrayDeque,ConcurrentLinkedDeque,LinkedBlockingDeque,LinkedList
基本方法:
从头部操作 从尾部操作
抛异常 特殊值 抛异常 特殊值
插入 addFirst(e) offerFirst(e) addLast(e) offerLast(e)
删除 removeFirst() pollFirst() removeLast() pollLast()
访问元素 getFirst() peekFirst() getLast() peekLast()
八、优先队列
PriorityQueue 插入操作O(1)、去除操作O(logn)按照元素的优先级取出,保证了一定的有序性,底层实现可以是heap、bst、treap,必须要实现comparator方法就是比较大小用于保证有序
基本方法:
boolean add(E e):添加元素
void clear():清空优先队列
boolean offer():添加元素
boolean remove(Object o) :删除元素
poll/peek
九、对于Queue和PriorityQueue分析
对于Queue来说很简单它只是一个接口,主要有add添加抛异常、remove移除头元素、element返回头元素、offer添加返回特殊值、poll移除头元素、peek返回头元素,前面的会抛出异常而后面的几个会返回特殊值
Queue主要的实现类有ArrayBlockingQueue、ArrayDeque、ConcurrentLinekedQueue、ConcurrentLinekedDeque、DelayQueue、LinkedList、LinkedBlockingQueue、LinkedBlockingDeque、PriorityQueue等。
ArrayBlockingQueue举例核心成员变量有:
- 元素数组Object[] items
- 放入队头元素的下标 takeIndex
- 拿走队尾元素的下标 putIndex
- 队列元素数量 count
对于并发和锁的方面主要有:
- ReentrantLock 可重入锁 具有对中断有响应、可限时、可公平锁的特点
- 2个Condition 用于控制放入和拿走元素的条件 实现线程间的协调
对于PriorityQueue他是属于Queue的一种实现,底层结构使用数组,初始化大小为11个
在初始化的时候首先会heapify构建这个堆,在插入的时候会siftUp调整这个堆以保证每次拿出来
对顶元素都是最小值,在出队列的时候会shiftDown然后将最后一个元素放到0位置整体在向下进行调整使得再次成为堆
十、改写Deque
Deque<String> deque = new LinkedList<>();
deque.addFirst("a");
deque.addFirst("b");
deque.addLast("c");
System.out.println(deque);
String peek = deque.peek();
System.out.println(peek);
System.out.println(deque);
while (deque.size() > 0) {
System.out.println(deque.pop());
}
System.out.println(deque);