10.1 Giới thiệu về hàm băm và bảng băm
Hãy cùng ôn tập và mở rộng kiến thức về hàm băm và bảng băm. Hàm băm là một thuật toán chuyển đổi dữ liệu đầu vào có độ dài bất kỳ thành một chuỗi có độ dài cố định. Các đặc tính chính của hàm băm:
- Tính xác định: cùng dữ liệu đầu vào luôn cho cùng kết quả.
- Tính toán nhanh chóng: băm phải được tính toán đủ nhanh.
- Không thể đảo ngược (với hàm băm mật mã): không thể (hoặc cực kỳ khó) khôi phục dữ liệu gốc từ băm.
- Phân phối đều: những thay đổi nhỏ trong dữ liệu đầu vào dẫn đến những thay đổi lớn trong băm.
Nói đơn giản, hàm này ở các đối tượng giống nhau thì luôn trùng khớp, nhưng nếu hàm băm ở hai đối tượng giống nhau, thì các đối tượng này không nhất thiết phải bằng nhau. Trong toán học, điều này được gọi là điều kiện cần nhưng không đủ.
Bảng băm là một cấu trúc dữ liệu sử dụng hàm băm để lưu trữ và tìm kiếm thông tin hiệu quả. Nó bao gồm:
- Mảng "rổ" để lưu trữ dữ liệu.
- Hàm băm xác định rổ nào để đặt dữ liệu.
Bảng băm cung cấp truy cập dữ liệu nhanh chóng, thường với độ phức tạp O(1) trong trường hợp trung bình.
Ứng dụng của hàm băm trong đời sống thực tế
Ví dụ: Công nghệ Blockchain
Trong blockchain, hàm băm được sử dụng để tạo ra các định danh duy nhất cho các khối và đảm bảo tính toàn vẹn của dữ liệu. Mỗi khối chứa băm của khối trước đó, tạo thành một chuỗi và khiến hệ thống chống lại sự thay đổi.
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()
# Ví dụ sử dụng
block1 = Block("Giao dịch 1", "0")
block2 = Block("Giao dịch 2", block1.hash)
print(f"Hash của block 1: {block1.hash}")
print(f"Hash của block 2: {block2.hash}")
So sánh hiệu suất
Xem xét bài toán tìm kiếm trùng lặp trong một mảng. So sánh giải pháp sử dụng bảng băm và không sử dụng nó:
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
# Kiểm tra hiệu suất
arr = list(range(10000)) + list(range(5000)) # Mảng với các phần tử trùng lặp
start = time.time()
find_duplicates_with_hash(arr)
end = time.time()
print(f"Thời gian thực thi với bảng băm: {end - start} giây")
start = time.time()
find_duplicates_without_hash(arr)
end = time.time()
print(f"Thời gian thực thi không có bảng băm: {end - start} giây")
Chạy chương trình và tìm hiểu xem việc sử dụng bảng băm giúp tăng tốc tìm kiếm trùng lặp như thế nào, đặc biệt là trên các mảng dữ liệu lớn.
10.2 Ví dụ về ứng dụng của hàm băm trong các bài toán thực tế
1. Băm mật khẩu
Hàm băm được sử dụng để lưu trữ mật khẩu an toàn. Thay vì lưu mật khẩu ở dạng thô, hệ thống lưu trữ băm của chúng. Khi người dùng nhập mật khẩu, hệ thống băm mật khẩu đã nhập và so sánh với băm đã lưu trong cơ sở dữ liệu.
Ví dụ thực hiện:
import hashlib
def hash_password(password):
return hashlib.sha256(password.encode()).hexdigest()
# Ví dụ sử dụng:
password = "securepassword"
hashed_password = hash_password(password)
print(f"Hash của mật khẩu: {hashed_password}")
2. Kiểm tra tính toàn vẹn của dữ liệu
Hàm băm được sử dụng để kiểm tra tính toàn vẹn của các tập tin và dữ liệu. Ví dụ, để kiểm tra xem tệp có bị thay đổi hoặc hư hỏng trong quá trình truyền không.
Ví dụ thực hiện:
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()
# Ví dụ sử dụng:
file_hash = get_file_hash('example.txt')
print(f"SHA-256 hash của tệp: {file_hash}")
3. Công cụ tìm kiếm và chỉ mục hóa
Các công cụ tìm kiếm sử dụng hàm băm để tạo chỉ mục và tìm kiếm thông tin nhanh chóng. Mỗi tài liệu được chỉ mục theo các từ khóa, và hàm băm giúp tìm kiếm nhanh các tài liệu chứa từ khóa cụ thể.
Ví dụ thực hiện:
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
# Ví dụ sử dụng:
text = "This is an example text for indexing"
index = create_index(text)
print(f"Chỉ mục: {index}")
10.3 Tối ưu hóa tìm kiếm bằng cách sử dụng hàm băm
1. Sử dụng bảng băm để tìm kiếm trùng lặp
Bảng băm cho phép tìm kiếm trùng lặp trong một mảng một cách nhanh chóng bằng cách so sánh các giá trị hash của các phần tử.
Ví dụ thực hiện:
def find_duplicates(arr):
seen = set()
duplicates = []
for item in arr:
if item in seen:
duplicates.append(item)
else:
seen.add(item)
return duplicates
# Ví dụ sử dụng:
arr = [1, 2, 3, 2, 4, 5, 6, 4, 7]
print(find_duplicates(arr)) # Kết quả: [2, 4]
2. Tối ưu hóa tìm kiếm cặp có tổng cho trước
Bảng băm cho phép tìm kiếm cặp số trong một mảng, có tổng bằng giá trị đã cho một cách hiệu quả.
Ví dụ thực hiện:
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
# Ví dụ sử dụng:
arr = [2, 4, 3, 7, 8, -2, 10, -1]
target_sum = 6
print(find_pairs_with_sum(arr, target_sum)) # Kết quả: [(4, 2), (3, 3), (8, -2)]
10.4 Ví dụ sử dụng hàm băm trong các thuật toán khác nhau
1. Đếm số lượng từ trong văn bản
Sử dụng bảng băm để đếm số lần xuất hiện của mỗi từ trong văn bản.
Ví dụ thực hiện:
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
# Ví dụ sử dụng:
text = "this is a test this is only a test"
print(count_words(text)) # Kết quả: {'this': 2, 'is': 2, 'a': 2, 'test': 2, 'only': 1}
2. Kiểm tra giao nhau của hai mảng
Kiểm tra xem hai mảng có giao nhau không (có ít nhất một phần tử chung).
Ví dụ thực hiện:
def has_intersection(arr1, arr2):
set1 = set(arr1)
for item in arr2:
if item in set1:
return True
return False
# Ví dụ sử dụng:
arr1 = [1, 2, 3, 4]
arr2 = [3, 5, 6, 7]
arr3 = [8, 9, 10]
print(has_intersection(arr1, arr2)) # Kết quả: True
print(has_intersection(arr1, arr3)) # Kết quả: False
3. Kiểm tra tính duy nhất của các phần tử trong mảng
Kiểm tra xem trong mảng có chỉ chứa các phần tử duy nhất hay không.
Ví dụ thực hiện:
def all_unique(arr):
seen = set()
for item in arr:
if item in seen:
return False
seen.add(item)
return True
# Ví dụ sử dụng:
arr1 = [1, 2, 3, 4, 5]
arr2 = [1, 2, 3, 4, 5, 3]
print(all_unique(arr1)) # Kết quả: True
print(all_unique(arr2)) # Kết quả: False
GO TO FULL VERSION