Hashing là gì?
Hàm băm là một giá trị có độ dài cố định và nó đượ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.
Một hàm băm sử dụng một thuật toán toán học để chuyển đổi khóa thành một hàm băm. Xung đột xảy ra khi một hàm băm tạo ra cùng một giá trị băm cho nhiều hơn một khóa.
Trong hướng dẫn về Thuật toán này, bạn sẽ học:
- Hashing là gì?
- Bảng băm là gì?
- Hàm băm
- Các phẩm chất của một hàm băm tốt
- Va chạm
- Hoạt động bảng băm
- Ví dụ về bảng băm trong Python
- Giải thích mã bảng băm
- Ví dụ từ điển Python
- 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
Bảng băm là gì?
Một bảng băm là một cấu trúc dữ liệu mà các cửa hàng giá trị 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 làm cho việc tìm kiếm các giá trị trong bảng băm rất nhanh, bất kể số lượng mục trong bảng băm là bao nhiêu.
Hàm băm
Ví dụ: nếu chúng ta 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 cách sử dụng một số nhân viên.
Chúng ta có thể sử dụng 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 có bậc là (m * n 2 ) trong đó biến m là kích thước của mảng và biến n là số chữ số của số nhân viên. Cách tiếp cận này đưa ra một 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ố nhân viên và sử dụng nó để tạo 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 một 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 một 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) = 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 1 % m là thuật toán cho hàm băm của chúng ta trong đó k1 là giá trị chúng ta 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 khóa.
Thí dụ
Giả sử rằng chúng ta có một danh sách với 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 các vị trí mà mỗi giá trị sẽ chiếm.
Hình ảnh sau đây cho thấy 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ẽ được 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ỉ mục 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ỉ mục 2
Bước 3)
Tính vị trí sẽ được 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ỉ mục 0
Kết quả cuối cùng
Bảng băm đã điền của chúng ta bây giờ sẽ như sau.
Các phẩm chất của một hàm băm tốt
Một hàm băm tốt cần có những phẩm chất 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 phải 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 sẽ giảm thiểu số lần 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 hàm 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 hàm băm cho nhiều hơn một giá trị.
Hãy xem một ví dụ.
Giả sử chúng ta có danh sách các giá trị sau
[3,2,9,11,7]
Giả sử rằng 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 1 % m) trong đó m là kích thước của bảng băm.
Bảng sau đây cho thấy các giá trị băm sẽ được tạo.
| Chìa khóa | Thuật toán băm (k 1 % 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ừ 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ị tại mỗi vị trí.
Vấ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ò.
Chuỗi
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 các danh sách được liên kết mà mỗi danh sách có các chỉ mục duy nhất.
Hình ảnh sau đây hình dung một danh sách được xâu chuỗi trông như thế nào
Cả 2 và 9 đều chiếm cùng một 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 chuỗi:
- 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ó dung lượng trống.
Thăm dò
Kỹ thuật khác được sử dụng để giải quyết va chạm là thăm dò. Khi sử dụng phương pháp thăm dò, nếu xảy ra va chạm, chúng ta chỉ cần tiếp tục và tìm một vùng 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 | Sự miêu 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 một cách tuyến tính bắt đầu 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 vị trí trống. 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ùng trống tiếp theo có sẵn. |
| Băm đôi | 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 có sẵn 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
Dưới đây là các Hoạt động được hỗ trợ bởi bảng Hash:
- Chèn - Thao tác này được sử dụng để thêm một phần tử vào bảng băm
- Tìm kiếm - Thao tác này được sử dụng để tìm kiếm các phần tử trong bảng băm bằng cách sử dụng phím
- Xóa - Thao tác này đượ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 cách sử dụng hàm băm. Hàm băm giải quyết mọi xung đột xảy ra khi tính toán số chỉ mục.
Tìm kiếm hoạt động dữ liệu
Thao tác tìm kiếm được sử dụng để tra cứu các giá trị trong bảng băm bằng cách sử dụ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 ở chỉ mục 2, thì thao tác tìm kiếm với chỉ số 2 sẽ trả về giá trị 6.
Xóa dữ liệu hoạt động
Thao tác xóa được sử dụng để xóa một giá trị khỏi bảng băm. Để xóa Thao tác được thực hiện bằng cách sử dụng số chỉ mục. Khi một giá trị đã bị xóa, số chỉ mục sẽ được miễn phí. Nó có thể được sử dụng để lưu trữ các giá trị khác bằng thao tác chèn.
Triển khai bảng băm với ví dụ Python
Hãy xem một ví dụ đơn giản để tính toán giá trị băm của một khóa
def hash_key( key, m):return key % mm = 7print(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,
- Định nghĩa một hàm hash_key chấp nhận khóa tham số và m.
- Sử dụng một hoạt động mô-đun đơn giản để xác định giá trị băm
- Định nghĩa một biến m được khởi tạo giá trị 7. Đây là kích thước của bảng băm của chúng ta
- 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
Việc thực thi đoạn mã trên sẽ cho kết quả như sau.
The hash value for 3 is 3The hash value for 2 is 2The hash value for 9 is 2The hash value for 11 is 4The hash value for 7 is 0
Ví dụ từ điển Python
Python đi kèm với một kiểu dữ liệu tích hợp được gọi 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 va chạm đều được giải quyết cho chúng tôi trong nền.
Ví dụ sau cho thấy cách bạn có thể sử dụng kiểu dữ liệu từ điển trong python 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,
- Xác định một nhân viên biến từ điển. Tên khóa được sử dụng để lưu trữ giá trị John Doe, lưu trữ tuổi 36 và vị trí lưu trữ giá trị Giám đốc kinh doanh.
- Lấy giá trị của tên khóa và in nó trong thiết bị đầu cuối
- Cập nhật giá trị của vị trí quan trọng 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 nhân viên 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ẽ tạo ra 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 xung đột 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
- Cơ sở dữ liệu
- Mảng liên kết
- Bộ
- Bộ nhớ đệm
Ưu điểm của bảng băm
Dưới đây là ư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 đối với 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 bộ dữ liệu lớn.
Nhược điểm của bảng băm
Đâ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 chìa khóa bằng cách sử dụng. 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óm lược:
- 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 một thuật toán toán học để tính toán giá trị băm.
- Xung đột xảy ra khi cùng một giá trị băm được tạo cho nhiều hơn một giá trị.
- Chuỗi giải quyết xung đột bằng cách tạo danh sách liên kết.
- Probing giải quyết xung đột bằng cách tìm các khe 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 va chạm.
- Thăm dò bậc hai sử dụng biểu thức đa thức để tìm rãnh trống tiếp theo khi xảy ra va chạm.
- Băm kép sử dụng thuật toán hàm băm thứ cấp để tìm khe trống tiếp theo khi xảy ra va chạm.
- 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 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 các hàm băm. Một hàm băm tốt sẽ giảm thiểu số lần va chạm xảy ra để cải thiện hiệu suất.