5.1 哈希函數的定義及其應用
哈希函數 是一種函數，它接受輸入數據（或鍵）並返回固定大小的位數，通常稱為哈希或哈希值。哈希函數的主要目的是將數據高效地分配到哈希表中，以保證快速訪問元素。
應用：
- 哈希表: 用於實現關聯數組（Python 中的字典），提供根據鍵的快速數據訪問。
- 數據完整性檢查: 使用哈希函數檢查文件和數據的完整性（例如，MD5、SHA-1、SHA-256 算法）。
- 密碼學: 哈希函數用於加密和創建數字簽名的密碼算法中。
- 搜索引擎: 用於數據索引和快速信息搜索。
- 緩存管理: 用於組織緩存以快速找到數據。
在 Python 中使用哈希函數的示例：
# 在 Python 中為哈希表（字典）使用哈希函數的示例
data = {"apple": 1, "banana": 2, "cherry": 3}
# 獲取鍵的哈希值
key = "banana"
hash_value = hash(key)
print(f"鍵 '{key}' 的哈希值: {hash_value}")
5.2 現實生活中的類比
利用哈希函數，可以將大群對象分成大約相等的組。而且，如果繼續添加新對象，它們會繼續均勻地分佈在各組中。
假設你有 1000 個人需要被分成 30 組。這就是你可以做的。
方法 1. 按名字的第一個字母。
第一組是名字以「A」開頭的人，第二組是名字以「B」開頭的人，依此類推。規則「你的小組是你名字的第一個字母」就是哈希函數。但使用這樣的哈希函數，我們可能會在「A」組有很多人，而在「Z」組很少人。
方法 2. 按出生日期。
任何一個月的第一天出生的人是第一組，第二天出生的是第二組，依此類推。這樣會有31組。第31組的人大約只有其他組的一半，但是這樣分組的人比第一種情況更均勻地分佈。
方法 3. 電話號碼
理想的選擇是獲得一個數字，一方面它應該是盡可能隨機的（那麼這些數字會均勻分佈），另一方面它應該能夠快速計算並保持不變。
我們來拿電話號碼的最後4個數字來算——這樣會有10,000種可能。然後將這個數字整除30。我們將得到30個可能的餘數：0, 1, 2, ..., 29。這就是我們的組號。
有用的小知識！事實上，幾乎所有的哈希函數都使用整除的餘數——這非常簡單並且可以控制需要分成多少組的元素。
5.3 好的哈希函數的主要特性
好的哈希函數的主要特性：
確定性: 同一哈希函數 對於相同的輸入值應始終返回相同的哈希值。
示例：
key = "example"
assert hash(key) == hash(key)
重要！ 操作符 assert 檢查右邊的表達式是否為真 True。如果表達式不為真 False，則會引發異常。
均勻性: 好的哈希函數應該在可能的哈希值全範圍內均勻分佈，以避免碰撞。
Python 開發者的現實生活示例：在 Python 的字典（類 dict）中，哈希函數 hash() 會均勻地分配鍵。
計算效率: 哈希函數應該快速且高效，以免減慢插入和搜索操作。
Python 開發者的現實生活示例：Python 中的標準哈希函數實現了對不同類型鍵（如字符串和數字）的操作。
碰撞最小化: 當 兩個不同的鍵有相同的哈希值時會發生碰撞。好的哈希函數應該最小化碰撞的可能性。
Python 開發者的現實生活示例：算法 SHA-256 最小化哈希數據時的碰撞可能性。
哈希分佈: 對於大量數據，哈希函數應該確保哈希值在整個哈希表中均勻分佈。
Python 開發者的現實生活示例：Python 中的標準哈希函數在哈希表中良好地分配鍵。
5.4 哈希函數的示例及其實現
哈希函數接受任意大小的 輸入數據 並返回固定大小的 哈希值。讓我們看看一些哈希函數的示例及其實現。
示例 1: 簡單的字符串哈希函數
最簡單的字符串哈希函數之一可以用字符串字符碼的和來實現：
def simple_hash(key):
hash_value = 0
for char in key:
hash_value += ord(char)
return hash_value % 1000 # 假設我們的表大小為1000
# 使用示例:
key = "example"
print(f"鍵 '{key}' 的哈希值: {simple_hash(key)}")
示例 2: 使用多項式哈希的字符串哈希函數
多項式哈希是一種更複雜但有效的技術：
def polynomial_hash(key, a=33, m=1000):
hash_value = 0
for char in key:
hash_value = (hash_value * a + ord(char)) % m
return hash_value
# 使用示例:
key = "example"
print(f"鍵 '{key}' 的哈希值: {polynomial_hash(key)}")
示例 3: Python 內建哈希函數
Python 提供內建函數 hash() 來獲取不同數據類型的哈希值：
key = "example"
print(f"鍵 '{key}' 的哈希值: {hash(key)}")
示例 4: 密碼學哈希函數 (SHA-256)
密碼學哈希函數，如 SHA-256，用於確保數據安全：
import hashlib
def sha256_hash(key):
return hashlib.sha256(key.encode()).hexdigest()
# 使用示例:
key = "example"
print(f"鍵 '{key}' 的哈希值: {sha256_hash(key)}")
5.5 哈希和其應用簡介
哈希 是使用哈希函數將任意大小的輸入數據轉換為固定大小的哈希值的過程。哈希在計算機科學和編程中被廣泛用於優化和保證安全。
哈希的主要應用：
1. 哈希表（字典）: 哈希表使用哈希函數來組織和快速訪問數據。
data = {"apple": 1, "banana": 2, "cherry": 3}
key = "banana"
hash_value = hash(key)
print(f"鍵 '{key}' 的哈希值: {hash_value}")
2. 數據完整性檢查: 使用哈希函數檢查文件和數據的完整性。
示例: 使用 SHA-256 檢查文件完整性：
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. 密碼學與安全: 哈希函數用於創建密碼學基本構件，如數字簽名和密碼哈希。
示例: 使用 SHA-256 哈希密碼：
import hashlib
def hash_password(password):
return hashlib.sha256(password.encode()).hexdigest()
password = "securepassword"
hashed_password = hash_password(password)
print(f"密碼哈希: {hashed_password}")
4. 搜索引擎和索引: 哈希用於創建索引和快速搜索數據。
示例: 為文本搜索創建索引：
def create_index(text):
index = {}
for word in text.split():
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}")
5. 緩存管理: 哈希用於組織緩存以快速找到數據。
示例: 使用哈希函數的簡單緩存：
cache = {}
def get_from_cache(key):
hash_key = hash(key)
return cache.get(hash_key, None)
def add_to_cache(key, value):
hash_key = hash(key)
cache[hash_key] = value
# 添加和從緩存中獲取數據
add_to_cache("test_key", "test_value")
print(get_from_cache("test_key")) # 輸出: test_value
GO TO FULL VERSION