数据结构和算法——散列表的性能分析(开放地址法的查找性能、期望探测次数与装填因子的关系、分离链接法的查找性能)

目录

开放地址法的查找性能

线性探测法

平方探测法和双散列探测法

期望探测次数与装填因子的关系

分离链接法的查找性能

总结


散列表的性能分析

  • 平均查找长度(ASL)用来度量散列表查找效率:成功、不成功
  • 关键词的比较次数,取决于产生冲突的多少,影响产生冲突多少有以下三个因素
  1. 散列函数是否均匀;
  2. 处理冲突的方法;
  3. 散列表的装填因子\alpha

开放地址法的查找性能

线性探测法

可以证明,线性探测法的期望探测次数满足下列公式:

p=\frac{1}{2}\left [ 1+\frac{1}{​{(1-\alpha )}^2} \right ](对插入和不成功查找而言)

p=\frac{1}{2}\left ( 1+\frac{1}{1-\alpha } \right )(对成功查找而言)


\alpha =0.5时,

  • 插入操作和不成功查找的期望ASLu=0.5*\left [ 1+ \frac{1}{​{(1-0.5)}^2}\right ]=2.5
  • 成功查找的期望ASLs=0.5*\left ( 1+\frac{1}{1-0.5} \right )=1.5

在实际问题中,

H(key)0123456789101112
key1130477299845420
冲突次数060010313

\alpha =9/13=0.69,于是,经过公式计算得:

ASLu=5.70次,ASLs=2.11(实际计算ASLs=2.56)

平方探测法和双散列探测法

可以证明,平方探测法和双散列探测法探测次数满足下列公式:

p=\frac{1}{1-\alpha }(对插入和不成功查找而言)

p=-\frac{1}{\alpha }\ln(1-\alpha )(对成功查找而言)


\alpha =0.5时,

  • 插入操作和不成功查找的期望ASLu=\frac{1}{1-0.5}=2
  • 成功查找的期望ASLs=-\frac{1}{0.5}\ln (1-0.5)\approx 1.39

在实际问题中,

H(key)012345678910
key1130204784729954
冲突次数033020100

\alpha =9/11=0.82,于是,通过公式计算得:

ASLu=5.56次,ASLs=2.09次(实际计算ASLs=2)。

期望探测次数与装填因子的关系

  •  当装填因子\alpha < 0.5的时候,各种探测法的期望探测次数都不大,也比较接近。
  • 随着\alpha的增大,线性探测法的期望探测次数增加较快,不成功查找和插入操作的期望探测次数比成功查找的期望探测次数要大
  • 合理的最大装填因子应该不超过0.85

分离链接法的查找性能

所有地址链表的平均长度定义成装填因子\alpha\alpha有可能超过1。

不难证明:其期望探测次数p为:

p=\alpha +e^{-\alpha }(对插入和不成功查找而言)

p=1+\frac{\alpha }{2}(对成功查找而言)


\alpha =1时,

  • 插入操作和不成功查找的期望ASLu=1+e^{-1}=1.37
  • 成功查找的期望ASLs=1+\frac{1}{2}=1.5

在实际问题中,

前面例子14个元素分布在11个单链表中,所以\alpha =14/11\approx 1.27,故

期望ALSu=1.55次,ASLs=1.64次(实际计算ASLs为1.36).

总结

  • (优点)选择合适的h(key),散列表的查找效率期望是常数O(1),它几乎与关键字的空间的大小n无关!也适合于关键字直接比较计算量大的问题
  • 它是以较小的\alpha为前提。因此,散列方法是以空间换时间
  • (缺点)散列方法的存储对关键字是随机的,不便于顺序查找关键字,也不适用与范围查找,或最大值最小值查找。

开放地址法

  • (优点)散列表是一个数组,存储效率高,随机查找
  • (缺点)散列表有“聚集”现象

分离链接法

  • 散列表顺序存储和链式存储的结合,链表部分的存储效率和查找效率都比较低
  • (优点)关键字删除不需要“懒惰删除”法,从而没有存储“垃圾”
  • (缺点)太小的\alpha可能导致空间浪费,大的\alpha又将付出更多的时机代价。不均匀的链表长度导致时间效率的严重下降。

    end


    学习自:MOOC数据结构——陈越、何钦铭

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://xiahunao.cn/news/1381963.html

如若内容造成侵权/违法违规/事实不符,请联系瞎胡闹网进行投诉反馈,一经查实,立即删除!

相关文章

Dataloader数据集的制作

数据集Dataloader制作 如何自定义数据集&#xff1a; 1.数据和标签的目录结构先搞定(得知道到哪读数据)2.写好读取数据和标签路径的函数(根据自己数据集情况来写)3.完成单个数据与标签读取函数(给dataloader举一个例子) 咱们以花朵数据集为例&#xff1a; 原来数据集都是以…

RabbitMQ 消息队列(Spring boot AMQP)

文章目录 &#x1f370;有几个原因可以解释为什么要选择 RabbitMQ&#xff1a;&#x1f969;mq之间的对比&#x1f33d;RabbitMQ vs Apache Kafka&#x1f33d;RabbitMQ vs ActiveMQ&#x1f33d;RabbitMQ vs RocketMQ&#x1f33d;RabbitMQ vs Redis &#x1f969;linux docke…

Android App消息推送 实现原理

https://www.jianshu.com/p/b61a49e0279f 1.消息推送的实质 实际上&#xff0c;是当服务器有新消息需推送给用户时&#xff0c;先发送给应用App&#xff0c;应用App再发送给用户 2. 作用产品角度&#xff1a;功能需要&#xff0c;如&#xff1a;资讯类产品的新闻推送、工具类…

App消息推送 实现原理

1.消息推送的实质 实际上&#xff0c;是当服务器有新消息需推送给用户时&#xff0c;先发送给应用App&#xff0c;应用App再发送给用户 2. 作用 产品角度&#xff1a;功能需要&#xff0c;如&#xff1a;资讯类产品的新闻推送、工具类产品的公告推送等等 运营角度&#xff1a;活…

浏览器及app消息推送

消息推送 什么是消息推送PC端的实现方法1:Notification方法2&#xff1a;pushjs APP端实现打包设置 什么是消息推送 消息推送可以存在于浏览器端&#xff0c;也存在APP端。浏览器的推送&#xff0c;会在电脑通知中显示&#xff0c;app中显示在通知栏 PC端的实现 方法1:Notif…

IOS推送-pushy

iOS 引入jar包创建APNSConnect进行发送报错对照表 引入jar包 创建APNSConnect 创建APNSConnect&#xff0c;与APNs进行链接 public class APNSConnect { private static ApnsClient apnsClient null;public static ApnsClient getAPNSConnectP8(String path,String teamId,S…

unipush+java+个推实现app消息推送

“ 你现在的气质里&#xff0c;藏着你走过的路&#xff0c;读过的书&#xff0c;和爱过的人。 ” 整体还是比较简单地&#xff0c;就是有一些需要注意的地方&#xff0c;很多问题官方文档里面也写了&#xff0c;这里总结一下 对于安卓&#xff0c;谷歌本来有专门的推送通道&…

uniapp - App 超详细消息推送功能实现,从 0-1 实现官方 unipush 推送全步骤稳定性毋庸置疑(附带详细的可运行示例源码和注释,保证 100% 完美接入)苹果安卓手机

效果图 网上的教程太乱用不了,无法改造成自己想要的效果。 在uniapp中开发的app(安卓苹果),使用 unipush 官方推送,从0-1实现完整过程及功能开发。 你可以直接复制示例源码,跟着教程一步步配置,注释详细! 准备 消息

Android 项目必备(三十八)-->APP 消息推送

文章目录 前言推送的实现方式1. C2DM2. 轮询3. SMS信令推送4. MQTT协议5. XMPP协议6. 使用第三方平台 Android 中 MQTT 的使用1. 集成2. 具体代码3. 项目地址 前言 今天来讲讲推送这件小事&#xff0c;事虽小&#xff0c;要做好却不容易。 推送难&#xff0c;难于上青天。 我们…

APP消息推送(APP Push)解决方案-服务端工作逻辑和实现

一、APP 推送概述&#xff1a; App推送消息是我们常见的一种app消息提醒方式。 我们的实现需要第三方的支持&#xff0c;实现方式是后台通过接口将Push请求发送至第三方&#xff0c;第三方实现在App所在设备上的推送。 二、APP推送后台处理逻辑&#xff1a; 在与推送平台交互时…

app消息推送的详细实现教程

实现的主要思想 app实现消息推送&#xff0c;利用的是第三方的个推平台&#xff0c;后端将需要推送的内容通过第三方个推服务器传递给手机端。 具体前端打包配置 根据上图可知&#xff0c;采用的打包软件是Hbuilder X,在模块配置的时候&#xff0c;勾选push模块中的uniPush。…

App消息推送的原理

文章目录 1. 基本概念2. iOS和Android消息推送原理对比2.1 iOS2.1.1 基本原理2.1.2 优劣势 2.2 Android2.2.1 基本原理2.2.2 优劣势 3. Android消息推送原理3.1 操作系统有自身的消息推送功能&#xff08;系统级别&#xff09;3.2 三种基本的推送方式&#xff1a;Push、Pull 和…

php实现app消息推送

如何用php实现APP消息推送 现在有很多的消息推送厂商&#xff0c;比如阿里云的消息推送&#xff0c;极光推送&#xff0c;融云的消息推送。他们的原理都是把sdk内置在app里面&#xff0c;达到消息推送的目的&#xff0c;通过一张图来了解一下&#xff0c;看不懂不要紧&#xf…

Android,ios,安卓app推送消息通知,java后台向手机推送app的通知教程

文章目录 一、业务介绍1.1 产品简介1.2 名词解释1.3 消息推送流程 二、应用创建三、客户端 SDK 集成3.1 Android3.2 iOS 四、服务端推送4.1 服务端消息下发流程&#xff08;必读&#xff09;4.2 开发者中心后台4.3 推送代码 五、参数说明 一、业务介绍 1.1 产品简介 个推是商…

App消息推送概述

消息推送介绍 消息推送&#xff08;Push&#xff09;&#xff0c;是指从云端服务器到手机终端的消息推送通道&#xff0c;运营人员可以通过自己产品后台或者第三方推送通道对用户移动设备进行主动的消息推送。通过消息推送&#xff0c;目标用户可以在移动设备通知和状态栏看到…

PushDeer:一种无APP的通知推送解决方案

概述 去年六月&#xff0c;我曾写下一篇博客介绍如何 借助 ServerChan 实现个人微信通知推送&#xff0c;在那篇文章中介绍了 ServerChan 及其使用方法&#xff0c;总的来说&#xff0c;对于简单的通知需求&#xff0c;使用 ServerChan 是非常简单有效的。但是实际使用起来&…

一文让你知道关于App推送那些事

推送相关介绍 在用户未打开App时&#xff0c;服务端向用户推送服务器最新的消息数据&#xff0c;称为推送。消息推送在移动开发中用到的场景非常多&#xff0c;比如典电商类app的商品促销活动&#xff0c;资讯类的app的新闻推送等等。在实际开发中&#xff0c;我们常常会根据产…

关于ISO27701隐私信息安全管理体系介绍

01 什么是ISO27701 ISO27701是对ISO27001信息安全管理和ISO27002安全控制的隐私扩展&#xff0c;全称《安全技术—扩展ISO27001和ISO27002的隐私信息管理—要求与指南》&#xff0c;是ISO标准委员会以ISO 27001为基准&#xff0c;以ISO27552为蓝本&#xff0c;建立发布的隐私…

双向循环链表、dancing links

目录 双向循环链表 力扣 426. 将二叉搜索树转化为排序的双向链表 十字交叉双向循环链表&#xff08;dancing links&#xff09; 精确覆盖问题 dancing links X算法&#xff08;V1递归版&#xff09; POJ 3740 Easy Finding 数独 X算法优化 X算法&#xff08;V2非递归…

jpg照片太大怎么压缩变小?jpg如何缩小图片大小kb?

我们平时在接收过多的jpg格式图片的时候&#xff0c;越大的图片虽然越清晰&#xff0c;但是接收和储存起来就非常不方便&#xff0c;那么有没有什么办法可以将jpg图片压缩呢&#xff1f;其实现在可以通过在线图片处理工具来完成jpg压缩&#xff08;https://www.yasuotu.com/jpg…