Python数据结构与算法——散列(Hash)

Stella981
• 阅读 820

Python数据结构与算法——散列(Hash)

点击上方“蓝字”关注我们

散列(Hash)


对于一组数据项,顺序查找的时间复杂度是O(n),二分查找是O(logn),而对于散列的数据结构,查找算法的时间复杂度降到了O(1)

Python数据结构与算法——散列(Hash)

散列表(hash table)


散列表又叫“哈希表”,是一种数据集,其中数据项的存储方式有利于快速的进行查找操作

散列表中每一个用于存储数据项的存储位置加作“槽(slot)”,每一个槽都对应着一个唯一的名字

在python中与之对应的数据结构就是字典

{'a': 1, 'b': 2, 'c': 3}

Python数据结构与算法——散列(Hash)

散列函数(hash function)


散列函数:实现从数据项到存储槽名称的转换

有一种常用的散列函数就是“求余数”:将数据项除以散列表的大小,得到的余数作为槽名

为什么求余数比较常见呢?因为散列函数返回的槽号必须在散列表的范围内,所以一般会对散列表大小求余

当数据项都保存到散列表后,查找就可以直接通过槽号直接查询了,算法时间复杂度O(1)

Python数据结构与算法——散列(Hash)

冲突(collision)


散列函数在计算槽位的时候,不同数据项理应计算出不同的槽位,但是有时候会出现不同数据项计算出相同槽位(即冲突)

例如:大小11的散列表,散列函数“求余数”,77和44计算出的槽位都是0号!出现了冲突

对于散列表而言,最主要的讨论话题就是解决冲突

Python数据结构与算法——散列(Hash)

完美散列函数


完美散列函数:若给定一组数据项,完美散列函数可以把每一个数据项映射到不同的槽中

对于固定的一组数据,总是能想办法设计出近似完美的散列函数

好的散列函数具备的特征:

  • 冲突少(每个数据项的槽位都不同)

  • 计算难度较低(计算槽位的过程较容易)

  • 充分分散数据项(节约空间)

散列技术的应用


散列技术除了在散列表中安排数据项的存储位置,还在许多信息处理领域有较多的应用

由于散列函数能够对任何不同的数据生成不同的散列值,若将散列值作为数据的“标志”,这一特性就可以广泛应用于数据一致性校验

因为散列值往往是一对一的,具有唯一性,所以可以作为某一个数据项的标志

作为一致性校验额数据“标志”,散列函数需要具备以下特征

  • 压缩性 :任意长度的数据,通过散列函数计算出的散列值是 固定长度

  • 容易计算 :很容易从原数据计算出散列值(“标志”), 注意不能从“标志”反向推出原数据

  • 抗修改性:对原数据的微小变动,都会引起“标志”(散列值)巨大改变

  • 抗冲突性:已知原数据和对应的散列值(“标志”),要再找到相同的散列值很难(即唯一性!)

近似完美函数:MD5/SHA


MD5(Message Digset):将任何长度的数据变换成固定长度为128位(16字节)的“标志”

128位已经是非常巨大的数字空间了,据说地球的沙子的数量就是这么多

SHA(Secure Hash Algorithm)

  • SHA-0/SHA-1:输出散列值160位(20字节)

  • SHA-256/SHA-224:分别输出256位和224位

  • SHA-512/SHA-384:分别输出512位和384位

Python的散列函数库:hashlib


Python自带了MD5和SHA系列的散列函数:hashlib

包含了:md5、sha1、sha224、sha256、sha384、sha512

Python数据结构与算法——散列(Hash)

计算结果:

d26a53750bc40b38b65a520292f69306

数据一致性检验中的应用


1. 数据文件是否是一致的

为每个文件计算其散列值,通过比对散列值即可得知是否文件内容相同

2. 用于网络文件下载完整性校验

下载时会提供文件的散列值,下载过程中不断比对散列值,看是否下载出错

3. 用于文件分享系统(例如:百度网盘)

服务器中都存储了文件的散列值,相同文件无需存储多次

4. 加密形式保存密码(常用Python数据结构与算法——散列(Hash)

在注册账户密码时,服务器往往存储的是密码对应的散列值,用户登录输入密码时,通过散列值比对验证

Python数据结构与算法——散列(Hash)

本文分享自微信公众号 - 小杨的python之路(gh_6ba152d49331)。
如有侵权,请联系 support@oschina.cn 删除。
本文参与“OSC源创计划”,欢迎正在阅读的你也加入,一起分享。

点赞
收藏
评论区
推荐文章
blmius blmius
2年前
MySQL:[Err] 1292 - Incorrect datetime value: ‘0000-00-00 00:00:00‘ for column ‘CREATE_TIME‘ at row 1
文章目录问题用navicat导入数据时,报错:原因这是因为当前的MySQL不支持datetime为0的情况。解决修改sql\mode:sql\mode:SQLMode定义了MySQL应支持的SQL语法、数据校验等,这样可以更容易地在不同的环境中使用MySQL。全局s
皕杰报表之UUID
​在我们用皕杰报表工具设计填报报表时,如何在新增行里自动增加id呢?能新增整数排序id吗?目前可以在新增行里自动增加id,但只能用uuid函数增加UUID编码,不能新增整数排序id。uuid函数说明:获取一个UUID,可以在填报表中用来创建数据ID语法:uuid()或uuid(sep)参数说明:sep布尔值,生成的uuid中是否包含分隔符'',缺省为
Wesley13 Wesley13
2年前
Java获得今日零时零分零秒的时间(Date型)
publicDatezeroTime()throwsParseException{    DatetimenewDate();    SimpleDateFormatsimpnewSimpleDateFormat("yyyyMMdd00:00:00");    SimpleDateFormatsimp2newS
Stella981 Stella981
2年前
Android So动态加载 优雅实现与原理分析
背景:漫品Android客户端集成适配转换功能(基于目标识别(So库35M)和人脸识别库(5M)),导致apk体积50M左右,为优化客户端体验,决定实现So文件动态加载.!(https://oscimg.oschina.net/oscnet/00d1ff90e4b34869664fef59e3ec3fdd20b.png)点击上方“蓝字”关注我
Stella981 Stella981
2年前
Python之time模块的时间戳、时间字符串格式化与转换
Python处理时间和时间戳的内置模块就有time,和datetime两个,本文先说time模块。关于时间戳的几个概念时间戳,根据1970年1月1日00:00:00开始按秒计算的偏移量。时间元组(struct_time),包含9个元素。 time.struct_time(tm_y
Wesley13 Wesley13
2年前
mysql设置时区
mysql设置时区mysql\_query("SETtime\_zone'8:00'")ordie('时区设置失败,请联系管理员!');中国在东8区所以加8方法二:selectcount(user\_id)asdevice,CONVERT\_TZ(FROM\_UNIXTIME(reg\_time),'08:00','0
Wesley13 Wesley13
2年前
00:Java简单了解
浅谈Java之概述Java是SUN(StanfordUniversityNetwork),斯坦福大学网络公司)1995年推出的一门高级编程语言。Java是一种面向Internet的编程语言。随着Java技术在web方面的不断成熟,已经成为Web应用程序的首选开发语言。Java是简单易学,完全面向对象,安全可靠,与平台无关的编程语言。
Stella981 Stella981
2年前
Docker 部署SpringBoot项目不香吗?
  公众号改版后文章乱序推荐,希望你可以点击上方“Java进阶架构师”,点击右上角,将我们设为★“星标”!这样才不会错过每日进阶架构文章呀。  !(http://dingyue.ws.126.net/2020/0920/b00fbfc7j00qgy5xy002kd200qo00hsg00it00cj.jpg)  2
Wesley13 Wesley13
2年前
MySQL部分从库上面因为大量的临时表tmp_table造成慢查询
背景描述Time:20190124T00:08:14.70572408:00User@Host:@Id:Schema:sentrymetaLast_errno:0Killed:0Query_time:0.315758Lock_
Python进阶者 Python进阶者
5个月前
Excel中这日期老是出来00:00:00,怎么用Pandas把这个去除
大家好,我是皮皮。一、前言前几天在Python白银交流群【上海新年人】问了一个Pandas数据筛选的问题。问题如下:这日期老是出来00:00:00,怎么把这个去除。二、实现过程后来【论草莓如何成为冻干莓】给了一个思路和代码如下:pd.toexcel之前把这