Bảng băm trong cấu trúc dữ liệu: Python Ví dụ

Băm là gì?

Giá trị băm là một giá trị có độ dài cố định và được tạo bằng công thức toán học. Giá trị băm được sử dụng trong nén dữ liệu, mật mã, v.v. Trong lập chỉ mục dữ liệu, giá trị băm được sử dụng vì chúng có kích thước độ dài cố định bất kể giá trị được sử dụng để tạo ra chúng. Nó làm cho các giá trị băm chiếm không gian tối thiểu so với các giá trị khác có độ dài khác nhau.

Hàm băm sử dụng thuật toán toán học để chuyển khóa thành hàm băm. Xung đột xảy ra khi hàm băm tạo ra cùng một giá trị băm cho nhiều khóa.

Bảng băm là gì?

A BẢNG Băm là cấu trúc dữ liệu lưu trữ các giá trị bằng cách sử dụng một cặp khóa và giá trị. Mỗi giá trị được gán một khóa duy nhất được tạo bằng hàm băm.

Tên của khóa được sử dụng để truy cập giá trị liên quan của nó. Điều này giúp tìm kiếm giá trị trong bảng băm rất nhanh, bất kể số lượng mục trong bảng băm.

Hàm băm

Ví dụ: nếu chúng tôi muốn lưu trữ hồ sơ nhân viên và mỗi nhân viên được xác định duy nhất bằng mã số nhân viên.

Chúng ta có thể sử dụng mã số nhân viên làm khóa và gán dữ liệu nhân viên làm giá trị.

Cách tiếp cận trên sẽ yêu cầu thêm không gian trống theo thứ tự (m*n²) trong đó biến m là kích thước của mảng, và biến n là số chữ số của mã số nhân viên. Cách tiếp cận này gây ra vấn đề về không gian lưu trữ.

Hàm băm giải quyết vấn đề trên bằng cách lấy mã số nhân viên và sử dụng nó để tạo ra giá trị số nguyên băm, các chữ số cố định và tối ưu hóa không gian lưu trữ. Mục đích của hàm băm là tạo khóa sẽ được sử dụng để tham chiếu giá trị mà chúng ta muốn lưu trữ. Hàm chấp nhận giá trị cần lưu sau đó sử dụng thuật toán để tính giá trị của khóa.

Sau đây là một ví dụ về một hàm băm đơn giản

h(k) = k₁ % m

ĐÂY,

h(k) là hàm băm chấp nhận tham số k. Tham số k là giá trị mà chúng ta muốn tính khóa.
k₁ % m là thuật toán cho hàm băm của chúng tôi trong đó k1 là giá trị chúng tôi muốn lưu trữ và m là kích thước của danh sách. Chúng tôi sử dụng toán tử mô đun để tính toán khóa.

Ví dụ

Giả sử chúng ta có một danh sách có kích thước cố định là 3 và các giá trị sau

[1,2,3]

Chúng ta có thể sử dụng công thức trên để tính toán vị trí mà mỗi giá trị sẽ chiếm giữ.

Hình ảnh sau đây hiển thị các chỉ mục có sẵn trong bảng băm của chúng tôi.

Bước 1) Tính vị trí sẽ bị chiếm bởi giá trị đầu tiên như vậy

h(1) = 1 % 3

= 1

Giá trị 1 sẽ chiếm không gian trên chỉ số 1

Bước 2) Tính vị trí sẽ bị chiếm bởi giá trị thứ hai

h(2) = 2 % 3

= 2

Giá trị 2 sẽ chiếm không gian trên chỉ số 2

Bước 3) Tính vị trí sẽ bị chiếm bởi giá trị thứ ba.

h(3) = 3 % 3

= 0

Giá trị 3 sẽ chiếm không gian trên chỉ số 0

Kết quả cuối cùng

Bảng băm được điền của chúng tôi bây giờ sẽ như sau.

Phẩm chất của một hàm băm tốt

Một hàm băm tốt phải có những đặc điểm sau.

Công thức tạo hàm băm phải sử dụng giá trị của dữ liệu được lưu trữ trong thuật toán.
Hàm băm sẽ tạo ra các giá trị băm duy nhất ngay cả đối với dữ liệu đầu vào có cùng số lượng.
Chức năng này sẽ giảm thiểu số lượng va chạm. Xung đột xảy ra khi cùng một giá trị được tạo cho nhiều giá trị.
Các giá trị phải được phân phối nhất quán trên toàn bộ các giá trị băm có thể có.

Va chạm

Xung đột xảy ra khi thuật toán tạo ra cùng một giá trị băm cho nhiều giá trị.

Hãy xem xét ví dụ sau.

Giả sử chúng ta có danh sách các giá trị sau

[3,2,9,11,7]

Giả sử kích thước của bảng băm là 7 và chúng ta sẽ sử dụng công thức (k₁ % m) trong đó m là kích thước của bảng băm.

Bảng sau đây hiển thị các giá trị băm sẽ được tạo ra.

Key	Thuật toán băm (k1 % m)	Giá trị băm
3	3% 7	3
2	3% 7	2
9	3% 7	2
11	3% 7	4
7	3% 7	0

Như chúng ta có thể thấy từ các kết quả trên, giá trị 2 và 9 có cùng giá trị băm và chúng ta không thể lưu trữ nhiều hơn một giá trị ở mỗi vị trí.

Bài toán đã cho có thể được giải quyết bằng cách sử dụng chuỗi hoặc thăm dò. Các phần sau sẽ thảo luận chi tiết về chuỗi và thăm dò.

Xâu chuỗi

Xâu chuỗi là một kỹ thuật được sử dụng để giải quyết vấn đề xung đột bằng cách sử dụng danh sách liên kết mà mỗi danh sách có chỉ mục duy nhất.

Hình ảnh sau đây trực quan hóa danh sách được nối trông như thế nào

Cả 2 và 9 đều có cùng chỉ mục nhưng chúng được lưu trữ dưới dạng danh sách liên kết. Mỗi danh sách có một mã định danh duy nhất.

Lợi ích của danh sách chuỗi

Sau đây là những lợi ích của danh sách nối tiếp:

Danh sách chuỗi có hiệu suất tốt hơn khi chèn dữ liệu vì thứ tự chèn là O(1).
Không cần thiết phải thay đổi kích thước bảng băm sử dụng danh sách chuỗi.
Nó có thể dễ dàng chứa một số lượng lớn các giá trị miễn là có không gian trống.

Thăm dò

Kỹ thuật khác được sử dụng để giải quyết xung đột là thăm dò. Khi sử dụng phương pháp thăm dò, nếu xảy ra xung đột, chúng ta có thể chỉ cần tiếp tục và tìm một khe trống để lưu trữ giá trị của mình.

Sau đây là các phương pháp thăm dò:

Phương pháp	Mô tả
Thăm dò tuyến tính	Đúng như tên gọi, phương pháp này tìm kiếm các khe trống bắt đầu tuyến tính từ vị trí xảy ra va chạm và di chuyển về phía trước. Nếu đã đến cuối danh sách và không tìm thấy chỗ trống nào. Việc thăm dò bắt đầu ở đầu danh sách.
thăm dò bậc hai	Phương pháp này sử dụng các biểu thức đa thức bậc hai để tìm vị trí trống tiếp theo.
Double Băm	Kỹ thuật này sử dụng thuật toán hàm băm thứ cấp để tìm vị trí trống tiếp theo.

Sử dụng ví dụ trên của chúng tôi, bảng băm sau khi sử dụng thăm dò sẽ xuất hiện như sau:

Hoạt động bảng băm

Sau đây là Operacác chức năng được hỗ trợ bởi bảng Hash:

chèn - điều này Operation được sử dụng để thêm một phần tử vào bảng băm
Tìm kiếm - điều này Operation được sử dụng để tìm kiếm các phần tử trong bảng băm bằng phím
xóa - điều này Operation được sử dụng để xóa các phần tử khỏi bảng băm

Thao tác chèn dữ liệu

Thao tác chèn được sử dụng để lưu trữ các giá trị trong bảng băm. Khi một giá trị mới được lưu trữ trong bảng băm, nó sẽ được gán một số chỉ mục. Số chỉ mục được tính bằng hàm băm. Hàm băm giải quyết mọi xung đột xảy ra khi tính số chỉ mục.

Tìm kiếm hoạt động dữ liệu

Hoạt động tìm kiếm được sử dụng để tra cứu các giá trị trong bảng băm bằng số chỉ mục. Thao tác tìm kiếm trả về giá trị được liên kết với số chỉ mục tìm kiếm. Ví dụ: nếu chúng ta lưu trữ giá trị 6 tại chỉ mục 2 thì thao tác tìm kiếm với chỉ mục số 2 sẽ trả về giá trị 6.

Thao tác xóa dữ liệu

Hoạt động xóa được sử dụng để xóa một giá trị khỏi bảng băm. Để xóa OperaViệc này được thực hiện bằng cách sử dụng số chỉ mục. Sau khi một giá trị đã bị xóa, số chỉ mục sẽ được giải phóng. Nó có thể được sử dụng để lưu trữ các giá trị khác bằng cách sử dụng thao tác chèn.

Triển khai bảng băm với Python Ví dụ

Hãy xem một ví dụ đơn giản tính giá trị băm của khóa

def hash_key( key, m):
    return key % m


m = 7

print(f'The hash value for 3 is {hash_key(3,m)}')
print(f'The hash value for 2 is {hash_key(2,m)}')
print(f'The hash value for 9 is {hash_key(9,m)}')
print(f'The hash value for 11 is {hash_key(11,m)}')
print(f'The hash value for 7 is {hash_key(7,m)}')

Giải thích mã bảng băm

ĐÂY,

Xác định hàm hash_key chấp nhận tham số key và m.
Sử dụng một phép toán mô đun đơn giản để xác định giá trị băm
Xác định một biến m được khởi tạo bằng giá trị 7. Đây là kích thước của bảng băm của chúng tôi
Tính toán và in giá trị băm của 3
Tính toán và in giá trị băm của 2
Tính toán và in giá trị băm của 9
Tính toán và in giá trị băm của 11
Tính toán và in giá trị băm của 7

Thực thi đoạn mã trên sẽ tạo ra kết quả sau.

The hash value for 3 is 3
The hash value for 2 is 2
The hash value for 9 is 2
The hash value for 11 is 4
The hash value for 7 is 0

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

Python đi kèm với một kiểu dữ liệu tích hợp có tên là Từ điển. Từ điển là một ví dụ về bảng băm. Nó lưu trữ các giá trị bằng cách sử dụng một cặp khóa và giá trị. Các giá trị băm được tạo tự động cho chúng tôi và mọi xung đột đều được giải quyết cho chúng tôi ở chế độ nền.

Ví dụ sau đây cho thấy cách bạn có thể sử dụng kiểu dữ liệu từ điển trong trăn 3

employee = {
    'name': 'John Doe',
    'age': 36,
    'position': 'Business Manager.'
}

print (f"The name of the employee is {employee['name']}")
employee['position'] = 'Software Engineer'
print (f"The position of {employee['name']} is {employee['position']}")
employee.clear()

print (employee)

ĐÂY,

Định nghĩa một biến từ điển nhân viên. Tên khóa được sử dụng để lưu trữ giá trị John Doe, tuổi lưu trữ 36 và vị trí lưu trữ giá trị Trình quản lý doanh nghiệp.
Lấy giá trị của tên khóa và in nó trong terminal
Cập nhật giá trị của vị trí then chốt thành giá trị Kỹ sư phần mềm
In các giá trị của tên và vị trí khóa
Xóa tất cả các giá trị được lưu trữ trong biến từ điển của chúng tôi
In giá trị của nhân viên

Chạy đoạn mã trên sẽ cho kết quả sau.

The name of the employee is John Doe.
The position of John Doe is a Software Engineer.
{}

Phân tích độ phức tạp

Bảng băm có độ phức tạp thời gian trung bình là O (1) trong trường hợp tốt nhất. Độ phức tạp thời gian trong trường hợp xấu nhất là O(n). Trường hợp xấu nhất xảy ra khi nhiều giá trị tạo ra cùng một khóa băm và chúng ta phải giải quyết va chạm bằng cách thăm dò.

Ứng dụng trong thế giới thực

Trong thế giới thực, bảng băm được sử dụng để lưu trữ dữ liệu cho

Cơ sở dữ liệu
Mảng kết hợp
bộ
Bộ nhớ cache

Ưu điểm của bảng băm

Dưới đây là những ưu/lợi ích của việc sử dụng bảng băm:

Bảng băm có hiệu suất cao khi tra cứu dữ liệu, chèn và xóa các giá trị hiện có.
Độ phức tạp về thời gian của bảng băm là không đổi bất kể số lượng mục trong bảng.
Chúng hoạt động rất tốt ngay cả khi làm việc với các tập dữ liệu lớn.

Nhược điểm của bảng băm

Dưới đây là nhược điểm của việc sử dụng bảng băm:

Bạn không thể sử dụng giá trị null làm khóa.
Không thể tránh được va chạm khi tạo khóa bằng cách sử dụng. các hàm băm. Xung đột xảy ra khi một khóa đã được sử dụng được tạo ra.
Nếu hàm băm có nhiều xung đột, điều này có thể dẫn đến giảm hiệu suất.

Tổng kết

Bảng băm được sử dụng để lưu trữ dữ liệu bằng cách sử dụng một cặp khóa và giá trị.
Hàm băm sử dụng thuật toán toán học để tính giá trị băm.
Xung đột xảy ra khi cùng một giá trị băm được tạo ra cho nhiều giá trị.
Chuỗi giải quyết xung đột bằng cách tạo danh sách liên kết.
Thăm dò giải quyết xung đột bằng cách tìm các ô trống trong bảng băm.
Thăm dò tuyến tính tìm kiếm vị trí trống tiếp theo để lưu trữ giá trị bắt đầu từ vị trí xảy ra xung đột.
Thăm dò bậc hai sử dụng các biểu thức đa thức để tìm khe trống tiếp theo khi xảy ra xung đột.
Double băm sử dụng thuật toán hàm băm thứ cấp để tìm vị trí trống tiếp theo khi xảy ra xung đột.
Bảng băm có hiệu suất tốt hơn khi so sánh với các cấu trúc dữ liệu khác.
Độ phức tạp thời gian trung bình của các bảng băm là O (1)
Kiểu dữ liệu từ điển trong python là một ví dụ về bảng băm.
Bảng băm hỗ trợ các thao tác chèn, tìm kiếm và xóa.
Giá trị null không thể được sử dụng làm giá trị chỉ mục.
Không thể tránh được va chạm trong hàm băm. Hàm băm tốt sẽ giảm thiểu số lượng xung đột xảy ra để cải thiện hiệu suất.

Bạn có thể thích:

Băm là gì?

Bảng băm là gì?

Hàm băm

Ví dụ

NHỮNG BÀI VIẾT LIÊN QUAN

Phẩm chất của một hàm băm tốt

Va chạm

Xâu chuỗi

Thăm dò

Hoạt động bảng băm

Thao tác chèn dữ liệu

Tìm kiếm hoạt động dữ liệu

Thao tác xóa dữ liệu

Triển khai bảng băm với Python Ví dụ

Giải thích mã bảng băm

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

Phân tích độ phức tạp

Ứng dụng trong thế giới thực

Ưu điểm của bảng băm

Nhược điểm của bảng băm

Tổng kết