美文网首页
查询算法

查询算法

作者: 阔阔飞翔 | 来源:发表于2019-04-23 17:14 被阅读0次

1、二分查找

二分查找的时间复杂度是O(logn),查找数据的效率非常高。不过,并不是什么情况下都可以用二分查找,它的应用场景是有很大局限性的。那

什么情况下适合用二分查找,什么情况下不适合呢?

首先,二分查找依赖的是顺序表结构,简单点说就是数组。那二分查找能否依赖其他数据结构呢?比如链表。答案是不可以的,主要原因是二分查找算法需要按照下标随机访问元素。

其次,二分查找针对的是有序数据。二分查找对这一点的要求比较苛刻,数据必须是有序的。如果数据没有序,我们需要先排序。前面章节里我们讲到,排序的时间复杂度最低是O(nlogn)。所以,如果我们针对的是一组静态的数据,没有频繁地插入、删除,我们可以进行一次排序,多次二分查找。这样排序的成本可被均摊,二分查找的边际成本就会比较低。但是,如果我们的数据集合有频繁的插入和删除操作,要想用二分查找,要么每次插入、删除操作之后保证数据仍然有序,要么在每次二分查找之前都先进行排序。针对这种动态数据集合,无论哪种方法,维护有序的成本都是很高的。

所以,二分查找只能用在插入、删除操作不频繁,一次排序多次查找的场景中。针对动态变化的数据集合,二分查找将不再适用。

再次,数据量太小不适合二分查找。

2、跳表-链表

对于一个单链表来讲,即便链表中存储的数据是有序的,如果我们要想在其中查找某个数据,也只能从头到尾遍历链表。这样查找效率就会很低,时间复杂度会很高,是O(n)。

每两个结点提取一个结点到上一级,我们把抽出来的那一级叫作索引或索引层

如果我们现在要查找某个结点,比如16。我们可以先在索引层遍历,当遍历到索引层中值为13的结点时,我们发现下一个结点是17,那要查找的结点16肯定就在这两个结点之间。然后我们通过索引层结点的down指针,下降到原始链表这一层,继续遍历。这个时候,我们只需要再遍历2个结点,就可以找到值等于16的这个结点了。这样,原来如果要查找16,需要遍历10个结点,现在只需要遍历7个结点。

跟前面建立第一级索引的方式相似,我们在第一级索引的基础之上,每两个结点就抽出一个结点到第二级索引。现在我们再来查找16,只需要遍历6个结点了,需要遍历的结点数量又减少了。如图

Redis中的有序集合是通过跳表来实现的,严格点讲,其实还用到了散列表。不过散列表我们后面才会讲到,所以我们现在暂且忽略这部分。如果你去查看Redis的开发手册,就会发现,Redis中的有序集合支持的核心操作主要有下面这几个:

插入一个数据;

删除一个数据;

查找一个数据;

按照区间查找数据(比如查找值在[100, 356]之间的数据);

迭代输出有序序列。

其中,插入、删除、查找以及迭代输出有序序列这几个操作,红黑树也可以完成,时间复杂度跟跳表是一样的。但是,按照区间来查找数据这个操作,红黑树的效率没有跳表高。对于按照区间查找数据这个操作,跳表可以做到O(logn)的时间复杂度定位区间的起点,然后在原始链表中顺序往后遍历就可以了。这样做非常高效。

当然,Redis之所以用跳表来实现有序集合,还有其他原因,比如,跳表更容易代码实现。虽然跳表的实现也不简单,但比起红黑树来说还是好懂、好写多了,而简单就意味着可读性好,不容易出错。还有,跳表更加灵活,它可以通过改变索引构建策略,有效平衡执行效率和内存消耗。

不过,跳表也不能完全替代红黑树。因为红黑树比跳表的出现要早一些,很多编程语言中的Map类型都是通过红黑树来实现的。我们做业务开发的时候,直接拿来用就可以了,不用费劲自己去实现一个红黑树,但是跳表并没有一个现成的实现,所以在开发中,如果你想使用跳表,必须要自己实现。

3、散列表

散列表用的是数组支持按照下标随机访问数据的特性,所以散列表其实就是数组的一种扩展,由数组演化而来。可以说,如果没有数组,就没有散列表。

散列表用的就是数组支持按照下标随机访问的时候,时间复杂度是O(1)的特性。我们通过散列函数把元素的键值映射为下标,然后将数据存储在数组中对应下标的位置。当我们按照键值查询元素时,我们用同样的散列函数,将键值转化数组下标,从对应的数组下标的位置取数据。

散列冲突

再好的散列函数也无法避免散列冲突。那究竟该如何解决散列冲突问题呢?我们常用的散列冲突解决方法有两类,开放寻址法和链表法。

开放寻址法的核心思想是,如果出现了散列冲突,我们就重新探测一个空闲位置,将其插入。

链表法是一种更加常用的散列冲突解决办法,相比开放寻址法,它要简单很多。我们来看这个图,在散列表中,每个“桶(bucket)”或者“槽(slot)”会对应一条链表,所有散列值相同的元素我们都放到相同槽位对应的链表中。

工业级散列表举例分析

java中的HashMap这样一个工业级的散列表

(1).初始大小

HashMap默认的初始大小是16,当然这个默认值是可以设置的,如果事先知道大概的数据量有多大,可以通过修改默认初始大小,减少动态扩容的次数,这样会大大提高HashMap的性能。

(2).装载因子和动态扩容

最大装载因子默认是0.75,当HashMap中元素个数超过0.75*capacity(capacity表示散列表的容量)的时候,就会启动扩容,每次扩容都会扩容为原来的两倍大小。

(3).散列冲突解决方法

HashMap底层采用链表法来解决冲突。即使负载因子和散列函数设计得再合理,也免不了会出现拉链过长的情况,一旦出现拉链过长,则会严重影响HashMap的性能。于是,在JDK1.8版本中,为了对HashMap做进一步优化,我们引入了红黑树。而当链表长度太长(默认超过8)时,链表就转换为红黑树。我们可以利用红黑树快速增删改查的特点,提高HashMap的性能。当红黑树结点个数少于8个的时候,又会将红黑树转化为链表。因为在数据量较小的情况下,红黑树要维护平衡,比起链表来,性能上的优势并不明显。

相关文章

  • 查询算法

    1、二分查找 二分查找的时间复杂度是O(logn),查找数据的效率非常高。不过,并不是什么情况下都可以用二分查找,...

  • Android查询算法

    一、获取最小值 二、递归数兔子 三、查找文件 四、二分查找(1)使用递归 (2)二分查找 五、字符串旋转

  • 仿淘宝多商品SKU组合(Android版)

    本文算法参考淘宝SKU查询算法,本文主要在于功能的实现,存在一些瑕疵,多多包涵。 查询原理这里就不做过多的赘述了,...

  • 二分查找

    二分查询算法 马戏团人塔

  • mysql中简单安全处理和分页算法

    简单分页算法 //查询总条数$sql = "select count(*) from tablename"...

  • Python算法

    注:采转归档,自己学习查询使用 Python算法:基础知识Python算法:Counting 101Python算...

  • 浅谈算法和数据结构

    注:采转归档,自己学习查询使用 浅谈算法和数据结构: 一 栈和队列浅谈算法和数据结构: 二 基本排序算法浅谈算法和...

  • Redis学习--阻塞

    API或数据结构使用不合理 慢查询查询慢查询日记,发现慢查询.1)修改为低算法度的命令,如hgetall改为hmg...

  • 密码学(二)- MD5 & HMAC

    一、MD5 MD5加密算法反向查询网站网站简介:本站针对md5等全球通用公开的加密算法进行反向查询,建立了密文对应...

  • 核心技术-索引

    1.3索引算法的演变 1.3.1 BTREE算法,由来 BTREE讲究的是查找数据的平衡,让我们的查询可以快速锁定...

网友评论

      本文标题:查询算法

      本文链接:https://www.haomeiwen.com/subject/kuhbgqtx.html