Python数据结构与算法中的散列是什么

本篇内容主要讲解“Python数据结构与算法中的散列是什么”，感兴趣的朋友不妨来看看。本文介绍的方法操作简单快捷，实用性强。下面就让小编来带大家学习“Python数据结构与算法中的散列是什么”吧!

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• 冲突少（每个数据项的槽位都不同）

• 计算难度较低（计算槽位的过程较容易）

• 充分分散数据项（节约空间）

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

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

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

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

• 压缩性 ：任意长度的数据，通过散列函数计算出的散列值是 固定长度 的
• 容易计算 ：很容易从原数据计算出散列值（“标志”）， 注意不能从“标志”反向推出原数据
• 抗修改性：对原数据的微小变动，都会引起“标志”（散列值）巨大改变
• 抗冲突性：已知原数据和对应的散列值（“标志”），要再找到相同的散列值很难（即唯一性！）

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自带了MD5和SHA系列的散列函数：hashlib

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

计算结果：

d26a53750bc40b38b65a520292f69306

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

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

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

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

3. 用于文件分享系统（例如：百度网盘）

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

4. 加密形式保存密码（常用）

在注册账户密码时，服务器往往存储的是密码对应的散列值，用户登录输入密码时，通过散列值比对验证
到此，相信大家对“Python数据结构与算法中的散列是什么”有了更深的了解，不妨来实际操作一番吧！这里是亿速云网站，更多相关内容可以进入相关频道进行查询，关注我们，继续学习！