如何更快速地查找

一、概述

查找算法在计算机程序设计中占据着主要的核心位置，查找算法的效率直接影响着计算机程序设计与开发的结果与速度。本章主要会讲到顺序查找、二分查找、索引查找和哈希查找这四种查找算法以及效率分析。掌握了相关查找算法，不管是在代码编程计算机技术上面，还在日常生活中都会有很大的用处。

在分析查找算法的效率时，我们不仅会从空间复杂度和时间复杂度上进行分析，还会使用到平均查找长度（Average Search Length，ASL）来分析，平均查找长度为：

ASL = P1C1 + P2C2 + ... + PnCn

其中，Pi 为查找第 i 个元素的概率，Ci 为第 i 个元素需要比较的次数。

二、顺序查找

顺序查找是指从表中指定位置开始，沿某个方向将记录的关键字与给定值比较，若某个记录的关键字和给定值相等，则查找成功，反之，若找完整个表没有找到与给定值相等的记录，则查找失败。简单的讲，顺序查找就是从头到尾按顺序查找。

简单实现代码如下：

public static int iterationSearch(int[] array, int a) {
    for (int i = 0; i < array.length; i++) {
        if (a == array[i]) {
            return i;
        }
    }
    return -1;
}

从前面可知，顺序查找的空间复杂度为 O(1)，时间复杂度最好情况为 O(1)，最坏情况为 O(n)，平均情况为 O(n)，对于具有 n 个记录的顺序表，查找成功时的ASL为：

ASL = ∑ PiCi

对于顺序表中 Ci = n - i + 1，假设查找每个记录的概率相等，即 Pi = 1/n ，则可以得出：

ASL = 1/n ∑ (n - i + 1)  = (n + 1)/2

三、二分查找

如果顺序表的记录是有序的，则可以使用二分查找算法来查找，即每次与表的中间记录进行比较，若相等，则查找成功，若小于中间值，则只可能在表的前半部分，若大于中间值，则只可能在表的后半部分，这样下去，每比较一次，查找范围会缩小一半，直到查找到记录或记录不在表中。

简单代码实现如下：

public static int binarySearch(int[] array, int a) {
    int start = 0;
    int end = array.length - 1;
    int mid;
    while (start <= end) {
        mid = (start + end) / 2;
        if (array[mid] < a) {
            start = mid + 1;
        } else if (array[mid] > a) {
            end = mid - 1;
        } else {
            return mid;
        }
    }
    return -1;
}

二分查找的时间复杂度为 O(log n)，假设查找概率相等，可以得出：

ASL = 1/n ∑ Ci = 1/n (∑ j × 2 j-1) = (n + 1)/n log2(n + 1) - 1

当 n 很大时，可以得出近似结果：

              ASL ≈ log2(n + 1) - 1

所以我们可以得出，在有序表里使用二分查找的效率是很高的。

四、索引查找

当我们数据量很大且无序时，如何设计查找算法才能更快的查找到数据呢？就像我们查字典一样，如果不看前面的目录，而一页一页的去翻（顺序查找），那是多么可怕。当数据太多，而又杂乱无章的时候，可以考虑使用建立索引来进行查找，一般使用索引的方法的步骤是：

• 先分析数据规律，建立索引
  
• 再根据索引进行快速定位
  
• 在定位的地方进行细致搜索

在根据索引查找表时，定位操作不会去匹配整行数据，而是只匹配某一个或几个列的值，假设我们只匹配一个列来确定记录的位置，把这个列称为关键字（Key），后面我们列举两种常见的索引类型来由浅入深地讲解原理和使用。

1. 稠密索引

如果我们要通过关键字来查询数据记录，可以建立一个索引表，在该索引表中只维护原数据表中的关键字，并排列有序，每条索引表的记录中存在一个指向原数据表记录的指针，这样子做的话，当我们需要通过关键字来查询记录时，可以先从索引表中进行查找，找到该数据的索引记录，然后通过指针找到数据表中的记录，因为索引表是有序的，所以查询效率很高（对有序表进行二分查找）。

在前面创建的索引表中，数据表中的每条记录都对应有一个索引记录，这种索引我们把它叫做稠密索引。

2. 稀疏索引

在使用稠密索引时，每一条数据记录都需要对应存在索引记录，所以需要维护一份与数据表大小相等的索引表，而且为了减少对无效数据IO的操作，我们可以把数据表中的数据分成若干个块，而且要保证块之间是有序的，块内的数据可以无序，然后我们在索引表中关键字只记录每个块中的最大值，指针指向每个块中第一个元素。如下图，比如我们需要查找关键字为18的记录，步骤如下：

• 从索引表中定位块，因为有 12<18<=26 所以它有可能存在于第2块中
  
• 从第2块中查找数据，最终查找到18的位置

这样创建的索引表，索引记录对应数据表中的一个块，这种索引叫做稀疏索引。

在块之间是有序的，所有我们可以对索引表通过顺序查找或二分查找来确定块的位置，然而块内数据是无序的，所以可以通过顺序查找或者哈希查找来定位数据记录，不管是使用什么方式查找，可以得知索引查找的效率与索引表和块内的查找方式有关，因此可知：

ASL = ASL(索引表) + ASL(块内)

再扩展一下我们的思维，如果把索引表再分块，按照前面所讲的方法给索引表再建立索引表，这样就会得到多层的稀疏索引，而且可以通过上层的索引表来定位下一层索引表，以此类推，最终查找到记录。

由多层索引表会构建成的整个索引表的树（关于树的数据结构后面会讲到），我们把最顶层的索引称作整个索引树的根（Root），此时树上的非叶子结点只存储索引，而叶子结点存储数据，假设我们按照一定规则建立索引表，在插入或者删除每一条记录时，索引树都会实现自动平衡，而且每个叶子结点都有相邻子叶子结点的指针，这就是传说中的B+树。

五、哈希查找

前面讲了顺序查找、二分查找和索引查找，现在来讲一种查询效率更高的算法，一般情况下，在关键字（key）与记录在表中的存储位置之间建立一个函数关系，以函数 H(key) 作为关键字 key 的记录在表中的位置，我们把这个函数叫做哈希函数。而当我们需要通过关键字查找记录时，只需要通过哈希函数做逆计算来取得记录的存储位置，时间复杂度为 O(1)。

我们在使用哈希查找时，会存在不同的关键字使用哈希函数计算生成的地址会一样，这要两条记录的哈希地址就会产生“冲突”，即当 key1!=key2 时 H(key1)==H(key2)，我们把这种现象叫做哈希碰撞，因为很难找到一个不产生冲突的哈希函数，只能使冲突尽可能少。因此，设计一个好的哈希函数需要做到：计算简单、冲突少。

1. 哈希函数

例如我们存在一个解放后每年出生人数的统计表，把出生年份当作关键字，然后使用下面哈希函数计算出哈希地址：

H(key) = key + (-1948)

此时表对应哈希地址如下：

我们在使用哈希查找时，会存在不同的关键字使用哈希函数计算生成的地址会一样，这要两条记录的哈希地址就会产生“冲突”，即当 key1!=key2 时 H(key1)==H(key2)，我们把这种现象叫做哈希碰撞，因为很难找到一个不产生冲突的哈希函数，只能使冲突尽可能少。因此，设计一个好的哈希函数需要做到：计算简单、冲突少。

1. 哈希函数

例如我们存在一个解放后每年出生人数的统计表，把出生年份当作关键字，然后使用下面哈希函数计算出哈希地址：

H(key) = key + (-1948)

此时表对应哈希地址如下：

常见解决冲突的方法有：开放地址法、再哈希法、链地址法、公共溢出区法等，其他方法读者可以自己找资料扩展。

六、总结

四种查找算法对比

数据库中B+树索引与哈希索引的区别：

根据前面的分析可以得到，B+树更适合范围查找，而且支持多列联合索引的最左匹配规则。哈希索引更适合等值查找，但不支持范围查找，也没办法利用索引排序，在存在大量重复键值的情况下，哈希索引效率也是极低的，因为要处理哈希碰撞问题。