- 迭代
- 利用哈希表Map存value和index
应用：LRU 缓存
- 迭代+双指针，哨兵头节点-1
- 迭代+双指针，pre指针在前，cur指针为null，pre指针一直指向cur
- 递归，f(n) = f(n-1) + f(1)，递：头节点和剩余节点的解决方式，归：head.next.next = head; head.next = null;
- 快慢指针，fast.next.next == low.next;
应用：函数调用、浏览器前进后退
- 栈，左闭合进 右闭合出
应用：阻塞队列、并发队列
冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较，看是否满足大小关系要求。如果不满足就让它俩互换。一次冒泡会让至少一个元素移动到它应该在的位置，重复 n 次，就完成了 n 个数据的排序工作。
插入算法的核心思想是取未排序区间中的元素，在已排序区间中找到合适的插入位置将其插入，并保证已排序区间数据一直有序。重复这个过程，直到未排序区间中元素为空，算法结束。
选择排序每次会从未排序区间中找到最小的元素，将其放到已排序区间的末尾。
我们先把数组从中间分成前后两部分，然后对前后两部分分别排序，再将排好序的两部分合并在一起，这样整个数组就都有序了。
如果要排序数组中下标从 p 到 r 之间的一组数据，我们选择 p 到 r 之间的任意一个数据作为 pivot（分区点）。
将要排序的数据分到几个有序的桶里，每个桶里的数据再单独进行排序。桶内排完序之后，再把每个桶里的数据按照顺序依次取出，组成的序列就是有序的了。
当要排序的 n 个数据，所处的范围并不大的时候，比如最大值是 k，我们就可以把数据划分成 k 个桶
基数排序对要排序的数据是有要求的，需要可以分割出独立的“位”来比较，而且位之间有递进的关系，如果 a 数据的高位比 b 数据大，那剩下的低位就不用比较了。
二分查找针对的是一个有序的数据集合，查找思想有点类似分治思想。每次都通过跟区间的中间元素对比，将待查找的区间缩小为之前的一半，直到找到要查找的元素，或者区间被缩小为 0。
应用：Redis 中的有序集合（Sorted Set）
比较：
- 按照区间来查找数据这个操作，红黑树的效率没有跳表高
- 跳表更容易代码实现
- 红黑树比跳表的出现要早一些，很多编程语言中的 Map 类型都是通过红黑树来实现的
应用：HashTable
解决散列冲突：
- 开放寻址法 当数据量比较小、装载因子小的时候，适合采用开放寻址法。这也是 Java 中的ThreadLocalMap使用开放寻址法解决散列冲突的原因。
- 链表法 基于链表的散列冲突处理方法比较适合存储大对象、大数据量的散列表，而且，比起开放寻址法，它更加灵活，支持更多的优化策略，比如用红黑树代替链表。
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
public int hashCode() {
int h = hash;
if (h == 0 && value.length > 0) {
char val[] = value;
for (int i = 0; i < value.length; i++) {
h = 31 * h + val[i];
}
hash = h;
}
return h;
}
应用：sha1、md5
具体场景：
-
唯一标识
-
数据完整性和正确性
-
安全加密
-
散列函数
-
负载均衡
-
数据分片
-
分布式存储
应用：二叉查找树