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

文章目录

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

一、散列

散列 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的一个区块

您正在阅读的是《数据结构与算法Python版》专栏！关注不迷路~