CodeGym /Các khóa học /Python SELF VI /Nguyên tắc hoạt động của bảng băm

Nguyên tắc hoạt động của bảng băm

Python SELF VI

Mức độ , Bài học

Có sẵn

6.1 Định nghĩa bảng băm và cấu trúc của nó

Bảng băm – là một cấu trúc dữ liệu cho phép tìm kiếm, chèn và xóa phần tử nhanh chóng bằng cách sử dụng hàm băm để tính toán chỉ số trong mảng hoặc danh sách. Bảng băm thường được sử dụng để triển khai các mảng kết hợp, còn được gọi là từ điển.

Các khía cạnh quan trọng của bảng băm

Mảng – là thành phần chính của bảng băm, nó lưu trữ các con trỏ đến các phần tử hoặc danh sách các phần tử.

Hàm băm: Hàm chuyển đổi các khóa của từ điển thành các chỉ số trong mảng.

Xung đột: Tình trạng hai khóa khác nhau có cùng giá trị băm. Để giải quyết xung đột, nhiều phương pháp được sử dụng như chuỗi (chaining) hoặc địa chỉ mở (open addressing).

Ví dụ về từ điển:


{
   "apple": 101,
   "banana": 102,
   "cherry": 103
}

Ví dụ về cấu trúc bảng băm:

Chỉ số	Giá trị
0	None
1	[('apple', 101)]
2	None
3	[('banana', 102)]
4	None
5	None
6	None
7	[('cherry', 103)]
8	None
9	None

6.2 Các thao tác chính trong bảng băm

Các thao tác chính trong bảng băm: chèn, tìm kiếm, xóa

1. Chèn (Insertion): Quá trình thêm phần tử mới (cặp khóa-giá trị) vào bảng băm.

Các bước chèn:

Tính giá trị băm của khóa bằng cách sử dụng hàm băm.
Tìm chỉ số trong mảng dựa trên giá trị băm.
Nếu trong mảng tại chỉ số đó đã có phần tử (xung đột), thì thêm phần tử vào danh sách (trong trường hợp chuỗi) hoặc tìm chỉ số tiếp theo có sẵn (trong trường hợp địa chỉ mở).

Ví dụ về chèn vào bảng băm sử dụng chuỗi:


class HashTable:
    def __init__(self, size):
        self.size = size
        self.table = [None] * size

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

    def insert(self, key, value):
        index = self.hash_function(key)
        if self.table[index] is None:
            self.table[index] = [(key, value)]
        else:
            for i, kv in enumerate(self.table[index]):
                k, v = kv
                if k == key:
                    self.table[index][i] = (key, value)
                    return
            self.table[index].append((key, value))

# Ví dụ sử dụng:
hash_table = HashTable(10)
hash_table.insert("apple", 1)
hash_table.insert("banana", 2)
hash_table.insert("cherry", 3)
print(hash_table.table)

2. Tìm kiếm (Search): Quá trình tìm giá trị theo khóa đã cho trong bảng băm.

Các bước tìm kiếm:

Tính giá trị băm của khóa bằng cách sử dụng hàm băm.
Tìm chỉ số trong mảng dựa trên giá trị băm.
Kiểm tra sự tồn tại của khóa trong danh sách các phần tử (trong trường hợp chuỗi) hoặc tại chỉ số (trong trường hợp địa chỉ mở).

Ví dụ về tìm kiếm trong bảng băm sử dụng chuỗi:


class HashTable:
    def __init__(self, size):
        self.size = size
        self.table = [None] * size

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

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

# Ví dụ sử dụng:
hash_table = HashTable(10)
hash_table.insert("apple", 1)
hash_table.insert("banana", 2)
hash_table.insert("cherry", 3)
print(hash_table.search("banana"))  # Xuất: 2
print(hash_table.search("grape"))   # Xuất: None

3. Xóa (Deletion): Quá trình xóa phần tử (cặp khóa-giá trị) khỏi bảng băm.

Các bước xóa:

Tính giá trị băm của khóa bằng cách sử dụng hàm băm.
Tìm chỉ số trong mảng dựa trên giá trị băm.
Xóa phần tử khỏi danh sách (trong trường hợp chuỗi) hoặc đặt giá trị tại chỉ số thành None (trong trường hợp địa chỉ mở).

Ví dụ về xóa từ bảng băm sử dụng chuỗi:


class HashTable:
    def __init__(self, size):
        self.size = size
        self.table = [None] * size

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

    def insert(self, key, value):
        index = self.hash_function(key)
        if self.table[index] is None:
            self.table[index] = [(key, value)]
        else:
            for i, kv in enumerate(self.table[index]):
                k, v = kv
                if k == key:
                    self.table[index][i] = (key, value)
                    return
            self.table[index].append((key, value))

    def delete(self, key):
        index = self.hash_function(key)
        if self.table[index] is None:
            return
        for i, kv in enumerate(self.table[index]):
            k, v = kv
            if k == key:
                del self.table[index][i]
                return

# Ví dụ sử dụng:
hash_table = HashTable(10)
hash_table.insert("apple", 1)
hash_table.insert("banana", 2)
hash_table.insert("cherry", 3)
print(hash_table.table)
hash_table.delete("banana")
print(hash_table.table)
print(hash_table.search("banana"))  # Xuất: None

6.3 Độ phức tạp thời gian của bảng băm

Độ phức tạp thời gian của các thao tác trong bảng băm

Chèn (Insertion):

Trường hợp trung bình: O(1)
Trường hợp xấu nhất: O(n) (trong trường hợp nhiều xung đột hoặc tất cả phần tử đều rơi vào cùng một vị trí)

Tìm kiếm (Search):

Trường hợp trung bình: O(1)
Trường hợp xấu nhất: O(n) (trong trường hợp nhiều xung đột hoặc tất cả phần tử đều rơi vào cùng một vị trí)

Xóa (Deletion):

Trường hợp trung bình: O(1)
Trường hợp xấu nhất: O(n) (trong trường hợp nhiều xung đột hoặc tất cả phần tử đều rơi vào cùng một vị trí)

Giải thích:

Trường hợp trung bình: Trong trường hợp trung bình, hàm băm phân phối các phần tử đồng đều qua bảng, và mỗi phần tử nằm ở ô riêng của mình, đảm bảo thời gian truy cập cố định O(1).

Trường hợp xấu nhất: Trong trường hợp xấu nhất, tất cả các phần tử đều rơi vào một ô do hàm băm kém hoặc nhiều xung đột. Khi đó bảng băm trở thành danh sách liên kết, và độ phức tạp thời gian của các thao tác trở thành O(n).

6.4 Ví dụ sử dụng bảng băm

1. Triển khai từ điển (mảng kết hợp)

Bảng băm thường được sử dụng để triển khai từ điển, cho phép lưu trữ cặp khóa-giá trị và cung cấp truy cập nhanh theo khóa.

Ví dụ:


# Tạo từ điển
dictionary = {}

# Thêm phần tử
dictionary["apple"] = 1
dictionary["banana"] = 2
dictionary["cherry"] = 3

# Tìm kiếm phần tử
print(dictionary["banana"])  # Xuất: 2

# Xóa phần tử
del dictionary["cherry"]

# Kiểm tra sự tồn tại của khóa
if "apple" in dictionary:
    print("Khóa 'apple' tồn tại trong từ điển")  # Xuất: Khóa 'apple' tồn tại trong từ điển

Bây giờ bạn đã biết thêm một chút về từ điển trong Python và cách nó hoạt động.

2. Bộ nhớ đệm kết quả tính toán

Bảng băm được sử dụng để bộ nhớ đệm kết quả của các tính toán tốn kém để tăng tốc các yêu cầu sau này.

Ví dụ:


# Bộ nhớ đệm để lưu kết quả
cache = {}

def expensive_computation(x):
    if x in cache:
        return cache[x]
    result = x * x  # Ví dụ tính toán tốn kém
    cache[x] = result
    return result

# Sử dụng bộ nhớ đệm
print(expensive_computation(10))  # Xuất: 100 (tính toán và bộ nhớ đệm)
print(expensive_computation(10))  # Xuất: 100 (từ bộ nhớ đệm)

3. Đếm tần suất từ trong văn bản

Bảng băm được sử dụng để đếm số lần xuất hiện của mỗi từ trong văn bản.

Ví dụ:


from collections import defaultdict

text = "this is a simple text with some simple words this is simple"
word_count = defaultdict(int)

for word in text.split():
    word_count[word] += 1

# Xuất kết quả
for word, count in word_count.items():
    print(f"Từ '{word}' xuất hiện {count} lần")

4. Tìm kiếm bản sao trong danh sách

Bảng băm được sử dụng để tìm kiếm bản sao trong danh sách một cách hiệu quả.


def find_duplicates(arr):
    seen = set()
    duplicates = []
    for item in arr:
        if item in seen:
            duplicates.append(item)
        else:
            seen.add(item)
    return duplicates

# Ví dụ sử dụng
arr = [1, 2, 3, 2, 4, 5, 6, 4, 7]
print(find_duplicates(arr))  # Xuất: [2, 4]

Trước Bài học trước

Kế tiếp Bài học tiếp theo

Bình luận

TO VIEW ALL COMMENTS OR TO MAKE A COMMENT,
GO TO FULL VERSION