当前位置：首页 > article >正文

数据结构与算法Python版散列与区块链

article 2024/12/25 16:07:54

文章目录

一、散列
二、完美散列函数
三、完美散列函数的应用-区块链

一、散列

散列 Hashing

构造一个新的数据结构，使得查找算法的复杂度降到O(1)，这种概念称为“散列Hashing”
由数据项的值来确定其存放位置，数据项应该出现在大概什么位置，就可以直接到那个位置看看数据项是否存在即可

散列表 Hash table

散列表又称哈希表，是一种数据集，其中数据项的存储方式尤其有利于将来快速的查找定位
散列表中的每一个存储位置，称为槽（slot），可以用来保存数据项，每个槽有一个唯一的名称
例如：一个包含11个槽的散列表，槽的名称分别为0～10。在插入数据项之前，每个槽的值都是None，表示空槽

在这里插入图片描述

散列函数 Hash function

实现从数据项到存储槽名称的转换的，称为散列函数
一种常用的散列方法是“求余数”，将数据项除以散列表的大小，得到的余数作为槽号。

示例

数据项：54，26，93，17，77，31。使用散列函数求余：h(item)= item % 11。按照散列函数h(item)，为每个数据项计算出存放的位置之后，就可以将数据项存入相应的槽中
槽被数据项占据的比例称为散列表的“负载因子”，这里负载因子为6/11
对查找项进行计算，测试返回的槽号所对应的槽中是否有数据项。实现了O(1)时间复杂度的查找算法。

在这里插入图片描述

二、完美散列函数

冲突 Collision

在上面的例子中，如果还要保存44，h(44)=0，它跟77被分配到同一个0#槽中，这种情况称为**“冲突“**

完美散列函数

给定一组数据项，如果一个散列函数能把每个数据项映射到不同的槽中，即不发生冲突，那么这个散列函数就可以称为**“完美散列函数”**
由于完美散列函数能够对任何不同的数据生成不同的散列值，如果把散列值当作数据的“指纹”或者“摘要”，这种特性被广泛应用在数据的一致性校验上
作为一致性校验的数据“指纹”函数需要具备如下的特性
- 压缩性：任意长度的数据，得到的“指纹”长度是固定的；
- 易计算性：从原数据计算“指纹”很容易；（从指纹计算原数据是不可能的）；
- 抗修改性：对原数据的微小变动，都会引起“指纹”的大改变；
- 抗冲突性：已知原数据和“指纹”，要找到相同指纹的数据（伪造）是非常困难的

散列函数MD5/SHA

最著名的近似完美散列函数是MD5和SHA系列函数
MD5（Message Digest）将任何长度的数据变换为固定长为128位（16字节）的“摘要“
SHA（Secure Hash Algorithm）是另一组散列函数
- SHA-0/SHA-1输出散列值160位（20字节）
- SHA-256/SHA-224分别输出256位、224位
- SHA-512/SHA-384分别输出512位和384位

Python内置库hashlib

包括了md5 / sha1 / sha224 / sha256 / sha384 / sha512等6种散列函数
update方法用来对任意长的数据分部分来计算，这样不管多大的数据都不会有内存不足的问题。

import hashlib

m = hashlib.md5(b"hello world").hexdigest()
s = hashlib.sha1(b"hello world").hexdigest()
print(m)
print(s)

# 对任意长的数据分部分来计算
m2 = hashlib.md5()
m2.update(b"abcd")
m2.update(b"1234")
m2.update(b"xyz")
print(m2.hexdigest())


### 输出结果
5eb63bbbe01eeed093cb22bb8f5acdc3
2aae6c35c94fcfb415dbe95f408b9ce91ee846ed 
381bff64d37e09ff354730d46c9972b1

完美散列函数的应用

加密形式保存密码：仅保存密码的散列值，用户输入密码后，计算散列值并比对；无需保存密码的明文即可判断用户是否输入了正确的密码。
防文件篡改：完美散列函数能对数据文件进行一致性判断。防篡改，防抵赖，是电子商务的信息技术基础。
网盘中相同的文件可以无需存储多次：每个文件计算其散列值，仅对比其散列值即可得知是否文件内容相同。从而实现“极速上传”。

三、完美散列函数的应用-区块链

区块链

区块链是一种分布式数据库，通过网络连接节点，每个节点都保存着整个数据库所有数据，任何地点存入的数据都会完成同步
区块链最本质特征是“去中心化”。不存在任何控制中心、协调中心节点。所有节点都是平等的，无法被控制
区块链由一个个区块（block）组成，区块分为头（head）和体（body）
- 区块头记录了一些元数据和链接到前一个区块的信息。包括生成时间、前一个区块(head+body)的散列值等。
- 区块体记录了实际数据

在这里插入图片描述

区块链特性

不可修改性：任何对某个区块数据的改动必然引起散列值的变化，从而导致该区块脱离。
为了不导致这个区块脱离链条，就需要修改所有后续的区块。由于有“工作量证明”的机制，这种大规模修改几乎不可能实现。

工作量证明：Proof of Work(POW)

区块链是大规模的分布式数据库，同步较慢，所以需要控制新区块的添加速度。
当你第一个计算出一个新区块的有效散列值，你就有资格把新区块挂到区块链中。Bitcoin规定，每个区块中包含了一定数量的比特币作为“记账奖励”，每4年奖励的比特币减半。
有效的散列值计算方法
- 找到一个数值Nonce，把它跟整个区块数据一起计算散列。当这个散列值小于target，则这个是有效的散列值
- target等于常数targetmax除以难度系数Difficulty。难度系数会逐渐增加，导致target越来越小，从而增加计算难道
- 目前，这个Nonce的寻找只能靠暴力穷举，计算工作量+运气是唯一的方法。

示例：区块链比特币Bitcoin的一个区块
在这里插入图片描述