数据结构与算法(五)查询

很多时候,我们会比较在意查询的时间,因为这是用户最常使用的功能,并且是实时的需求,非常影响用户体验,以下是各种数据结构查询的效率,我们可以看到平衡二叉树等查找效率比较高,其实这是将时间前移了,因为平衡二叉树本身就是有序的,相当于已经对数据进行了一个排序,我们可以看到插入构造这个树的时间LOG(N)。

image

一.无序数据基础查找

像单链表这种无序队列,插入的时候很快的,直接加到末尾就可以,但是其查找确实耗时,使用了直接查找法。

所以为了加速查找的速度,需要将数据预先进行排序,一般就是生成的 时候就进行排序,比如数据库表加索引,构造二叉树,哈希表存储数据,这样在这些有序数据基础上进行数据查找就快多了,虽然在构造的时候会消耗时间,甚至让总时间都增加了,但是,有什么关系呢。

二.有序数据查找

无序数据查找效率比较慢,所以一般查找前都会排序,分担一部分的压力。

折半查找法

适用场景:针对已排序序列,并且只适用于顺序存储结构的序列,这样才能O(1)找到其中间值。但是这样一来,其插入,删除会变得比较低效,鱼熊不可兼得。

B树(二叉查找树)算法

其查找效率与树的深度有关。

HASH查找

算法思想:哈希的思路很简单,如果所有的键都是整数,那么就可以使用一个简单的无序数组来实现:将键作为索引,值即为其对应的值,这样就可以快速访问任意键的值。这是对于简单的键的情况,我们将其扩展到可以处理更加复杂的类型的键。

算法流程:

1)用给定的哈希函数构造哈希表;

2)根据选择的冲突处理方法解决地址冲突;

常见的解决冲突的方法:拉链法和线性探测法。 详细的介绍可以参见:  哈希表 。

3)在哈希表的基础上执行哈希查找。

这也是用空间换时间的例子之一。所以哈希表是查询效率的极致了。但是要解决好健冲突问题,比如拉链法,相当于将有共同哈希值的数据存储到一个链上,哈希值索引指向这个链,如果链COUNT>1,则再在链上顺序查找,这也有分治法的应用效果,基本上std::map 这种 kv存储结构就是哈希表的应用。这还可以衍生出进行大数据外排查找Top K问题。

数组的特点是:寻址容易,插入和删除困难;而链表的特点是:寻址困难,插入和删除容易。综合两者特性,设计一种寻址容易,插入删除也容易的数据结构,如拉链法实现的哈希表。

拉链法实现的哈希表应该也算是一个分块查找,索引查找的实现方式

分块查找(索引查找)

分块查找又称索引顺序查找,它是顺序查找的一种改进方法。

算法思想: 将n个数据元素”按块有序”划分为m块(m ≤ n)。每一块中的结点不必有序,但块与块之间必须”按块有序”;即第1块中任一元素的关键字都必须小于第2块中任一元素的关键字;而第2块中任一元素又都必须小于第3块中的任一元素,……

这种也适合使用并行进行查找。

算法流程:

step1 先选取各块中的最大关键字构成一个索引表;

step2 查找分两个部分:先对索引表进行二分查找或顺序查找,以确定待查记录在哪一块中;然后,在已确定的块中用顺序法进行查找。