往期链接

17 散列(Hashing)

S1 说明

散列是一种将输入数据(通常称为键)转换为固定大小的字符串或数字的过程,通常称为散列值或哈希值。散列函数是执行此转换的算法,其输出是一个唯一的哈希码,用于快速查找和存储数据。

特点
  • 固定长度输出:
    无论输入数据的大小如何,散列函数的输出长度是固定的。例如,SHA-256 散列函数始终输出 256 位(32 字节)的哈希值。
  • 快速计算:
    散列函数的计算速度通常很快,能够在常量时间内生成哈希值。
  • 抗碰撞性:
    理想的散列函数应当使得不同的输入数据产生相同输出的概率极低。这意味着很难找到两个不同的输入具有相同的哈希值(称为碰撞)。
  • 不可逆性:
    散列函数应当是不可逆的,即从散列值无法反推原始输入。这使得散列在数据安全和加密中非常有用。
  • 敏感性:
    微小的输入变化会导致哈希值的大幅变化。这一特性被称为“雪崩效应”。
应用领域

散列在多个领域中有广泛的应用,包括:

  • 数据结构:
    哈希表:使用散列函数将键映射到数组中的位置,实现快速的查找、插入和删除操作。哈希表广泛用于实现集合和字典等数据结构。
  • 密码学:
    • 数字签名:用于创建数字签名,通过散列原始消息并对其哈希值进行加密,以确保数据的完整性和- 身份验证。
    • 消息认证码(MAC):结合密钥和消息的散列,用于验证消息的完整性和来源。
  • 数据完整性
    文件完整性检查:通过计算文件的哈希值,可以快速检查文件在传输或存储过程中是否被篡改(如使用 MD5 或 SHA-256)。
  • 数据库:
    索引:使用散列值作为索引,以加速数据库中的数据检索。
  • 分布式系统:
    • 负载均衡:散列函数可用于将请求分配到不同的服务器,以实现负载均衡。
    • 一致性哈希:在分布式缓存和存储系统中,使用一致性哈希来管理节点之间的负载分配。
  • 区块链:
    在区块链技术中,散列函数用于确保区块的完整性和安全性。每个区块包含前一个区块的哈希值,从而形成链式结构,确保数据不可篡改。
  • 数据去重:
    在数据存储和处理领域,通过计算数据的哈希值,可以有效地识别和去除重复数据。

S2 示例:字符串哈希

import hashlib

def generate_hash(data):
    """生成数据的SHA-256哈希值"""
    hash_object = hashlib.sha256()
    hash_object.update(data.encode('utf-8'))  # 将字符串编码为字节
    return hash_object.hexdigest()  # 返回十六进制哈希值

# 示例:生成字符串的哈希值
data = "这是一个测试的字符串"
hash_
10-21 12:57