哈希函数及其应用

10.1 介绍哈希函数和哈希表

让我们回顾并加深对哈希函数和表的理解。哈希函数 是一种将任意长度的输入数据转换为固定长度字符串的算法。哈希函数的主要属性：

• 确定性：相同的输入总是产生相同的结果。
• 快速计算：哈希应该能快速计算出来。
• 不可逆性（对于加密哈希函数）：从哈希中恢复原始数据几乎不可能。
• 均匀分布：输入数据的微小变化会导致哈希的显著改变。

简单来说，相同对象的哈希值必须相同，但两个对象的哈希值相同，它们不一定相等。数学上这被称为必要但不充分条件。

哈希表 是一种使用哈希函数进行高效存储和检索信息的数据结构。它由以下部分组成：

• 用于存储数据的"桶"数组。
• 决定将数据放在哪个桶里的哈希函数。

哈希表提供对数据的快速访问，通常在平均情况下其时间复杂度为O(1)。

哈希函数的实际应用

例子：区块链技术

在区块链中，哈希函数用于创建区块的唯一标识符并确保数据的完整性。每个区块包含前一个区块的哈希，从而形成链条，使系统经受住篡改。

import hashlib
import time

class Block:
    def __init__(self, data, previous_hash):
        self.timestamp = time.time()
        self.data = data
        self.previous_hash = previous_hash
        self.hash = self.calculate_hash()

    def calculate_hash(self):
        hash_string = str(self.timestamp) + str(self.data) + str(self.previous_hash)
        return hashlib.sha256(hash_string.encode()).hexdigest()

# 使用示例
block1 = Block("交易1", "0")
block2 = Block("交易2", block1.hash)
print(f"区块1的哈希：{block1.hash}")
print(f"区块2的哈希：{block2.hash}")

性能比较

考虑在数组中查找重复项的问题。我们比较使用哈希表和不使用哈希表的解决方案：

import time

def find_duplicates_with_hash(arr):
    seen = set()
    duplicates = []
    for item in arr:
        if item in seen:
            duplicates.append(item)
        else:
            seen.add(item)
    return duplicates

def find_duplicates_without_hash(arr):
    duplicates = []
    for i in range(len(arr)):
        for j in range(i+1, len(arr)):
            if arr[i] == arr[j] and arr[i] not in duplicates:
                duplicates.append(arr[i])
    return duplicates

# 性能测试
arr = list(range(10000)) + list(range(5000))  # 带有重复项的数组

start = time.time()
find_duplicates_with_hash(arr)
end = time.time()
print(f"使用哈希表的执行时间：{end - start} 秒")

start = time.time()
find_duplicates_without_hash(arr)
end = time.time()
print(f"不使用哈希表的执行时间：{end - start} 秒")

运行程序，并观察使用哈希表在搜索大量数据集合中的重复项时的加速效果。

10.2 哈希函数在实际任务中的应用示例

1. 密码哈希化

哈希函数用于安全存储密码。系统不直接存储密码，而是存储它们的哈希。当用户输入密码时，系统将输入的密码进行哈希化并与存储在数据库中的哈希进行比较。

实现示例：

import hashlib

def hash_password(password):
    return hashlib.sha256(password.encode()).hexdigest()

# 使用示例：
password = "securepassword"
hashed_password = hash_password(password)
print(f"密码的哈希：{hashed_password}")

2. 数据完整性检查

哈希函数用于检查文件和数据的完整性。例如，检查文件是否在传输过程中被更改或损坏。

实现示例：

import hashlib

def get_file_hash(file_path):
    hasher = hashlib.sha256()
    with open(file_path, 'rb') as file:
        buf = file.read()
        hasher.update(buf)
    return hasher.hexdigest()

# 使用示例：
file_hash = get_file_hash('example.txt')
print(f"文件的SHA-256哈希：{file_hash}")

3. 搜索引擎和索引

搜索引擎使用哈希函数来创建索引和快速检索信息。每个文档根据关键词进行索引，哈希函数能快速定位包含特定词语的文档。

实现示例：

def create_index(text):
    index = {}
    words = text.split()
    for word in words:
        word_hash = hash(word)
        if word_hash not in index:
            index[word_hash] = []
        index[word_hash].append(word)
    return index

# 使用示例：
text = "This is an example text for indexing"
index = create_index(text)
print(f"索引：{index}")

10.3 使用哈希函数优化搜索

1. 使用哈希表查找重复项

哈希表通过比较元素的哈希值快速在数组中找到重复项。

实现示例：

def find_duplicates(arr):
    seen = set()
    duplicates = []
    for item in arr:
        if item in seen:
            duplicates.append(item)
        else:
            seen.add(item)
    return duplicates

# 使用示例：
arr = [1, 2, 3, 2, 4, 5, 6, 4, 7]
print(find_duplicates(arr))  # 输出：[2, 4]

2. 使用哈希表优化查找和的配对

哈希表可以高效地在数组中找到其和等于给定值的数对。

实现示例：

def find_pairs_with_sum(arr, target_sum):
    seen = set()
    pairs = []

    for num in arr:
        complement = target_sum - num
        if complement in seen:
            pairs.append((complement, num))
        seen.add(num)

    return pairs

# 使用示例：
arr = [2, 4, 3, 7, 8, -2, 10, -1]
target_sum = 6
print(find_pairs_with_sum(arr, target_sum))  # 输出：[(4, 2), (3, 3), (8, -2)]

10.4 哈希函数在各种算法中的应用示例

1. 统计文本中的单词数量

使用哈希表统计文本中每个单词的出现次数。

实现示例：

def count_words(text):
    word_count = {}
    words = text.split()

    for word in words:
        if word in word_count:
            word_count[word] += 1
        else:
            word_count[word] = 1

    return word_count

# 使用示例：
text = "this is a test this is only a test"
print(count_words(text))  # 输出：{'this': 2, 'is': 2, 'a': 2, 'test': 2, 'only': 1}

2. 检查两个数组是否有交集

检查两个数组是否有交集（至少有一个相同元素）。

实现示例：

def has_intersection(arr1, arr2):
    set1 = set(arr1)
    for item in arr2:
        if item in set1:
            return True
    return False

# 使用示例：
arr1 = [1, 2, 3, 4]
arr2 = [3, 5, 6, 7]
arr3 = [8, 9, 10]
print(has_intersection(arr1, arr2))  # 输出：True
print(has_intersection(arr1, arr3))  # 输出：False

3. 检查数组中的元素是否唯一

检查数组中是否包含唯一元素。

实现示例：

def all_unique(arr):
    seen = set()
    for item in arr:
        if item in seen:
            return False
        seen.add(item)
    return True

# 使用示例：
arr1 = [1, 2, 3, 4, 5]
arr2 = [1, 2, 3, 4, 5, 3]
print(all_unique(arr1))  # 输出：True
print(all_unique(arr2))  # 输出：False