Bản đồ băm DSA

Bản đồ băm

Bản đồ 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 mục nhập.

Sử dụng Hash Map, chúng ta có thể tìm kiếm, thêm, sửa đổi và xóa các mục nhập rất nhanh.

Hash Maps được sử dụng để tìm thông tin chi tiết về một cái gì đó.

Trong mô phỏng bên dưới, mọi người được lưu trữ trong Hash Map. Một người có thể được tra cứu bằng số an sinh xã hội duy nhất của một người (khóa Hash Map) và sau đó chúng ta có thể thấy tên của người đó (giá trị Hash Map).

Sẽ dễ hiểu cách Hash Maps hoạt động hơn nếu trước tiên bạn xem hai trang trước về Bảng Hash và Bộ Hash . Điều quan trọng là phải hiểu ý nghĩa của các từ dưới đây.

• Mục nhập: Bao gồm một khóa và một giá trị, tạo thành một cặp khóa-giá trị.
• Khóa: Duy nhất cho mỗi mục trong Hash Map. Được sử dụng để tạo mã băm xác định nhóm mục nhập trong Bản đồ băm. Điều này đảm bảo rằng mọi mục nhập đều có thể được định vị một cách hiệu quả.
• Mã băm: Một số được tạo từ khóa của mục nhập, để xác định mục nhập Hash Map đó thuộc về nhóm nào.
• Nhóm: Bản đồ Hash bao gồm nhiều nhóm hoặc vùng chứa như vậy để lưu trữ các mục nhập.
• Giá trị: Có thể là hầu hết mọi loại thông tin, như tên, ngày sinh và địa chỉ của một người. Giá trị có thể là nhiều loại thông tin khác nhau kết hợp lại.

Tìm mã băm

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

Hàm băm trong mô phỏng ở trên lấy các số trong số an sinh xã hội (không phải dấu gạch ngang), cộng chúng lại với nhau và 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 người được lưu trữ vào một trong mười nhóm có thể có trong Hash Map, theo mã băm của số an sinh xã hội của người đó. Mã băm tương tự được tạo và sử dụng khi chúng tôi muốn tìm kiếm hoặc xóa một người khỏi Bản đồ 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 người trong nhóm tương ứng.

Trong mô phỏng ở trên, Charlotte có số an sinh xã hội 123-4567 . Cộng các số lại với nhau chúng ta có tổng 28 , và modulo 10 của số đó là 8 . Đó là lý do tại sao cô ấy thuộc nhóm 8 .

Truy cập trực tiếp trong Hash Maps

Tìm kiếm Charlotte trong Hash Map, chúng ta phải sử dụng số an sinh xã hội 123-4567 (khóa Hash Map), tạo ra mã băm 8 , như đã giải thích ở trên.

Điều này có nghĩa là chúng ta có thể đi thẳng đến nhóm 8 để lấy tên của cô ấy (giá trị Hash Map) mà không cần tìm kiếm qua các mục khác trong Hash Map.

Trong những trường hợp như thế này, chúng tôi nói rằng Hash Map có thời gian không đổi \(O(1)\) để tìm kiếm, thêm và xóa các mục, tốc độ này thực sự nhanh so với việc sử dụng một mảng hoặc danh sách liên kết.

Tuy nhiên, trong trường hợp xấu nhất, tất cả mọi người đều được lưu trữ trong cùng một nhóm và nếu người mà chúng tôi đang cố gắng tìm là người cuối cùng trong nhóm này, chúng tôi cần so sánh với tất cả các số an sinh xã hội khác trong nhóm đó trước khi chúng tôi tìm thấy người mà chúng tôi đang tìm kiếm.

Trong trường hợp xấu nhất như vậy, Hash Map 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ản đồ Hash nhanh chóng, điều quan trọng là phải có hàm băm sẽ phân phối đồng đều các mục giữa các nhóm và có nhiều nhóm như các mục nhập Bản đồ Hash.

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

Triển khai bản đồ băm

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

Để triển khai Hash Map bằng Python, chúng ta tạo một lớp SimpleHashMap .

Bên trong lớp SimpleHashMap , chúng ta có một phương thức __init__ để khởi tạo Hash Map, 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 Map cơ bản: put , get và remove .

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

 class SimpleHashMap:
    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, key):
        # Sum only the numerical values of the key, ignoring non-numeric characters
        numeric_sum = sum(int(char) for char in key if char.isdigit())
        return numeric_sum % 10  # Perform modulo 10 on the sum

    def put(self, key, value):
        # Add or update a key-value pair
        index = self.hash_function(key)
        bucket = self.buckets[index]
        for i, (k, v) in enumerate(bucket):
            if k == key:
                bucket[i] = (key, value)  # Update existing key
                return
        bucket.append((key, value))  # Add new key-value pair if not found

    def get(self, key):
        # Retrieve a value by key
        index = self.hash_function(key)
        bucket = self.buckets[index]
        for k, v in bucket:
            if k == key:
                return v
        return None  # Key not found

    def remove(self, key):
        # Remove a key-value pair
        index = self.hash_function(key)
        bucket = self.buckets[index]
        for i, (k, v) in enumerate(bucket):
            if k == key:
                del bucket[i]  # Remove the key-value pair
                return

    def print_map(self):
        # Print all key-value pairs in the hash map
        print("Hash Map Contents:")
        for index, bucket in enumerate(self.buckets):
            print(f"Bucket {index}: {bucket}")

Sử dụng lớp SimpleHashMap , chúng ta có thể tạo Hash Map giống như ở đầu trang này:

 class SimpleHashMap:
    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, key):
        # Sum only the numerical values of the key, ignoring non-numeric characters
        numeric_sum = sum(int(char) for char in key if char.isdigit())
        return numeric_sum % 10  # Perform modulo 10 on the sum

    def put(self, key, value):
        # Add or update a key-value pair
        index = self.hash_function(key)
        bucket = self.buckets[index]
        for i, (k, v) in enumerate(bucket):
            if k == key:
                bucket[i] = (key, value)  # Update existing key
                return
        bucket.append((key, value))  # Add new key-value pair if not found

    def get(self, key):
        # Retrieve a value by key
        index = self.hash_function(key)
        bucket = self.buckets[index]
        for k, v in bucket:
            if k == key:
                return v
        return None  # Key not found

    def remove(self, key):
        # Remove a key-value pair
        index = self.hash_function(key)
        bucket = self.buckets[index]
        for i, (k, v) in enumerate(bucket):
            if k == key:
                del bucket[i]  # Remove the key-value pair
                return

    def print_map(self):
        # Print all key-value pairs in the hash map
        print("Hash Map Contents:")
        for index, bucket in enumerate(self.buckets):
            print(f"Bucket {index}: {bucket}")

# Creating the Hash Map from the simulation
hash_map = SimpleHashMap(size=10)

# Adding some entries
hash_map.put("123-4567", "Charlotte")
hash_map.put("123-4568", "Thomas")
hash_map.put("123-4569", "Jens")
hash_map.put("123-4570", "Peter")
hash_map.put("123-4571", "Lisa")
hash_map.put("123-4672", "Adele")
hash_map.put("123-4573", "Michaela")
hash_map.put("123-6574", "Bob")

hash_map.print_map()

# Demonstrating retrieval
print("\nName associated with '123-4570':", hash_map.get("123-4570"))

print("Updating the name for '123-4570' to 'James'")
hash_map.put("123-4570","James")

# Checking if Peter is still there
print("Name associated with '123-4570':", hash_map.get("123-4570"))