7.1 Định nghĩa xung đột trong bảng băm
Xung đột trong bảng băm xảy ra khi hai khóa khác nhau được băm thành cùng một chỉ số mảng. Điều này dẫn đến hơn một phần tử cố gắng chiếm cùng một ô trong bảng băm.
Ví dụ về xung đột:
Giả sử, chúng ta có một hàm băm đơn giản, trả về phần dư của phép chia khóa cho kích thước bảng. Đối với khóa 5 và 15 với kích thước bảng 10 cả hai khóa sẽ cho cùng một chỉ số: 5 % 10 = 5 và 15 % 10 = 5. Đây là một xung đột.
Thêm một ví dụ nữa:
Giả sử bạn đang tạo một từ điển tên và bạn có một hàm băm đơn giản, trả về chữ cái đầu tiên của tên. Nhưng hóa ra, 80% tên bắt đầu bằng chữ cái "А". Đây không chỉ là một xung đột, mà là một vấn đề.
7.2 Phương pháp giải quyết xung đột – chaining
Có nhiều phương pháp giải quyết xung đột trong bảng băm. Hai phương pháp phổ biến nhất là chaining và open addressing.
Chaining
Lợi ích:
- Dễ dàng thực hiện.
- Hiệu quả khi số lượng xung đột nhỏ.
- Ít phụ thuộc vào mật độ lấp đầy của bảng băm.
Hạn chế:
- Yêu cầu thêm bộ nhớ cho các con trỏ trong danh sách liên kết.
- Hiệu suất có thể giảm khi có nhiều xung đột do chuỗi dài.
Ví dụ về triển khai phương pháp chaining:
Bạn có thể chỉ cần học cách hoạt động của hàm insert, nhưng mình quyết định đưa ra toàn bộ mã cho tiện lợi.
class HashTableChaining:
def __init__(self, size):
self.size = size
self.table = [None] * size
def hash_function(self, key):
return hash(key) % self.size
def insert(self, key, value):
index = self.hash_function(key)
if self.table[index] is None:
self.table[index] = [(key, value)]
else:
for i, kv in enumerate(self.table[index]):
k, v = kv
if k == key:
self.table[index][i] = (key, value)
return
self.table[index].append((key, value))
def search(self, key):
index = self.hash_function(key)
if self.table[index] is None:
return None
for k, v in self.table[index]:
if k == key:
return v
return None
def delete(self, key):
index = self.hash_function(key)
if self.table[index] is None:
return
for i, kv in enumerate(self.table[index]):
k, v = kv
if k == key:
del self.table[index][i]
return
# Ví dụ sử dụng:
hash_table = HashTableChaining(10)
hash_table.insert("apple", 1)
hash_table.insert("banana", 2)
hash_table.insert("cherry", 3)
print(hash_table.search("banana")) # Output: 2
hash_table.delete("banana")
print(hash_table.search("banana")) # Output: None
7.3 Phương pháp số hai – open addressing
Phương pháp open addressing là tìm kiếm ô tiếp theo có sẵn trong mảng nếu xảy ra xung đột. Có nhiều chiến lược khác nhau để tìm ô mới: linear probing, quadratic probing và double hashing.
Lợi ích:
- Không yêu cầu thêm bộ nhớ để lưu trữ con trỏ.
- Dữ liệu được lưu trữ gọn gàng hơn.
Hạn chế:
- Hiệu suất có thể giảm đáng kể khi mật độ lấp đầy bảng cao.
- Yêu cầu nhiều tài nguyên tính toán hơn để giải quyết xung đột.
Ví dụ về các chiến lược open addressing
Linear Probing:
- Probing với bước 1:
index = (index + 1) % size. - Đơn giản, nhưng có thể dẫn đến "clusterization".
Quadratic Probing:
- Probing với bước tăng theo bình phương:
index = (index + i^2) % size. - Giảm vấn đề clusterization, nhưng phức tạp hơn khi triển khai.
Double Hashing:
- Sử dụng hàm băm thứ hai để tính toán bước:
index = (index + i * hash2(key)) % size. - Ít vấn đề với clusterization, nhưng phức tạp hơn khi triển khai.
Ví dụ về triển khai phương pháp open addressing (linear probing): Mình sẽ đưa ra toàn bộ mã hoạt động, để đơn giản bạn có thể chỉ học cách hoạt động của hàm insert
class HashTableOpenAddressing:
def __init__(self, size):
self.size = size
self.table = [None] * size
def hash_function(self, key):
return hash(key) % self.size
def insert(self, key, value):
index = self.hash_function(key)
original_index = index
while self.table[index] is not None:
if self.table[index][0] == key:
self.table[index] = (key, value)
return
index = (index + 1) % self.size
if index == original_index:
raise Exception("Hash table is full")
self.table[index] = (key, value)
def search(self, key):
index = self.hash_function(key)
original_index = index
while self.table[index] is not None:
if self.table[index][0] == key:
return self.table[index][1]
index = (index + 1) % self.size
if index == original_index:
break
return None
def delete(self, key):
index = self.hash_function(key)
original_index = index
while self.table[index] is not None:
if self.table[index][0] == key:
self.table[index] = None
return
index = (index + 1) % self.size
if index == original_index:
break
# Ví dụ sử dụng:
hash_table = HashTableOpenAddressing(10)
hash_table.insert("apple", 1)
hash_table.insert("banana", 2)
hash_table.insert("cherry", 3)
print(hash_table.search("banana")) # Output: 2
hash_table.delete("banana")
print(hash_table.search("banana")) # Output: None
7.4 Ảnh hưởng của xung đột lên bảng băm
Ảnh hưởng của xung đột đến hiệu suất.
Thời gian truy cập trung bình:
- Trong điều kiện lý tưởng (khi không có xung đột), thời gian truy cập trung bình đến các phần tử trong bảng băm là
O(1). - Xung đột làm tăng thời gian truy cập, vì cần xử lý chuỗi hoặc probing ô, tăng số lượng thao tác.
Tăng độ dài chuỗi:
- Trong phương pháp chaining, tăng độ dài chuỗi khi có nhiều xung đột có thể dẫn đến thời gian truy cập tuyến tính
O(n)cho các thao tác tìm kiếm, chèn và xóa. - Chuỗi dài làm tăng số lượng so sánh cần thiết để tìm hoặc chèn phần tử.
Độ phức tạp không gian:
- Trong phương pháp chaining, cần thêm bộ nhớ để lưu trữ con trỏ trong danh sách liên kết.
- Trong phương pháp open addressing, lấp đầy bảng trên một mức nhất định (thường khoảng 70-80%) tăng đáng kể số lượng xung đột và do đó thời gian truy cập.
Clusterization: Trong phương pháp open addressing (đặc biệt là với linear probing) xảy ra clusterization, khi nhiều ô liên tiếp trở nên bận, làm tăng khả năng xảy ra xung đột và giảm hiệu suất.
Ví dụ phân tích ảnh hưởng của xung đột đến hiệu suất:
Điều này dành cho những ai thích tìm hiểu sâu hơn
import time
import random
# Linear Probing
class HashTableOpenAddressing:
def __init__(self, size):
self.size = size
self.table = [None] * size
def hash_function(self, key):
return hash(key) % self.size
def insert(self, key, value):
index = self.hash_function(key)
original_index = index
while self.table[index] is not None:
if self.table[index][0] == key:
self.table[index] = (key, value)
return
index = (index + 1) % self.size
if index == original_index:
raise Exception("Hash table is full")
self.table[index] = (key, value)
def search(self, key):
index = self.hash_function(key)
original_index = index
while self.table[index] is not None:
if self.table[index][0] == key:
return self.table[index][1]
index = (index + 1) % self.size
if index == original_index:
break
return None
# Tạo dữ liệu lớn để chèn
hash_table = HashTableOpenAddressing(1000)
keys = [random.randint(1, 10000) for _ in range(800)]
# Chèn dữ liệu và đo thời gian
start_time = time.time()
for key in keys:
hash_table.insert(key, key)
print(f"Thời gian chèn: {time.time() - start_time:.6f} giây")
# Tìm kiếm dữ liệu và đo thời gian
start_time = time.time()
for key in keys:
hash_table.search(key)
print(f"Thời gian tìm kiếm: {time.time() - start_time:.6f} giây")
GO TO FULL VERSION