分类目录归档：算法
并查集(union & find) 是一种树形结构，用于处理一些不交集(Disjoint Sets) 的合并及查询问题
Find: 确定元素属于哪一个子集。他可以被用来确定两个元素是否属于同一个子集。
Union: 将两个子集合合并成同一个集合
字典树，即 Trie 树，又称单词 查找树或键树，是一种树形结构。典型应用是用于统计和排序大量的字符串(但不仅限于字符串)，所以经常被搜索引擎系统用于文本词频统计。 它的优点是:最大限度地减少无谓的字符串比较，查询效率比哈希表高。
Trie 树的核心思想是空间换时间。 利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。
static用数组存储
二三树
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
缓存文件置换机制
缓存文件置换机制 中文
去的过程叫“递”，回来的过程叫“归”
写递归代码的关键就是找到如何将大问题分解为小问题的规律，并且基于此写出递推公式，然后再推敲终止条件，最后将递推公式和终止条件翻译成代码
编写递归代码的关键是，只要遇到递归，我们就把它抽象成一个递推公式，不用想一层层的调用关系，不要试图用人脑去分解递归的每个步骤
递归与循环没有明显的边界，它是通过函数体来进行的循环
终止条件 递推公式
递归会利用栈保存临时变量，如果
哈希表(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比较类排序: 通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此也称为非线性时间比较类排序。
非比较类排序: 不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时 间下界，以线性时间运行，因此也称为线性时间非比较类排序。
排序算法
比较类排序
交换排序
冒泡排序
快速排序
插入排序
简单插入排序
希尔排序
选择排序
栈只支持两个基本操作：入栈push()和出栈pop()
用数组实现的栈，我们叫作顺序栈，用链表实现的栈，我们叫作链式栈
不管是顺序栈还是链式栈，我们存储数据只需要一个大小为n的数组就够了。在入栈和出栈过程中，只需要一两个临时变量存储空间，所以空间复杂度是O(1)
不管是顺序栈还是链式栈，入栈、出栈只涉及栈顶个别数据的操作，所以时间复杂度都是O(1)。
注意，这里存储数据需要一个大小为n的数组，并不是说空间复杂度就是O(n)。因为，这n个空间是必须的，无法省掉。所以我们说空间复杂度的时候，是指除了原本的数据存储空间外，算法运行还需要额外的存储空间。
最好情况时间复杂度是O
队列跟栈一样，也是一种操作受限的线性表数据结构
用数组实现的队列叫作 顺序队列，用链表实现的队列叫作 链式队列
最基本的操作有两个：入队enqueue()，放一个数据到队列尾部；出队dequeue()，从队列头部取一个元素
高性能队列Disruptor、Linux环形缓存，都用到了循环并发队列；Java concurrent并发包利用ArrayBlockingQueue来实现公平锁
