查找
顺序查找
按照顺序一个个比较,直到序列末尾
int seq_search(int array[], int n, int key){ int i; for(i = 0; i < n; i++) { if(key == array[i]) { return i; //查找成功 } } return -1; //查找失败}
二分查找
通过对一个有序数组中对元素依次比较,从而能实现对数级别时间复杂度的查找
根据左右指针计算出一个mid指针 如果mid指针处的元素等于目标值 则要查找的目标就是在这里
否则如果mid处的指针比目标值大 则右指针等于mid-1 否则左指针等于mid+1
然后重复上述操作 直到左指针大于右指针
int l = 0, r = a.length - 1;while (l <= r) { int mid = l + (r - l) / 2; if (a[mid].equals(target)) { return mid; } if (less(target, a[mid])) {// 要查找的元素在左边 r = mid - 1; } else if (greater(target, a[mid])) { // 要查找的元素在右边 l = mid + 1; }}return -1;
- 二分查找依赖于顺序表结构
- 二分查找针对有序数据
- 二分查找依赖于一整块内存的随机访问,对于过大无法在内存中分配空间的数据也不适合
这个算法在快速定位BUG的时候也挺好用,一分为二,确定问题在前端还是后端,再继续划分,确定问题在系统哪一层
时间轮
round时间轮
时间轮被划分为 8 个 slot,每个 slot 代表 1s,当前时针指向 2。假如现在需要调度一个 3s 后执行的任务,应该加入 2+3=5 的 slot 中;如果需要调度一个 12s 以后的任务,需要等待时针完整走完一圈 round 零 4 个 slot,需要放入第 (2+12)%8=6 个 slot
怎么区分每个任务是否需要立即执行,还是需要等待下一圈 round,甚至更久时间之后执行呢?所以我们需要把 round 信息保存在任务中。例如图中第 6 个 slot 的链表中包含 3 个任务,第一个任务 round=0,需要立即执行;第二个任务 round=1,需要等待 18=8s 后执行;第三个任务 round=2,需要等待 28=8s 后执行。所以当时针转动到对应 slot 时,只执行 round=0 的任务
分层时间轮
当上层的时间轮转完一圈时,下层的定时器就要增加一个刻度
假设我们的任务需要在每天的 7:30:20 秒执行一次。任务首先添加于小时级别时钟轮的第 7 号刻度上,当其轮询线程访问到第 7 号刻度时,就将此任务转移到分钟级别时钟轮的第 30 号刻度上。当分钟级别的时钟轮线程访问到第 30 号刻度,就将此任务转移到秒级别时钟轮的第 20 号刻度上。当秒级别时钟轮线程访问到第 20 号刻度时,最终会将任务交给异步线程负责执行
bitmap
位图通过数组下标来定位数据,所以访问效率非常高
1存在 => 0100002存在 => 0010001,2都存在 => 011000
布隆过滤器
一串数据通过n个散列函数将一个位图的n位设置为1,当要查询时,对数据进行散列 判断对应的n位是否都为1 若都为1, 则就是可能存在
所以布隆过滤器也没有足够的信息可以删除指定的key,为了应对缓存数据过期,可以采用定期重建的方法,重建完保持两个过滤器的双写,一段时间后,就把全部请求都给到较新的这个过滤器上,清除老的过滤器
布谷鸟过滤器
- 布谷鸟哈希:使用两个哈希函数对一个key进行哈希,得到桶中的两个位置,如果有空位,key就放在空位里,否则就要随机踢掉一个元素,踢出的元素再计算哈希找到相应的存储位置
哈希表的基本单位称为条目(entry)。 每个条目存储一个指纹(fingerprint),指纹指的是使用一个哈希函数生成的n位比特位
相比布隆过滤器,布谷鸟过滤器可以通过从哈希表删除相应的指纹删除插入的项,由于哈希的特性,是存在误删的可能的,同时,只要不发生桶溢出,在查询的时候就不会出现假阳
索引
功能性需求
- 索引的数据是格式化数据还是非格式化数据
- 索引的数据是静态数据还是动态数据
- 索引存储在内存还是硬盘
- 单值查找还是区间查找
- 单条件查找还是多条件组合查找
非功能性需求
- 对存储空间的消耗不能过大
- 考虑索引查询效率的同时,还要考虑索引的维护成本
索引常用数据结构
- 散列表
- 红黑树
- B+树
- 跳表
- 布隆过滤器