Hướng dẫn cơ bản về Hashing trong DBMS

Xin chào các pháp sư cơ sở dữ liệu tương lai! Hôm nay, chúng ta sẽ cùng lặn vào thế giới kỳ diệu của hashing trong Hệ quản trị cơ sở dữ liệu (DBMS). Đừng lo lắng nếu bạn chưa từng viết một dòng mã trước đây - tôi sẽ là người bạn đồng hành thân thiện của bạn trong chuyến phiêu lưu này. Nào, lấy cây phép (bàn phím) của bạn và cùng bắt đầu nhé!

Hashing là gì?

Trước khi chúng ta nhảy vào chi tiết, hãy hiểu về hashing là gì. Hãy tưởng tượng bạn đang tổ chức một thư viện khổng lồ. Thay vì sắp xếp sách theo thứ tự chữ cái, bạn quyết định cấp một số duy nhất cho mỗi sách dựa trên tiêu đề của nó. Đó chính xác là điều mà hashing làm trong cơ sở dữ liệu - nó chuyển đổi dữ liệu thành một giá trị cố định kích thước (gọi là hash) để dễ dàng lưu trữ và truy xuất.

Ví dụ đơn giản về Hashing

Hãy bắt đầu với một ví dụ cơ bản bằng Python để minh họa hashing:

def simple_hash(string):
total = 0
for char in string:
total += ord(char)
return total % 10

print(simple_hash("Hello"))  # Output: 2
print(simple_hash("World"))  # Output: 7

Trong ví dụ này, chúng ta đang tạo một hàm hash rất đơn giản. Nó cộng tổng giá trị ASCII của mỗi ký tự trong chuỗi và sau đó sử dụng phép toán modulo để lấy một số介于 0 và 9. Đây là một dạng rất cơ bản của hashing, nhưng nó cho bạn một ý tưởng về cách nó hoạt động.

Cách tổ chức Hash

Bây giờ chúng ta đã có một hiểu biết cơ bản về hashing, hãy nhìn vào cách nó được tổ chức trong cơ sở dữ liệu.

Bảng Hash

Bảng hash là xương sống của tổ chức hash. Hãy tưởng tượng một bảng rất đặc biệt nơi mỗi phần tử (thường được gọi là bucket) có thể lưu trữ nhiều mục.

Dưới đây là một implement đơn giản của bảng hash bằng Python:

class HashTable:
def __init__(self, size):
self.size = size
self.table = [[] for _ in range(self.size)]

def hash_function(self, key):
return hash(key) % self.size

def insert(self, key, value):
hash_key = self.hash_function(key)
self.table[hash_key].append((key, value))

def get(self, key):
hash_key = self.hash_function(key)
for k, v in self.table[hash_key]:
if k == key:
return v
return None

# Sử dụng bảng hash của chúng ta
ht = HashTable(10)
ht.insert("apple", 5)
ht.insert("banana", 7)
print(ht.get("apple"))  # Output: 5
print(ht.get("grape"))  # Output: None

Bảng hash này sử dụng hàm hash()内置 của Python và phép toán modulo để xác định nơi lưu trữ mỗi cặp khóa-giá trị. Khi chúng ta muốn truy xuất một giá trị, chúng ta sử dụng cùng một quá trình để tìm nơi nó nên được lưu trữ.

Hash tĩnh

Hash tĩnh giống như việc có một số lượng cố định kệ trong thư viện của bạn. Bạn biết chính xác số lượng sách bạn có thể lưu trữ, nhưng bạn có thể gặp vấn đề nếu bạn có quá nhiều sách về một chủ đề.

Ưu và nhược điểm của Hash tĩnh

Ưu điểm	Nhược điểm
Dễ dàng triển khai	Có thể dẫn đến phân phối không đều
Nhanh cho bộ dữ liệu nhỏ	Không linh hoạt với bộ dữ liệu tăng trưởng
Hiệu suất dự đoán được	Có thể lãng phí không gian

Tràn Bucket

Đôi khi, hàm hash của chúng ta có thể gửi quá nhiều mục vào cùng một bucket. Điều này được gọi là tràn bucket, và nó giống như việc cố gắng nhét quá nhiều sách vào một kệ.

Xử lý Tràn Bucket

Có nhiều cách để xử lý tràn bucket:

1. Chaining: Mỗi bucket chứa một danh sách liên kết của các mục.
2. Open Addressing: Nếu một bucket đầy, chúng ta tìm bucket trống tiếp theo.

Hãy implement chaining trong bảng hash trước đó của chúng ta:

class ChainedHashTable:
def __init__(self, size):
self.size = size
self.table = [[] for _ in range(self.size)]

def hash_function(self, key):
return hash(key) % self.size

def insert(self, key, value):
hash_key = self.hash_function(key)
for item in self.table[hash_key]:
if item[0] == key:
item[1] = value
return
self.table[hash_key].append([key, value])

def get(self, key):
hash_key = self.hash_function(key)
for k, v in self.table[hash_key]:
if k == key:
return v
return None

# Sử dụng bảng hash liên kết của chúng ta
cht = ChainedHashTable(10)
cht.insert("apple", 5)
cht.insert("banana", 7)
cht.insert("cherry", 3)
print(cht.get("apple"))  # Output: 5
print(cht.get("cherry"))  # Output: 3

Trong implement này, mỗi bucket có thể chứa nhiều cặp khóa-giá trị, giải quyết vấn đề tràn bucket.

Hash động

Hash động giống như việc có một thư viện ma thuật có thể phát triển thêm kệ khi bạn cần. Nó linh hoạt hơn hash tĩnh và có thể thích ứng với bộ dữ liệu tăng trưởng.

Hash giãn nở

Một hình thức phổ biến của hash động là hash giãn nở. Nó sử dụng một cấu trúc thư mục có thể tăng hoặc giảm kích thước khi cần.

Dưới đây là một implement đơn giản của hash giãn nở:

class ExtendibleHashTable:
def __init__(self, bucket_size=2):
self.bucket_size = bucket_size
self.global_depth = 1
self.directory = [[] for _ in range(2**self.global_depth)]

def hash_function(self, key):
return hash(key) % (2**self.global_depth)

def insert(self, key, value):
hash_key = self.hash_function(key)
if len(self.directory[hash_key]) < self.bucket_size:
self.directory[hash_key].append((key, value))
else:
self._split(hash_key)
self.insert(key, value)

def _split(self, index):
self.global_depth += 1
new_directory = [[] for _ in range(2**self.global_depth)]
for i, bucket in enumerate(self.directory):
new_index = i if i < index else i + 2**(self.global_depth-1)
new_directory[new_index] = bucket
self.directory = new_directory

def get(self, key):
hash_key = self.hash_function(key)
for k, v in self.directory[hash_key]:
if k == key:
return v
return None

# Sử dụng bảng hash giãn nở của chúng ta
eht = ExtendibleHashTable()
eht.insert("apple", 5)
eht.insert("banana", 7)
eht.insert("cherry", 3)
eht.insert("date", 9)
print(eht.get("apple"))  # Output: 5
print(eht.get("date"))   # Output: 9

Implement này cho phép bảng hash tăng trưởng động khi thêm nhiều mục.

Tổ chức và Hoạt động

Bây giờ chúng ta đã bao gồm các nguyên tắc cơ bản của hashing và một số implement, hãy tóm tắt các hoạt động chính và độ phức tạp của chúng:

Hoạt động	Độ phức tạp trung bình	Trường hợp xấu nhất
Chèn	O(1)	O(n)
Xóa	O(1)	O(n)
Tìm kiếm	O(1)	O(n)

Trường hợp trung bình thường rất nhanh, đó là lý do tại sao hashing rất phổ biến. Tuy nhiên, trong trường hợp xấu nhất (khi tất cả các mục hash vào cùng một bucket), hiệu suất có thể suy giảm xuống cấp độ của danh sách liên kết.

Kết luận

Chúc mừng! Bạn đã刚刚 bước vào thế giới của hashing trong DBMS. Nhớ rằng, hashing là về việc tìm kiếm sự cân bằng giữa tốc độ và không gian. Nó là một công cụ mạnh mẽ, và khi được sử dụng đúng cách, nó có thể tăng tốc đáng kể các hoạt động cơ sở dữ liệu của bạn.

Khi bạn tiếp tục hành trình trong khoa học máy tính, bạn sẽ gặp hashing trong nhiều ngữ cảnh khác - từ lưu trữ mật khẩu đến hệ thống cache. Mỗi lần bạn sử dụng từ điển trong Python hoặc đối tượng trong JavaScript, bạn đều được hưởng lợi từ phép màu của hashing!

Tiếp tục luyện tập, 保持好奇心, và chúc bạn vui vẻ khi lập mã!

Credits: Image by storyset