查找算法总结

常见的查找算法有7种

1. 顺序查找

顺序查找对序列没有排序要求
ASL = 1/n(1+2+3+…+n) = (n+1)/2;
T((n+1)/2)复杂度为 O(n)

2. 折半查找

也叫二分查找,必须是有序的序列。

int binarySearch(int[] a, int key) {
    int low = 0;
    int high = a.length - 1;
    while (low <= high) {
        mid = (low + high) / 2;
        if (a[mid] == key) 
            return mid;
        else if (a[mid] < key)
            low = mid + 1;
        else 
            high = mid - 1;
    }
    // 不存在
    return -1;
}

有序后,过程可以转化为一颗二叉查找树,复杂度为O(log2n)

3. 插值查找

是对折半查找的一种习惯优化,就是不每次都是折半,即索引移动一半。而是根据值的差和索引差的比来权衡索引移动多少。
翻字典的例子举得很好,想找apple,肯定一开始不是翻到字典中间,而是知道了值a到M的距离差和页面索引差的比。会自适应

修改折半查找代码这句即可

// 折半
mid = (low + high) / 2;
// 等价于 mid = low + (high - low) / 2;

// 插值
mid = low + [(high - low) / (a[high] - a[low])] * (key - a[low])

4. 斐波那契查找

5. 树查找

树有很多,二叉查找树,AVL二叉平衡树,红黑树,B树,B+树等

AVL树即若左右子树存在,那么两者高度差绝对值小于1,而且左右子树也是平衡树。主要是为了解决二叉树退变为单链表的可能。更“匀称”化。

红黑树:红黑树并不满足AVL条件,是一般二叉查找树的变形,增加颜色间隔特点。红黑树是用非严格的平衡来换取增删节点时候旋转次数的降低,任何不平衡都会在三次旋转之内解决,而AVL是严格平衡树,因此在增加或者删除节点的时候,根据不同情况,旋转的次数比红黑树要多。 所以红黑树的插入删除效率更高。

B-树,也就是balance-树,多路查找树,主要是用在磁盘文件系统查找上。

B树

m阶的B树的一些性质:

  1. 每个节点最多有m棵子树(即最多m-1个关键字)
  2. 有多层,跟结点至少两个子树。
  3. 除根之外,任何非终结点至少有m/2棵子树。

B+树,是B树的一种变形,主要用在数据库索引上。

B+树
m阶B+树和B树的差异是:

  1. 有n棵子树的节点含有n个关键字
  2. 节点的关键字会重复传递下去,因为B+非叶子结点不包含信息,只是单纯的索引。而B树每个节点都有信息,查找到就返回了,B+树要到叶子节点。
  3. 每个节点最大的关键字,在其叶子节点也是最大。B+树可以看作是没有“右边拓展”。
  4. B+树叶子节点本身依关键字自小而大顺序链接。

6. 分块查找

7. hash表查找

常见的就是Map,就是设计一个大数据和一个hash函数,hash(key)映射到索引的位置存储。如果没有hash冲突的话,查找过程就是做一次hash计算而已,复杂度O(1)。

hash冲突解决方法:开放地址法和拉链法

开放地址法分为:

  1. 线性探测法: 即f(key + di) = hash的di是增幅为1的。直到找到空桶位置
  2. 二次探测法:f(key + di^2)
  3. 随机探测法:三种方法都是对di的取法有分别而已。适合不同情况。

拉链法:
使用一个单链表把冲突的串起来,桶的位置为表头。hashmap的put方法如是。先判断key是否为null, hashmap有专门的null存储。然后找到数组索引,从表头遍历,key和hash一样替换value。否则作为新表头放到桶处,next节点指向原表头。

jdk1.8后,解决冲突方法为单链表结合红黑树。短的时候使用单链表,长度达到一定改为红黑树。

参考

七大查找算法


  转载请注明: Chgl16 查找算法总结

 上一篇
title: Java8新特性date: 2019-07-12 22:50author: chgl16summary: Java8的各种新特性,以及常用的Lambda表达式tag: Lambdacategories: Java img:
2019-08-05 chgl16
下一篇 
秒杀系统流程及并发优化分析 秒杀系统流程及并发优化分析
流程分析之前看了下慕课网的秒杀系统,也动手实战过。分析下常见的秒杀抢购和抢红包系统流程和架构优化。提供给用户的前端页面主要有商品列表页和对应的详情页。登录用户信息这里只是使用了cookie。没有另外数据库层面的存储。 1.列表页列表页面
2019-07-19
  目录