分类标签归档：读书笔记
用数组存储
二三树
AVL
红黑树
B 树
B+
⭐️slpay 伸展树
⭐️treap树的面试题一般都是递归的，这是为什么？
看是否有环，有环为图
https://en.wikipedia.org/wiki/Self-balancing_binary_search_tree
二叉搜索树，也称为二叉搜索排序树、有序二叉树(Ordered Binary Tree)、排序二叉树(Sorted Binary Tree), 是指一棵空
去的过程叫“递”，回来的过程叫“归”
写递归代码的关键就是找到如何将大问题分解为小问题的规律，并且基于此写出递推公式，然后再推敲终止条件，最后将递推公式和终止条件翻译成代码
编写递归代码的关键是，只要遇到递归，我们就把它抽象成一个递推公式，不用想一层层的调用关系，不要试图用人脑去分解递归的每个步骤
递归与循环没有明显的边界，它是通过函数体来进行的循环
终止条件 递推公式
递归会利用栈保存临时变量，如果
from functools import lru_cache
@lru_cache(None)
def add(x, y):
return x+yhttps://www.jianshu.com/p/b1ab4a170c3c
Understanding the Meltdown exploit
缓存文件置换机制
缓存文件置换机制 中文
比较类排序: 通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此也称为非线性时间比较类排序。
非比较类排序: 不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时 间下界，以线性时间运行，因此也称为线性时间非比较类排序。
排序算法
比较类排序
交换排序
冒泡排序
快速排序
插入排序
简单插入排序
希尔排序
选择排序
哈希表(hash table)， 也叫散列表，是根据关键码值(key value) 而直接进行访问的数据结构 它通过贝把关键码值映射到表中的一个位置来访问记录，以加快查找的速度。 这个映射函数叫做散列函数(hash function)，存放记录的数组叫做哈希表(或散列表)
key - value对，key不重复
new HashMap()/ new TreeMap()
map.set(key, value)
map.get(key)
map.has(key)
map.size()
map.clear()
不重复元素集合
new Ha栈只支持两个基本操作：入栈push()和出栈pop()
用数组实现的栈，我们叫作顺序栈，用链表实现的栈，我们叫作链式栈
不管是顺序栈还是链式栈，我们存储数据只需要一个大小为n的数组就够了。在入栈和出栈过程中，只需要一两个临时变量存储空间，所以空间复杂度是O(1)
不管是顺序栈还是链式栈，入栈、出栈只涉及栈顶个别数据的操作，所以时间复杂度都是O(1)。
注意，这里存储数据需要一个大小为n的数组，并不是说空间复杂度就是O(n)。因为，这n个空间是必须的，无法省掉。所以我们说空间复杂度的时候，是指除了原本的数据存储空间外，算法运行还需要额外的存储空间。
最好情况时间复杂度是O
队列跟栈一样，也是一种操作受限的线性表数据结构
用数组实现的队列叫作 顺序队列，用链表实现的队列叫作 链式队列
最基本的操作有两个：入队enqueue()，放一个数据到队列尾部；出队dequeue()，从队列头部取一个元素
高性能队列Disruptor、Linux环形缓存，都用到了循环并发队列；Java concurrent并发包利用ArrayBlockingQueue来实现公平锁
数组（Array）是一种线性表数据结构。它用一组连续的内存空间，来存储一组具有相同类型的数据 数组是线性表（Linear List）。顾名思义，线性表就是数据排成像一条线一样的结构。 每个线性表上的数据最多只有前和后两个方向。其实除了数组，链表、队列、栈等也是线性表结构 而与它相对立的概念是非线性表，比如二叉树、堆、图等。之所以叫非线性，是因为，在非线性表中，数据之间并不是简单的前后关系。
| 操作 | 复杂度 | 备注 |
|---|---|---|
| Access | O(1) | |
| 插入 insert | O(n) | 头O(n), 尾O(1), 平均O(n/2) 即 O(n) |
| 删除 delete | O(n) | 头O(n), |
