Bảng băm DSA
Bảng băm
Bảng băm là một cấu trúc dữ liệu được thiết kế để hoạt động nhanh chóng.
Lý do Bảng băm đôi khi được ưa thích thay vì mảng hoặc danh sách liên kết là vì việc tìm kiếm, thêm và xóa dữ liệu có thể được thực hiện rất nhanh chóng, ngay cả đối với lượng lớn dữ liệu.
Trong Danh sách liên kết , việc tìm một người "Bob" mất nhiều thời gian vì chúng ta sẽ phải đi từ nút này sang nút tiếp theo, kiểm tra từng nút cho đến khi tìm thấy nút có "Bob".
Và việc tìm "Bob" trong Mảng có thể nhanh nếu chúng ta biết chỉ mục, nhưng khi chúng ta chỉ biết tên "Bob", chúng ta cần so sánh từng phần tử (như với Danh sách liên kết) và việc đó cần có thời gian.
Tuy nhiên, với Bảng băm, việc tìm kiếm "Bob" được thực hiện rất nhanh vì có một cách để đi thẳng đến nơi "Bob" được lưu trữ, sử dụng một thứ gọi là hàm băm.
Xây dựng bảng băm từ đầu
Để hiểu Bảng Hash là gì, chúng ta hãy thử xây dựng một bảng từ đầu để lưu trữ các tên duy nhất bên trong nó.
Chúng ta sẽ xây dựng Hash Set theo 5 bước:
- Bắt đầu với một mảng.
- Lưu trữ tên bằng hàm băm.
- Tra cứu một phần tử bằng hàm băm.
- Xử lý va chạm.
- Ví dụ và mô phỏng mã Hash Set cơ bản.
Bước 1: Bắt đầu với một mảng
Sử dụng một mảng, chúng ta có thể lưu trữ những tên như thế này:
my_array = ['Pete', 'Jones', 'Lisa', 'Bob', 'Siri']Để tìm "Bob" trong mảng này, chúng ta cần so sánh từng tên, từng phần tử cho đến khi tìm thấy "Bob".
Nếu mảng được sắp xếp theo thứ tự bảng chữ cái, chúng ta có thể sử dụng Tìm kiếm nhị phân để tìm tên nhanh chóng, nhưng việc chèn hoặc xóa tên trong mảng có nghĩa là phải thực hiện một thao tác lớn trong việc dịch chuyển các phần tử trong bộ nhớ.
Để tương tác với danh sách tên thật nhanh, thay vào đó hãy sử dụng Bảng băm hoặc Bộ băm, đây là phiên bản đơn giản của Bảng băm.
Để đơn giản, giả sử có tối đa 10 tên trong danh sách, do đó mảng phải có kích thước cố định gồm 10 phần tử. Khi nói về Bảng băm, mỗi phần tử này được gọi là nhóm .
my_hash_set = [None,None,None,None,None,None,None,None,None,None]Bước 2: Lưu trữ tên bằng hàm băm
Bây giờ đến cách đặc biệt mà chúng ta tương tác với Hash Set mà chúng ta đang tạo.
Chúng tôi muốn lưu trữ tên trực tiếp vào đúng vị trí của nó trong mảng và đây là lúc hàm băm xuất hiện.
Hàm băm có thể được tạo theo nhiều cách, tùy thuộc vào người tạo Bảng băm. Một cách phổ biến là tìm cách chuyển đổi giá trị thành số bằng một trong các số chỉ mục của Hash Set, trong trường hợp này là số từ 0 đến 9. Trong ví dụ của chúng tôi, chúng tôi sẽ sử dụng số Unicode của mỗi ký tự, tóm tắt chúng và thực hiện thao tác modulo 10 để lấy số chỉ mục 0-9.
Ví dụ
def hash_function(value):
sum_of_chars = 0
for char in value:
sum_of_chars += ord(char)
return sum_of_chars % 10
print("'Bob' has hash code:",hash_function('Bob')) Chạy ví dụ »Ký tự "B" có điểm mã Unicode là 66, "o" có 111 và "b" có 98. Cộng chúng lại với nhau chúng ta được 275. Modulo 10 của 275 là 5, vì vậy "Bob" phải được lưu dưới dạng phần tử mảng tại chỉ số 5.
Số được hàm băm trả về được gọi là mã băm .
Số Unicode: Mọi thứ trong máy tính của chúng ta đều được lưu trữ dưới dạng số và điểm mã Unicode là một số duy nhất tồn tại cho mỗi ký tự. Ví dụ ký tự A có số Unicode (còn gọi là điểm mã Unicode) 65 . Chỉ cần thử nó trong mô phỏng dưới đây. Xem trang này để biết thêm thông tin về cách các ký tự được biểu diễn dưới dạng số.
Modulo: Một phép toán, được viết dưới dạng % trong hầu hết các ngôn ngữ lập trình (hoặc \(mod\) trong toán học). Phép toán modulo chia một số với một số khác và đưa ra lời nhắc kết quả. Vì vậy, ví dụ: 7 % 3 sẽ cho chúng ta lời nhắc 1 . (Chia 7 quả táo cho 3 người, nghĩa là mỗi người được 2 quả táo, còn lại 1 quả táo.)
Sau khi lưu trữ "Bob" nơi mã băm cho chúng ta biết (chỉ mục 5), mảng của chúng ta bây giờ trông như thế này:
my_hash_set = [None,None,None,None,None,'Bob',None,None,None,None]Chúng ta có thể sử dụng hàm băm để tìm ra nơi lưu trữ các tên khác "Pete", "Jones", "Lisa" và "Siri".
Sau khi sử dụng hàm băm để lưu trữ những tên đó vào đúng vị trí, mảng của chúng ta trông như thế này:
my_hash_set = [None,'Jones',None,'Lisa',None,'Bob',None,'Siri','Pete',None]Bước 3: Tra cứu tên bằng hàm băm
Bây giờ chúng ta đã thiết lập một Hash Set siêu cơ bản, vì chúng ta không phải kiểm tra từng phần tử của mảng để tìm xem "Pete" có trong đó nữa hay không mà chỉ cần sử dụng hàm băm để đi thẳng đến phần tử bên phải!
Để tìm hiểu xem "Pete" có được lưu trong mảng hay không, chúng tôi đặt tên "Pete" cho hàm băm của mình, chúng tôi lấy lại mã băm 9, chúng tôi đi thẳng đến phần tử ở chỉ số 9, và anh ấy đây. Chúng tôi tìm thấy "Pete" mà không kiểm tra bất kỳ yếu tố nào khác.
Ví dụ
my_hash_set = [None,'Jones',None,'Lisa',None,'Bob',None,'Siri','Pete',None]
def hash_function(value):
sum_of_chars = 0
for char in value:
sum_of_chars += ord(char)
return sum_of_chars % 10
def contains(name):
index = hash_function(name)
return my_hash_set[index] == name
print("'Pete' is in the Hash Set:",contains('Pete')) Chạy ví dụ » Khi xóa tên khỏi Bộ băm, chúng ta cũng có thể sử dụng hàm băm để đi thẳng đến vị trí của tên đó và đặt giá trị phần tử đó thành None .
Bước 4: Xử lý va chạm
Hãy thêm "Stuart" vào Bộ băm của chúng ta.
Chúng tôi đưa "Stuart" vào hàm băm của mình và chúng tôi nhận được mã băm 3, nghĩa là "Stuart" phải được lưu trữ ở chỉ mục 3.
Cố gắng lưu trữ "Stuart" sẽ tạo ra cái gọi là xung đột , vì "Lisa" đã được lưu trữ ở chỉ mục 3.
Để khắc phục xung đột, chúng ta có thể nhường chỗ cho nhiều phần tử hơn trong cùng một nhóm và giải quyết vấn đề xung đột theo cách này được gọi là xâu chuỗi. Chúng ta có thể dành chỗ cho nhiều phần tử hơn trong cùng một nhóm bằng cách triển khai từng nhóm dưới dạng danh sách liên kết hoặc dưới dạng mảng.
Sau khi triển khai mỗi nhóm dưới dạng một mảng, để nhường chỗ cho nhiều tên trong mỗi nhóm, "Stuart" cũng có thể được lưu trữ ở chỉ mục 3 và Bộ băm của chúng ta bây giờ trông như thế này:
my_hash_set = [
[None],
['Jones'],
[None],
['Lisa', 'Stuart'],
[None],
['Bob'],
[None],
['Siri'],
['Pete'],
[None]
]Việc tìm kiếm "Stuart" trong Bộ băm của chúng tôi bây giờ có nghĩa là bằng cách sử dụng hàm băm, chúng tôi sẽ trực tiếp đến nhóm 3, nhưng sau đó trước tiên chúng tôi phải kiểm tra "Lisa" trong nhóm đó, trước khi chúng tôi tìm thấy "Stuart" là phần tử thứ hai trong nhóm 3 .
Bước 5: Ví dụ và mô phỏng mã Hash Set
Để hoàn thành mã Bộ băm rất cơ bản của chúng ta, hãy có các hàm để thêm và tìm kiếm tên trong Bộ băm, hiện là một mảng hai chiều.
Chạy ví dụ mã bên dưới và thử với các giá trị khác nhau để hiểu rõ hơn về cách hoạt động của Bộ băm.
Ví dụ
my_hash_set = [
[None],
['Jones'],
[None],
['Lisa'],
[None],
['Bob'],
[None],
['Siri'],
['Pete'],
[None]
]
def hash_function(value):
return sum(ord(char) for char in value) % 10
def add(value):
index = hash_function(value)
bucket = my_hash_set[index]
if value not in bucket:
bucket.append(value)
def contains(value):
index = hash_function(value)
bucket = my_hash_set[index]
return value in bucket
add('Stuart')
print(my_hash_set)
print('Contains Stuart:',contains('Stuart')) Chạy ví dụ »Hai trang tiếp theo trình bày cách triển khai tốt hơn và chi tiết hơn về Bộ Hast và Bảng băm.
Hãy thử mô phỏng Bộ băm bên dưới để hiểu rõ hơn về nguyên tắc hoạt động của Bộ băm.
Bộ băm
Mã Băm
{{ sumOfAscii }} % 10 = {{currHashCode }}
{{ resultText }} 0
Công dụng của bảng băm
Bảng băm rất tốt cho:
- Kiểm tra xem thứ gì đó có trong bộ sưu tập hay không (như tìm sách trong thư viện).
- Lưu trữ các vật phẩm độc đáo và tìm kiếm nhanh chóng (như lưu trữ số điện thoại).
- Kết nối giá trị với khóa (như liên kết tên với số điện thoại).
Lý do quan trọng nhất khiến Bảng Hash rất phù hợp cho những việc này là vì Bảng Hash so sánh Mảng và Danh sách Liên kết rất nhanh, đặc biệt đối với các tập hợp lớn. Mảng và Danh sách liên kết có độ phức tạp về thời gian \(O(n)\) để tìm kiếm và xóa, trong khi Bảng băm chỉ có \(O(1)\) trung bình! Đọc thêm về độ phức tạp thời gian ở đây .
Bộ băm so với bản đồ băm
Bảng băm có thể là Bộ băm hoặc Bản đồ băm. Hai trang tiếp theo mô tả các cấu trúc dữ liệu này chi tiết hơn.
Đây là cách Bộ băm và Bản đồ băm khác nhau và giống nhau như thế nào:
| Hash Set | Hash Map | |
|---|---|---|
| Uniqueness and storage | Every element is a unique key. | Every entry is a key-value-pair, with a key that is unique, and a value connected it. |
| Use case | Checking if an element is in the set, like checking if a name is on a guest list. | Finding information based on a key, like looking up who owns a certain telephone number. |
| Is it fast to search, add and delete elements? | Yes, average \(O(1)\). | Yes, average \(O(1)\). |
| Is there a hash function that takes the key, generates a hash code, and that is the bucket where the element is stored? | Yes | Yes |
Bảng băm được tóm tắt
Các phần tử của Bảng băm được lưu trữ trong các thùng lưu trữ được gọi là thùng .
Mỗi phần tử của Bảng băm có một phần duy nhất được gọi là khóa .
Hàm băm lấy khóa của một phần tử để tạo mã băm .
Mã băm cho biết phần tử đó thuộc về nhóm nào, vì vậy bây giờ chúng ta có thể truy cập trực tiếp vào phần tử Bảng băm đó: để sửa đổi hoặc xóa nó hoặc chỉ để kiểm tra xem nó có tồn tại hay không. Các hàm băm cụ thể được giải thích chi tiết ở hai trang tiếp theo.
Xung đột xảy ra khi hai phần tử Bảng Hash có cùng mã băm, vì điều đó có nghĩa là chúng thuộc cùng một nhóm . Một vụ va chạm có thể được giải quyết bằng hai cách.
Xâu chuỗi là cách giải quyết xung đột trong hướng dẫn này, bằng cách sử dụng mảng hoặc danh sách liên kết để cho phép nhiều phần tử trong cùng một nhóm.
Địa chỉ mở là một cách khác để giải quyết xung đột. Với địa chỉ mở, nếu chúng ta muốn lưu trữ một phần tử nhưng đã có một phần tử trong nhóm đó thì phần tử đó sẽ được lưu trữ trong nhóm có sẵn tiếp theo. Điều này có thể được thực hiện theo nhiều cách khác nhau, nhưng chúng tôi sẽ không giải thích thêm về địa chỉ mở ở đây.
Phần kết luận
Bảng băm là công cụ mạnh mẽ trong lập trình, giúp bạn quản lý và truy cập dữ liệu hiệu quả.
Việc bạn sử dụng Bộ băm hay Bản đồ băm tùy thuộc vào những gì bạn cần: chỉ để biết liệu có thứ gì đó ở đó hay để tìm thông tin chi tiết về nó.
