Bảng băm, hay còn gọi là Hash Table, là một cấu trúc dữ liệu hiệu quả được sử dụng rộng rãi để lưu trữ các cặp khóa-giá trị (key-value) và cho phép truy cập dữ liệu với tốc độ rất nhanh. Nguyên lý hoạt động của nó dựa trên việc ánh xạ mỗi khóa đến một vị trí cụ thể trong một mảng (hoặc danh sách) thông qua một hàm băm. Về cơ bản, bạn có thể hình dung nó giống như một cuốn từ điển, nơi mỗi từ (khóa) giúp bạn tìm thấy định nghĩa (giá trị) tương ứng một cách nhanh chóng.

Cấu trúc cơ bản của một Bảng băm

Mỗi bảng băm cần một mảng cơ sở để lưu trữ dữ liệu và một hàm băm để tính toán vị trí cho khóa. Khi có xung đột (collision) – tức là hai khóa khác nhau lại băm ra cùng một vị trí – chúng ta sẽ cần một cơ chế để xử lý, chẳng hạn như sử dụng danh sách liên kết (linked list) hoặc một danh sách đơn giản tại mỗi vị trí trong mảng.

Dưới đây là một ví dụ về cách khởi tạo một lớp bảng băm và hàm băm riêng:

class CustomHashTable:
    def __init__(self, initial_capacity=11):
        # Khởi tạo mảng lưu trữ với kích thước cố định, mỗi vị trí mặc định là None
        self.storage_array = [None] * initial_capacity

    def _calculate_hash_index(self, key):
        # Hàm băm nội bộ để chuyển đổi khóa thành chỉ số mảng
        hash_value = 0
        prime_multiplier = 31 # Một số nguyên tố thường dùng để tăng tính phân tán
        
        # Lặp qua từng ký tự của khóa để tính toán giá trị băm
        for char_code in str(key):
            hash_value = (hash_value + ord(char_code) * prime_multiplier) % len(self.storage_array)
        return hash_value

    def display_contents(self):
        # Phương thức hỗ trợ để in ra toàn bộ nội dung của bảng băm
        print("\n--- Nội dung bảng băm ---")
        for idx, slot_data in enumerate(self.storage_array):
            print(f"{idx}: {slot_data}")
        print("-------------------------\n")

Thêm dữ liệu vào Bảng băm (insert_item)

Để thêm một cặp khóa-giá trị mới, trước tiên chúng ta sử dụng hàm băm để tìm chỉ số vị trí trong mảng. Nếu vị trí đó chưa có gì, chúng ta khởi tạo nó thành một danh sách (để xử lý xung đột). Sau đó, cặp khóa-giá trị được thêm vào danh sách tại vị trí đó.

    def insert_item(self, key, value):
        # Tính toán chỉ số vị trí dựa trên khóa
        target_index = self._calculate_hash_index(key)

        # Nếu vị trí đó trống, khởi tạo nó thành một danh sách rỗng
        if self.storage_array[target_index] is None:
            self.storage_array[target_index] = []
        
        # Thêm cặp [khóa, giá trị] vào danh sách tại vị trí đó
        self.storage_array[target_index].append([key, value])

Truy xuất dữ liệu từ Bảng băm (retrieve_value)

Khi muốn lấy giá trị tương ứng với một khóa, chúng ta cũng sử dụng hàm băm để xác định vị trí trong mảng. Sau đó, duyệt qua danh sách các cặp khóa-giá trị tại vị trí đó để tìm khóa khớp và trả về giá trị của nó. Nếu không tìm thấy khóa hoặc vị trí trống, phương thức sẽ trả về None.

    def retrieve_value(self, search_key):
        # Lấy chỉ số băm cho khóa cần tìm
        hash_slot_idx = self._calculate_hash_index(search_key)

        # Kiểm tra xem vị trí đó có dữ liệu không
        if self.storage_array[hash_slot_idx] is not None:
            # Duyệt qua từng cặp khóa-giá trị trong danh sách tại vị trí đó
            for kv_pair in self.storage_array[hash_slot_idx]:
                if kv_pair[0] == search_key: # Nếu khóa khớp
                    return kv_pair[1] # Trả về giá trị
        return None # Trả về None nếu không tìm thấy khóa

Lấy danh sách tất cả các khóa (get_all_keys)

Để thu thập tất cả các khóa hiện có trong bảng băm, chúng ta cần duyệt qua toàn bộ mảng lưu trữ. Tại mỗi vị trí có dữ liệu, chúng ta duyệt qua danh sách các cặp khóa-giá trị và thêm khóa vào một danh sách kết quả.

    def get_all_keys(self):
        found_keys = []
        # Duyệt qua từng "bucket" (danh sách) trong mảng lưu trữ
        for bucket in self.storage_array:
            if bucket is not None:
                # Duyệt qua từng cặp khóa-giá trị trong bucket
                for entry in bucket:
                    found_keys.append(entry[0]) # Thêm khóa vào danh sách kết quả
        return found_keys

Ví dụ hoàn chỉnh và cách sử dụng

Dưới đây là mã nguồn hoàn chỉnh của lớp CustomHashTable cùng với ví dụ minh họa cách sử dụng các phương thức đã triển khai:

class CustomHashTable:
    def __init__(self, initial_capacity=11):
        self.storage_array = [None] * initial_capacity

    def _calculate_hash_index(self, key):
        hash_value = 0
        prime_multiplier = 31
        for char_code in str(key):
            hash_value = (hash_value + ord(char_code) * prime_multiplier) % len(self.storage_array)
        return hash_value

    def display_contents(self):
        print("\n--- Nội dung bảng băm ---")
        for idx, slot_data in enumerate(self.storage_array):
            print(f"{idx}: {slot_data}")
        print("-------------------------\n")

    def insert_item(self, key, value):
        target_index = self._calculate_hash_index(key)
        if self.storage_array[target_index] is None:
            self.storage_array[target_index] = []
        self.storage_array[target_index].append([key, value])

    def retrieve_value(self, search_key):
        hash_slot_idx = self._calculate_hash_index(search_key)
        if self.storage_array[hash_slot_idx] is not None:
            for kv_pair in self.storage_array[hash_slot_idx]:
                if kv_pair[0] == search_key:
                    return kv_pair[1]
        return None

    def get_all_keys(self):
        found_keys = []
        for bucket in self.storage_array:
            if bucket is not None:
                for entry in bucket:
                    found_keys.append(entry[0])
        return found_keys

# Tạo một thể hiện của CustomHashTable
my_item_store = CustomHashTable()

# Thêm các cặp khóa-giá trị
my_item_store.insert_item("ốc vít", 1400)
my_item_store.insert_item("long đền", 50)
my_item_store.insert_item("gỗ", 70)
my_item_store.insert_item("đinh", 200) # Thêm một mục để kiểm tra

# Hiển thị toàn bộ cấu trúc bảng băm
my_item_store.display_contents()

# Lấy giá trị từ bảng băm
print(f"Giá trị của 'ốc vít': {my_item_store.retrieve_value('ốc vít')}")
print(f"Giá trị của 'long đền': {my_item_store.retrieve_value('long đền')}")
print(f"Giá trị của 'gỗ': {my_item_store.retrieve_value('gỗ')}")
print(f"Giá trị của 'sắt': {my_item_store.retrieve_value('sắt')}") # Khóa không tồn tại

# Lấy tất cả các khóa
all_present_keys = my_item_store.get_all_keys()
print(f"\nTất cả các khóa trong bảng băm: {all_present_keys}")