Bộ hàm băm DSA

Bộ băm

Bộ băm là một dạng cấu trúc dữ liệu Bảng băm thường chứa một số lượng lớn các phần tử.

Sử dụng Bộ băm, chúng ta có thể tìm kiếm, thêm và xóa các phần tử rất nhanh.

Bộ băm được sử dụng để tra cứu, kiểm tra xem một phần tử có phải là một phần của tập hợp hay không.

Bộ băm lưu trữ các phần tử duy nhất trong các nhóm theo mã băm của phần tử.

• Mã băm: Một số được tạo từ giá trị (khóa) duy nhất của một phần tử, để xác định phần tử Hash Set đó thuộc nhóm nào.
• Các phần tử duy nhất: Một tập hợp băm không thể có nhiều hơn một phần tử có cùng giá trị.
• Nhóm: Bộ băm bao gồm nhiều nhóm hoặc thùng chứa như vậy để lưu trữ các phần tử. Nếu hai phần tử có cùng mã băm thì chúng thuộc cùng một nhóm. Do đó, các nhóm thường được triển khai dưới dạng mảng hoặc danh sách liên kết, vì một nhóm cần có khả năng chứa nhiều hơn một phần tử.

Tìm mã băm

Mã băm được tạo bởi hàm băm .

Hàm băm trong hình ảnh động ở trên lấy tên được ghi trong dữ liệu đầu vào và tổng hợp các điểm mã Unicode cho mỗi ký tự trong tên đó.

Sau đó, hàm băm thực hiện thao tác modulo 10 ( % 10 ) trên tổng các ký tự để lấy mã băm dưới dạng số từ 0 đến 9.

Điều này có nghĩa là một tên được đặt vào một trong mười nhóm có thể có trong Bộ băm, theo mã băm của tên đó. Mã băm tương tự được tạo và sử dụng khi chúng ta muốn tìm kiếm hoặc xóa tên khỏi Bộ băm.

Mã Hash cho phép chúng tôi truy cập ngay lập tức miễn là chỉ có một tên trong nhóm tương ứng.

Truy cập trực tiếp trong bộ băm

Tìm kiếm Peter trong Bộ băm ở trên, có nghĩa là mã băm 2 được tạo ra ( 512 % 10 ) và điều đó hướng chúng ta đến ngay nhóm mà Peter đang ở. Nếu đó là tên duy nhất trong nhóm đó, chúng ta sẽ tìm thấy Peter đúng xa.

Trong những trường hợp như thế này, chúng tôi nói rằng Bộ băm có thời gian không đổi \(O(1)\) để tìm kiếm, thêm và xóa các phần tử, tốc độ này thực sự rất nhanh.

Tuy nhiên, nếu chúng ta tìm kiếm Jens , chúng ta cần tìm kiếm qua các tên khác trong nhóm đó trước khi tìm thấy Jens . Trong trường hợp xấu nhất, tất cả các tên đều nằm trong cùng một nhóm và tên chúng ta đang tìm kiếm là tên cuối cùng. Trong trường hợp xấu nhất như vậy, Bộ băm có độ phức tạp về thời gian \(O(n)\), độ phức tạp về thời gian tương tự như mảng và danh sách liên kết.

Do đó, để giữ cho Bộ băm nhanh, điều quan trọng là phải có hàm băm sẽ phân phối đồng đều các phần tử giữa các nhóm và có nhiều nhóm như các phần tử Bộ băm.

Việc có nhiều nhóm hơn các phần tử Hash Set là một sự lãng phí bộ nhớ và có ít nhóm hơn các phần tử Hash Set là một sự lãng phí thời gian.

Triển khai bộ băm

Bộ băm trong Python thường được thực hiện bằng cách sử dụng kiểu dữ liệu set của Python, nhưng để hiểu rõ hơn về cách hoạt động của Bộ băm, chúng ta sẽ không sử dụng tập hợp đó ở đây.

Để triển khai Bộ băm trong Python, chúng ta tạo một lớp SimpleHashSet .

Bên trong lớp SimpleHashSet , chúng ta có một phương thức __init__ để khởi tạo Hash Set, một phương thức hash_function cho hàm băm và các phương thức cho các hoạt động Hash Set cơ bản: add , contains và remove .

Chúng tôi cũng tạo một phương thức print_set để thấy rõ hơn Bộ Hash trông như thế nào.

 class SimpleHashSet:
    def __init__(self, size=100):
        self.size = size
        self.buckets = [[] for _ in range(size)]  # A list of buckets, each is a list (to handle collisions)

    def hash_function(self, value):
        # Simple hash function: sum of character codes modulo the number of buckets
        return sum(ord(char) for char in value) % self.size

    def add(self, value):
        # Add a value if it's not already present
        index = self.hash_function(value)
        bucket = self.buckets[index]
        if value not in bucket:
            bucket.append(value)

    def contains(self, value):
        # Check if a value exists in the set
        index = self.hash_function(value)
        bucket = self.buckets[index]
        return value in bucket

    def remove(self, value):
        # Remove a value
        index = self.hash_function(value)
        bucket = self.buckets[index]
        if value in bucket:
            bucket.remove(value)

    def print_set(self):
        # Print all elements in the hash set
        print("Hash Set Contents:")
        for index, bucket in enumerate(self.buckets):
            print(f"Bucket {index}: {bucket}")

Sử dụng lớp SimpleHashSet , chúng ta có thể tạo Bộ băm tương tự như ở đầu trang này:

 class SimpleHashSet:
    def __init__(self, size=100):
        self.size = size
        self.buckets = [[] for _ in range(size)]  # A list of buckets, each is a list (to handle collisions)

    def hash_function(self, value):
        # Simple hash function: sum of character codes modulo the number of buckets
        return sum(ord(char) for char in value) % self.size

    def add(self, value):
        # Add a value if it's not already present
        index = self.hash_function(value)
        bucket = self.buckets[index]
        if value not in bucket:
            bucket.append(value)

    def contains(self, value):
        # Check if a value exists in the set
        index = self.hash_function(value)
        bucket = self.buckets[index]
        return value in bucket

    def remove(self, value):
        # Remove a value
        index = self.hash_function(value)
        bucket = self.buckets[index]
        if value in bucket:
            bucket.remove(value)

    def print_set(self):
        # Print all elements in the hash set
        print("Hash Set Contents:")
        for index, bucket in enumerate(self.buckets):
            print(f"Bucket {index}: {bucket}")

# Creating the Hash Set from the simulation
hash_set = SimpleHashSet(size=10)

hash_set.add("Charlotte")
hash_set.add("Thomas")
hash_set.add("Jens")
hash_set.add("Peter")
hash_set.add("Lisa")
hash_set.add("Adele")
hash_set.add("Michaela")
hash_set.add("Bob")

hash_set.print_set()

print("\n'Peter' is in the set:",hash_set.contains('Peter'))
print("Removing 'Peter'")
hash_set.remove('Peter')
print("'Peter' is in the set:",hash_set.contains('Peter'))
print("'Adele' has hash code:",hash_set.hash_function('Adele'))