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 số hiệu nhân viên và sử dụng nó để tạo ra một giá trị số nguyên băm, có số 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 ra một khóa được sử dụng để tham chiếu đến giá trị mà chúng ta muốn lưu trữ. Hàm này chấp nhận giá trị cần lưu rồi sử dụng thuật toán để tính toán 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) = k1 % 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.

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ò:

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)}')

Bảng băm Code Giải thích

ĐÂY,

1. Xác định hàm hash_key chấp nhận tham số key và m.
2. Sử dụng một phép toán mô đun đơn giản để xác định giá trị băm
3. 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
4. Tính toán và in giá trị băm của 3
5. Tính toán và in giá trị băm của 2
6. Tính toán và in giá trị băm của 9
7. Tính toán và in giá trị băm của 11
8. 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,

1. Đị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.
2. Lấy giá trị của tên khóa và in nó trong terminal
3. Cập nhật giá trị của vị trí then chốt thành giá trị Kỹ sư phần mềm
4. In các giá trị của tên và vị trí khóa
5. 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
6. 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.

Câu Hỏi Thường Gặp