devbox
凡人多烦事01
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

Python实战开发及案例分析（31）—— 哈希算法

作者：凡人多烦事01 | 2024-05-21 06:49:52

赞

踩

Python实战开发及案例分析（31）—— 哈希算法

        哈希算法（Hash Algorithm）是一种将输入数据映射到固定大小的输出（通常是一个整数或字符串）的算法。哈希算法广泛应用于数据结构（如哈希表）、加密、数据校验等领域。下面将详细介绍哈希算法的基本原理，并通过具体案例展示如何在Python中实现和应用哈希算法。

哈希算法的基本原理

        哈希算法通过一个哈希函数将输入数据转换成一个哈希值。理想的哈希函数具有以下特性：

  • 确定性：相同的输入总是产生相同的输出。
  • 快速计算：哈希函数计算哈希值的速度应尽可能快。
  • 均匀分布：哈希值应该均匀分布，以减少冲突（不同输入产生相同哈希值）。
  • 抗碰撞：不同的输入产生相同哈希值（碰撞）的概率应尽可能低。

Python实现哈希算法

        以下是几个常见的哈希算法在Python中的实现：

示例1：简单的哈希函数

        我们先实现一个简单的哈希函数，将字符串转换为一个整数哈希值。

  1. def simple_hash(data):
  2.     hash_value = 0
  3.     for char in data:
  4.         hash_value += ord(char)
  5.     return hash_value
  6.  
  7. # 测试简单哈希函数
  8. print(simple_hash("hello"))  # 输出：532
  9. print(simple_hash("world"))  # 输出：552
  10. print(simple_hash("hello world"))  # 输出：1116
示例2：改进的哈希函数（乘法哈希）

        改进哈希函数使得哈希值更加均匀分布，减少冲突。

  1. def improved_hash(data):
  2.     hash_value = 0
  3.     prime = 31
  4.     for char in data:
  5.         hash_value = hash_value * prime + ord(char)
  6.     return hash_value
  7.  
  8. # 测试改进哈希函数
  9. print(improved_hash("hello"))  # 输出：99162322
  10. print(improved_hash("world"))  # 输出：113318802
  11. print(improved_hash("hello world"))  # 输出：929490967117471

哈希算法的实际应用

案例：实现哈希表

        哈希表是一种数据结构，通过哈希函数将键映射到表中的位置，从而实现快速查找、插入和删除操作。我们将实现一个简单的哈希表，并演示其基本操作。

  1. class HashTable:
  2.     def __init__(self, size=100):
  3.         self.size = size
  4.         self.table = [None] * size
  5.  
  6.     def _hash(self, key):
  7.         hash_value = 0
  8.         prime = 31
  9.         for char in key:
  10.             hash_value = hash_value * prime + ord(char)
  11.         return hash_value % self.size
  12.  
  13.     def insert(self, key, value):
  14.         index = self._hash(key)
  15.         if self.table[index] is None:
  16.             self.table[index] = []
  17.         # 检查是否有相同的key，更新value
  18.         for item in self.table[index]:
  19.             if item[0] == key:
  20.                 item[1] = value
  21.                 return
  22.         self.table[index].append([key, value])
  23.  
  24.     def search(self, key):
  25.         index = self._hash(key)
  26.         if self.table[index] is None:
  27.             return None
  28.         for item in self.table[index]:
  29.             if item[0] == key:
  30.                 return item[1]
  31.         return None
  32.  
  33.     def delete(self, key):
  34.         index = self._hash(key)
  35.         if self.table[index] is None:
  36.             return
  37.         for i, item in enumerate(self.table[index]):
  38.             if item[0] == key:
  39.                 del self.table[index][i]
  40.                 return
  41.  
  42. # 测试哈希表
  43. hash_table = HashTable()
  44.  
  45. # 插入键值对
  46. hash_table.insert("name", "Alice")
  47. hash_table.insert("age", "25")
  48. hash_table.insert("city", "New York")
  49.  
  50. # 搜索键值
  51. print(hash_table.search("name"))  # 输出：Alice
  52. print(hash_table.search("age"))  # 输出：25
  53. print(hash_table.search("city"))  # 输出：New York
  54.  
  55. # 删除键值
  56. hash_table.delete("age")
  57. print(hash_table.search("age"))  # 输出：None

案例分析：密码存储与校验

        在密码存储和校验中，哈希算法用于将密码转换为哈希值，并存储在数据库中。当用户登录时，将输入的密码进行哈希计算，并与存储的哈希值进行比较。

示例：使用SHA-256哈希函数
  1. import hashlib
  2.  
  3. def hash_password(password):
  4.     return hashlib.sha256(password.encode()).hexdigest()
  5.  
  6. def verify_password(stored_hash, password):
  7.     return stored_hash == hashlib.sha256(password.encode()).hexdigest()
  8.  
  9. # 示例密码
  10. password = "securepassword"
  11. hashed_password = hash_password(password)
  12. print("Hashed Password:", hashed_password)
  13.  
  14. # 验证密码
  15. print(verify_password(hashed_password, "securepassword"))  # 输出：True
  16. print(verify_password(hashed_password, "wrongpassword"))  # 输出：False

总结

        哈希算法是计算机科学中非常重要的一种技术，广泛应用于数据结构、加密、数据校验等领域。通过实现简单和改进的哈希函数，我们了解了哈希算法的基本原理和实现方法。实际应用中，哈希表和密码存储与校验是哈希算法的经典应用。通过不断优化和扩展，哈希算法将在更多领域中发挥重要作用。        

深入探讨哈希算法的更多应用与优化

        哈希算法不仅用于简单的数据存储和密码校验，还可以在其他复杂应用中发挥重要作用。接下来，我们将探讨哈希算法在以下几个领域中的应用：

  1. 哈希碰撞处理：处理哈希表中的碰撞问题。
  2. 布隆过滤器：一种空间效率高的概率性数据结构，用于集合成员的快速查找。
  3. 区块链与加密货币：哈希函数在区块链中的应用。

1. 哈希碰撞处理

        在哈希表中，多个键被映射到同一个哈希值的位置会导致碰撞。常见的碰撞处理方法有两种：链地址法（Separate Chaining）和开放地址法（Open Addressing）。

链地址法

        链地址法通过在每个哈希桶中使用链表来处理碰撞，所有映射到同一位置的键值对都存储在同一个链表中。        

  1. class HashTableChaining:
  2.     def __init__(self, size=100):
  3.         self.size = size
  4.         self.table = [[] for _ in range(size)]
  5.  
  6.     def _hash(self, key):
  7.         hash_value = 0
  8.         prime = 31
  9.         for char in key:
  10.             hash_value = hash_value * prime + ord(char)
  11.         return hash_value % self.size
  12.  
  13.     def insert(self, key, value):
  14.         index = self._hash(key)
  15.         for item in self.table[index]:
  16.             if item[0] == key:
  17.                 item[1] = value
  18.                 return
  19.         self.table[index].append([key, value])
  20.  
  21.     def search(self, key):
  22.         index = self._hash(key)
  23.         for item in self.table[index]:
  24.             if item[0] == key:
  25.                 return item[1]
  26.         return None
  27.  
  28.     def delete(self, key):
  29.         index = self._hash(key)
  30.         for i, item in enumerate(self.table[index]):
  31.             if item[0] == key:
  32.                 del self.table[index][i]
  33.                 return
  34.  
  35. # 测试链地址法哈希表
  36. hash_table = HashTableChaining()
  37.  
  38. hash_table.insert("name", "Alice")
  39. hash_table.insert("age", "25")
  40. hash_table.insert("city", "New York")
  41.  
  42. print(hash_table.search("name"))  # 输出：Alice
  43. print(hash_table.search("age"))  # 输出：25
  44. print(hash_table.search("city"))  # 输出：New York
  45.  
  46. hash_table.delete("age")
  47. print(hash_table.search("age"))  # 输出：None
开放地址法

        开放地址法在碰撞发生时，通过探测空闲位置插入新键值对。常见的探测方法有线性探测、二次探测和双重哈希。

  1. class HashTableOpenAddressing:
  2.     def __init__(self, size=100):
  3.         self.size = size
  4.         self.table = [None] * size
  5.  
  6.     def _hash(self, key):
  7.         hash_value = 0
  8.         prime = 31
  9.         for char in key:
  10.             hash_value = hash_value * prime + ord(char)
  11.         return hash_value % self.size
  12.  
  13.     def insert(self, key, value):
  14.         index = self._hash(key)
  15.         for i in range(self.size):
  16.             probe_index = (index + i) % self.size
  17.             if self.table[probe_index] is None or self.table[probe_index][0] == key:
  18.                 self.table[probe_index] = (key, value)
  19.                 return
  20.         raise Exception("HashTable is full")
  21.  
  22.     def search(self, key):
  23.         index = self._hash(key)
  24.         for i in range(self.size):
  25.             probe_index = (index + i) % self.size
  26.             if self.table[probe_index] is None:
  27.                 return None
  28.             if self.table[probe_index][0] == key:
  29.                 return self.table[probe_index][1]
  30.         return None
  31.  
  32.     def delete(self, key):
  33.         index = self._hash(key)
  34.         for i in range(self.size):
  35.             probe_index = (index + i) % self.size
  36.             if self.table[probe_index] is None:
  37.                 return
  38.             if self.table[probe_index][0] == key:
  39.                 self.table[probe_index] = None
  40.                 return
  41.  
  42. # 测试开放地址法哈希表
  43. hash_table = HashTableOpenAddressing()
  44.  
  45. hash_table.insert("name", "Alice")
  46. hash_table.insert("age", "25")
  47. hash_table.insert("city", "New York")
  48.  
  49. print(hash_table.search("name"))  # 输出：Alice
  50. print(hash_table.search("age"))  # 输出：25
  51. print(hash_table.search("city"))  # 输出：New York
  52.  
  53. hash_table.delete("age")
  54. print(hash_table.search("age"))  # 输出：None

2. 布隆过滤器

        布隆过滤器是一种空间效率高的概率性数据结构，用于快速判断一个元素是否在集合中。布隆过滤器具有一定的误判率，即可能错误地认为一个不在集合中的元素存在于集合中，但不会漏判。

实现布隆过滤器
  1. from bitarray import bitarray
  2. import mmh3
  3.  
  4. class BloomFilter:
  5.     def __init__(self, size, hash_count):
  6.         self.size = size
  7.         self.hash_count = hash_count
  8.         self.bit_array = bitarray(size)
  9.         self.bit_array.setall(0)
  10.  
  11.     def add(self, item):
  12.         for i in range(self.hash_count):
  13.             digest = mmh3.hash(item, i) % self.size
  14.             self.bit_array[digest] = 1
  15.  
  16.     def check(self, item):
  17.         for i in range(self.hash_count):
  18.             digest = mmh3.hash(item, i) % self.size
  19.             if self.bit_array[digest] == 0:
  20.                 return False
  21.         return True
  22.  
  23. # 测试布隆过滤器
  24. bf = BloomFilter(500, 7)
  25.  
  26. items_to_add = ["apple", "banana", "cherry", "date"]
  27. items_to_check = ["apple", "banana", "grape", "orange"]
  28.  
  29. for item in items_to_add:
  30.     bf.add(item)
  31.  
  32. for item in items_to_check:
  33.     print(f"{item}: {bf.check(item)}")

3. 区块链与加密货币

        哈希函数在区块链中有重要应用，尤其是在数据完整性、工作量证明（Proof of Work）以及生成区块哈希等方面。区块链通过哈希函数确保数据不可篡改。

示例：使用SHA-256生成区块哈希
  1. import hashlib
  2. import json
  3. from time import time
  4.  
  5. class Block:
  6.     def __init__(self, index, previous_hash, transactions, proof, timestamp=None):
  7.         self.index = index
  8.         self.previous_hash = previous_hash
  9.         self.transactions = transactions
  10.         self.proof = proof
  11.         self.timestamp = timestamp or time()
  12.  
  13.     def compute_hash(self):
  14.         block_string = json.dumps(self.__dict__, sort_keys=True)
  15.         return hashlib.sha256(block_string.encode()).hexdigest()
  16.  
  17. class Blockchain:
  18.     def __init__(self):
  19.         self.chain = []
  20.         self.current_transactions = []
  21.         self.create_block(proof=1, previous_hash='0')
  22.  
  23.     def create_block(self, proof, previous_hash):
  24.         block = Block(index=len(self.chain) + 1,
  25.                       previous_hash=previous_hash,
  26.                       transactions=self.current_transactions,
  27.                       proof=proof)
  28.         self.current_transactions = []
  29.         self.chain.append(block)
  30.         return block
  31.  
  32.     def get_last_block(self):
  33.         return self.chain[-1]
  34.  
  35.     def add_transaction(self, sender, recipient, amount):
  36.         self.current_transactions.append({
  37.             'sender': sender,
  38.             'recipient': recipient,
  39.             'amount': amount
  40.         })
  41.         return self.get_last_block().index + 1
  42.  
  43.     def proof_of_work(self, last_proof):
  44.         proof = 0
  45.         while not self.valid_proof(last_proof, proof):
  46.             proof += 1
  47.         return proof
  48.  
  49.     def valid_proof(self, last_proof, proof):
  50.         guess = f'{last_proof}{proof}'.encode()
  51.         guess_hash = hashlib.sha256(guess).hexdigest()
  52.         return guess_hash[:4] == "0000"
  53.  
  54.     def add_block(self, proof):
  55.         previous_hash = self.get_last_block().compute_hash()
  56.         block = self.create_block(proof, previous_hash)
  57.         return block
  58.  
  59. # 创建区块链并添加区块
  60. blockchain = Blockchain()
  61. blockchain.add_transaction(sender="Alice", recipient="Bob", amount=50)
  62. last_proof = blockchain.get_last_block().proof
  63. proof = blockchain.proof_of_work(last_proof)
  64. blockchain.add_block(proof)
  65.  
  66. for block in blockchain.chain:
  67.     print(f"Block {block.index}: {block.compute_hash()}")

总结

        哈希算法在计算机科学中有着广泛的应用，从数据存储、密码学到区块链技术。通过实现和应用哈希算法及其优化，我们能够高效地解决复杂的实际问题。继续深入学习和研究哈希算法，可以帮助我们在更多领域中发现和应用这一强大的工具。

更复杂的哈希算法应用及其优化

        在继续深入探讨哈希算法的应用时，我们可以进一步研究其在以下领域中的复杂应用：

  1. 一致性哈希：在分布式系统中用于分布和存储数据。
  2. LSH（局部敏感哈希）：用于高维数据的相似性搜索。
  3. 密码学中的哈希链：用于验证数据完整性和防止篡改。

1. 一致性哈希

        一致性哈希（Consistent Hashing）是一种分布式系统中的哈希技术，用于在分布式节点间均匀分配数据，特别适合动态添加或删除节点的场景。

实现一致性哈希

        以下是使用Python实现一致性哈希的示例：

  1. import hashlib
  2. import bisect
  3.  
  4. class ConsistentHash:
  5.     def __init__(self, nodes=None, replicas=3):
  6.         self.replicas = replicas
  7.         self.ring = dict()
  8.         self.sorted_keys = []
  9.         
  10.         if nodes:
  11.             for node in nodes:
  12.                 self.add_node(node)
  13.  
  14.     def _hash(self, key):
  15.         return int(hashlib.md5(key.encode()).hexdigest(), 16)
  16.  
  17.     def add_node(self, node):
  18.         for i in range(self.replicas):
  19.             key = self._hash(f'{node}:{i}')
  20.             self.ring[key] = node
  21.             bisect.insort(self.sorted_keys, key)
  22.  
  23.     def remove_node(self, node):
  24.         for i in range(self.replicas):
  25.             key = self._hash(f'{node}:{i}')
  26.             if key in self.ring:
  27.                 del self.ring[key]
  28.                 self.sorted_keys.remove(key)
  29.  
  30.     def get_node(self, key):
  31.         if not self.ring:
  32.             return None
  33.         hash_key = self._hash(key)
  34.         idx = bisect.bisect(self.sorted_keys, hash_key)
  35.         if idx == len(self.sorted_keys):
  36.             idx = 0
  37.         return self.ring[self.sorted_keys[idx]]
  38.  
  39. # 测试一致性哈希
  40. nodes = ["node1", "node2", "node3"]
  41. ch = ConsistentHash(nodes)
  42.  
  43. print("Node for key 'my_key1':", ch.get_node("my_key1"))
  44. print("Node for key 'my_key2':", ch.get_node("my_key2"))
  45. print("Node for key 'my_key3':", ch.get_node("my_key3"))
  46.  
  47. # 添加节点
  48. ch.add_node("node4")
  49. print("Node for key 'my_key1' after adding node4:", ch.get_node("my_key1"))
  50.  
  51. # 移除节点
  52. ch.remove_node("node2")
  53. print("Node for key 'my_key2' after removing node2:", ch.get_node("my_key2"))

2. 局部敏感哈希（LSH）

        局部敏感哈希（LSH）是一种用于高维数据的相似性搜索技术，通过将相似的输入映射到相同的哈希桶中，适用于快速相似性搜索。

实现LSH

        以下是使用Python实现局部敏感哈希的示例：

  1. import numpy as np
  2.  
  3. class LSH:
  4.     def __init__(self, input_dim, num_tables, num_hashes):
  5.         self.num_tables = num_tables
  6.         self.num_hashes = num_hashes
  7.         self.hash_tables = [{} for _ in range(num_tables)]
  8.         self.random_vectors = [np.random.randn(num_hashes, input_dim) for _ in range(num_tables)]
  9.  
  10.     def _hash(self, x, random_vectors):
  11.         return tuple((np.dot(random_vectors, x) > 0).astype(int))
  12.  
  13.     def add(self, x, label):
  14.         for table, random_vectors in zip(self.hash_tables, self.random_vectors):
  15.             hash_value = self._hash(x, random_vectors)
  16.             if hash_value not in table:
  17.                 table[hash_value] = []
  18.             table[hash_value].append(label)
  19.  
  20.     def query(self, x):
  21.         results = set()
  22.         for table, random_vectors in zip(self.hash_tables, self.random_vectors):
  23.             hash_value = self._hash(x, random_vectors)
  24.             if hash_value in table:
  25.                 results.update(table[hash_value])
  26.         return results
  27.  
  28. # 测试LSH
  29. data = np.random.randn(100, 128)
  30. labels = np.arange(100)
  31.  
  32. lsh = LSH(input_dim=128, num_tables=5, num_hashes=10)
  33. for x, label in zip(data, labels):
  34.     lsh.add(x, label)
  35.  
  36. query = data[0]
  37. print("Similar items to query:", lsh.query(query))

3. 密码学中的哈希链

        哈希链是一种用于数据完整性和防篡改验证的技术，通过将一系列哈希值链接在一起，形成一个链条。

实现哈希链

        以下是使用Python实现哈希链的示例：

  1. import hashlib
  2.  
  3. class HashChain:
  4.     def __init__(self):
  5.         self.chain = []
  6.  
  7.     def add_block(self, data):
  8.         previous_hash = self.chain[-1]['hash'] if self.chain else '0'
  9.         block_hash = self._hash(data + previous_hash)
  10.         self.chain.append({'data': data, 'hash': block_hash})
  11.  
  12.     def _hash(self, data):
  13.         return hashlib.sha256(data.encode()).hexdigest()
  14.  
  15.     def verify_chain(self):
  16.         for i in range(1, len(self.chain)):
  17.             previous_hash = self.chain[i - 1]['hash']
  18.             current_data = self.chain[i]['data']
  19.             if self._hash(current_data + previous_hash) != self.chain[i]['hash']:
  20.                 return False
  21.         return True
  22.  
  23. # 测试哈希链
  24. hash_chain = HashChain()
  25. hash_chain.add_block("Block 1")
  26. hash_chain.add_block("Block 2")
  27. hash_chain.add_block("Block 3")
  28.  
  29. print("Hash Chain:", hash_chain.chain)
  30. print("Is chain valid?", hash_chain.verify_chain())
  31.  
  32. # 篡改数据
  33. hash_chain.chain[1]['data'] = "Tampered Block 2"
  34. print("Is chain valid after tampering?", hash_chain.verify_chain())

总结

        哈希算法在计算机科学中的应用非常广泛，从一致性哈希在分布式系统中的应用，到局部敏感哈希在高维数据相似性搜索中的应用，再到哈希链在密码学和数据完整性验证中的应用，每种技术都有其独特的优势和应用场景。通过深入研究和实现这些哈希算法，我们可以更好地理解和利用它们来解决实际问题。继续学习和探索哈希算法，将为我们提供更多解决复杂问题的有效工具。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/凡人多烦事01/article/detail/601314
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号