Thuật toán Hash Table

Giới thiệu thuật toán

“Hash table” (bảng băm) là một cấu trúc dữ liệu cho phép lưu trữ và truy xuất thông tin dựa trên khóa (key) và giá trị (value). Thuật toán hash table sử dụng một hàm băm (hash function) để chuyển đổi khóa thành một chỉ số (index) trong một mảng. Mỗi phần tử trong mảng này chứa một danh sách liên kết (linked list) các cặp khóa-giá trị. Khi cần truy xuất giá trị của một khóa, thuật toán sẽ áp dụng hàm băm để tìm chỉ số của khóa trong mảng, và sau đó duyệt qua danh sách liên kết tại chỉ số này để tìm giá trị tương ứng.

Thuật toán hash table có thể được mô tả bằng các bước sau:

  1. Khởi tạo một mảng có kích thước cố định.
  2. Định nghĩa hàm băm để chuyển đổi khóa thành chỉ số trong mảng. Hàm băm phải trả về một giá trị nguyên không âm nằm trong khoảng từ 0 đến kích thước của mảng.
  3. Khi thêm một cặp khóa-giá trị vào hash table, áp dụng hàm băm để tìm chỉ số của khóa trong mảng, sau đó thêm cặp khóa-giá trị vào danh sách liên kết tại chỉ số này.
  4. Khi tìm kiếm giá trị của một khóa, áp dụng hàm băm để tìm chỉ số của khóa trong mảng, sau đó duyệt qua danh sách liên kết tại chỉ số này để tìm giá trị tương ứng.

Các bước thực hiện thuật toán Hash table

Các bước thực hiện thuật toán Hash Table như sau:

  1. Khởi tạo một mảng có kích thước xác định trước, thường là một số nguyên tố, để lưu trữ các giá trị của khóa.
  2. Viết một hàm băm (hash function) để chuyển đổi khóa sang một chỉ số trong mảng đã khởi tạo. Hàm băm này cần đảm bảo tính phân tán đều các khóa trong mảng.
  3. Khi có một cặp khóa-giá trị được thêm vào hash table, chúng ta sử dụng hàm băm để chuyển đổi khóa thành chỉ số trong mảng. Nếu chỉ số này chưa được sử dụng, chúng ta lưu trữ cặp khóa-giá trị tại đó. Nếu chỉ số này đã được sử dụng, chúng ta sử dụng một phương thức xử lý va chạm (collision resolution) để xác định vị trí lưu trữ tiếp theo cho cặp khóa-giá trị.
  4. Khi truy xuất giá trị của một khóa, chúng ta sử dụng hàm băm để chuyển đổi khóa thành chỉ số trong mảng, sau đó tìm kiếm cặp khóa-giá trị tại chỉ số đó. Nếu tìm thấy, chúng ta trả về giá trị của khóa đó. Nếu không tìm thấy, chúng ta trả về None.
  5. Khi xóa một khóa, chúng ta sử dụng hàm băm để chuyển đổi khóa thành chỉ số trong mảng, sau đó xóa cặp khóa-giá trị tại đó. Nếu chỉ số này đã được sử dụng và chứa cặp khóa-giá trị cần xóa, chúng ta xóa cặp này và trả về giá trị của khóa đó. Nếu không tìm thấy cặp khóa-giá trị tại chỉ số này, chúng ta trả về None.

Cài đặt thuật toán Hash Table

Đây là một ví dụ về cách cài đặt thuật toán hash table bằng Python, sử dụng danh sách liên kết để lưu trữ các khóa-giá trị:

class Node:
    def __init__(self, key, value):
        self.key = key
        self.value = value
        self.next = None
        
class HashTable:
    def __init__(self, size):
        self.size = size
        self.table = [None] * size
        
    def hash_function(self, key):
        return key % self.size
    
    def add(self, key, value):
        index = self.hash_function(key)
        if self.table[index] is None:
            self.table[index] = Node(key, value)
        else:
            node = self.table[index]
            while node.next is not None and node.key != key:
                node = node.next
            if node.key == key:
                node.value = value
            else:
                node.next = Node(key, value)
                
    def get(self, key):
        index = self.hash_function(key)
        node = self.table[index]
        while node is not None and node.key != key:
            node = node.next
        if node is None:
            return None
        else:
            return node.value

Trong đó:

Node là một lớp đại diện cho một nút trong danh sách liên kết. Mỗi nút bao gồm một khóa (key), một giá trị (value) và một con trỏ đến nút tiếp theo (next).

HashTable là lớp chứa thuật toán hash table. Trong hàm khởi tạo, chúng ta khởi tạo một mảng có kích thước bằng với size, và mỗi phần tử trong mảng ban đầu đều là None.

Hàm hash_function chuyển đổi khóa thành một chỉ số trong mảng, bằng cách lấy phần dư của khóa cho size.

Hàm add thêm một cặp khóa-giá trị vào hash table. Đầu tiên, chúng ta sử dụng hash_function để tìm chỉ số của khóa trong mảng. Nếu phần tử tại chỉ số này là None, chúng ta tạo một nút mới và gán cho phần tử này. Nếu không, chúng ta duyệt qua danh sách liên kết tại chỉ số này để tìm nút có khóa bằng với khóa cần thêm. Nếu tìm thấy, chúng ta cập nhật giá trị của nút này. Nếu không tìm thấy, chúng ta tạo một nút mới và thêm vào cuối danh sách liên kết.

Hàm get trả về giá trị của một khóa trong hash table. Đầu tiên, chúng ta sử dụng hash_function để tìm chỉ số của khóa trong mảng. Sau đó, chúng ta duyệt qua danh sách liên kết tại chỉ số này để tìm nút có khóa bằng với khóa cần tìm. Nếu tìm thấy, chúng ta trả về giá trị của nút đó. Nếu không tìm thấy, chúng ta trả về None.

Ví dụ sử dụng thuật toán hash table này:

hash_table = HashTable(5)
hash_table.add(1, "One")
hash_table.add(2, "Two")
hash_table.add(6, "Six")
print(hash_table.get(1))  # "One"
print(hash_table.get(2))  # "Two"
print(hash_table.get(3))  # None
print(hash_table.get(6))  # "Six"

Trong ví dụ này, chúng ta tạo một hash table có kích thước là 5. Sau đó, chúng ta thêm các cặp khóa-giá trị vào hash table và sử dụng hàm get để truy xuất giá trị của một số khóa. Kết quả trả về sẽ là giá trị tương ứng của khóa đó, hoặc None nếu khóa không có trong hash table.

Đánh giá độ phức tạp của Thuật toán Hash Table

Độ phức tạp của thuật toán Hash Table phụ thuộc vào hàm băm được sử dụng để chuyển đổi khóa thành chỉ số trong mảng và cách xử lý va chạm (collision resolution).

Trong trường hợp tốt nhất, khi không có va chạm và hàm băm phân phối đều các khóa trong mảng, thao tác thêm, truy xuất và xóa đều có độ phức tạp là O(1).

Trong trường hợp xấu nhất, khi tất cả các khóa đều được chuyển đổi thành cùng một chỉ số và phải sử dụng danh sách liên kết để lưu trữ các khóa, độ phức tạp của thao tác thêm, truy xuất và xóa có thể lên đến O(n), với n là số lượng khóa trong hash table.

Tuy nhiên, trong thực tế, với hàm băm và cách xử lý va chạm phù hợp, thuật toán Hash Table thường đạt được hiệu suất rất tốt với độ phức tạp trung bình là O(1) cho các thao tác thêm, truy xuất và xóa.

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *