Mục đích của thông tin băm là gì?

Question

Sau khi được dạy cách tạo bảng băm trong lớp, tôi không hiểu khi nào dữ liệu băm sẽ hữu ích. Dường như với tôi rằng tất cả băm đều lưu trữ thông tin ở các vị trí bán ngẫu nhiên trong một mảng. Tôi muốn biết làm thế nào bất kỳ dữ liệu có thể được thực hiện hữu ích sau khi nó được lưu trữ.

Câu hỏi của tôi là: một số ví dụ về thông tin băm có lợi là gì? Dữ liệu được truy xuất theo cách có tổ chức như thế nào? Nó dường như được đặt ở vị trí tùy ý, nơi nó sẽ rất khó để lấy lại.

Answer 1

băm có thể được sử dụng cho nhiều mục đích:

1. Nó có thể được sử dụng để so sánh lượng lớn dữ liệu. Bạn tạo băm cho dữ liệu, lưu trữ các băm và sau này nếu bạn muốn so sánh dữ liệu, bạn chỉ cần so sánh các băm.

2. Có thể sử dụng dấu gạch ngang để lập chỉ mục dữ liệu. Chúng có thể được sử dụng trong các bảng băm để trỏ đến hàng chính xác. Nếu bạn muốn nhanh chóng tìm thấy một bản ghi, bạn tính toán giá trị băm của dữ liệu và trực tiếp đi tới bản ghi mà bản ghi băm tương ứng đang trỏ đến. (Điều này giả định rằng bạn có danh sách các băm được sắp xếp trỏ đến các bản ghi thực)

3. Chúng có thể được sử dụng trong các ứng dụng mã hóa như chữ ký số.

4. Việc băm có thể được sử dụng để tạo các chuỗi có vẻ ngẫu nhiên.

Dưới đây là các ứng dụng của hàm băm mà wikipedia liệt kê:

1. Finding duplicate records
2. Finding similar records
3. Finding similar substrings
4. Geometric hashing

Bây giờ, liên quan đến bảng băm, dưới đây là một số điểm cần lưu ý:

Nếu bạn đang sử dụng bảng băm, các bảng băm trong bảng phải được sắp xếp. Nếu không, bạn sẽ phải tạo một chỉ mục trên cột băm. Một số triển khai lưu trữ hàm băm riêng biệt theo cách được sắp xếp và trỏ đến bản ghi gốc.

Nếu ai đó đang lưu trữ băm theo thứ tự bán ngẫu nhiên, thì phải vì lý do trên hoặc vì họ chỉ muốn lưu trữ thông báo thông tin để so sánh, tìm bản sao, v.v ... chứ không phải là chỉ mục cho dữ liệu.

Answer 2

Có một vài lý do điển hình cho dữ liệu băm. Trong ví dụ bạn tham chiếu, bạn sẽ băm dữ liệu và sử dụng nó làm khóa để trích xuất giá trị thực của mục được băm. Dữ liệu được băm thường được gọi là khóa và nó tham chiếu đến một nhóm mà giá trị thực tế, không băm có thể được tìm thấy.

Lý do điển hình khác là tạo chữ ký của giá trị được băm để bạn có thể kiểm tra xem giá trị có bị thay đổi bởi người khác hay không. Vì nó thường hiếm, tùy thuộc vào thuật toán được sử dụng, để có hai mục băm có cùng giá trị, bạn có thể khôi phục một giá trị và so sánh nó với giá trị băm đã lưu để kiểm tra xem mục đó vẫn giữ nguyên.

Answer 3

Một trong những ứng dụng chính của bảng băm mà bạn đã tạo trong lớp học là khi bạn cần nhanh O (1) thời gian tra cứu. Bạn sẽ có hai thành phần, khóa và giá trị.

Hàm băm chuyển khóa thành số băm. Băm đó là một số, và cụ thể, nó là chỉ số của dữ liệu trong mảng.

Vì vậy, khi bạn cần tra cứu danh tiếng của Agscala trong bảng băm và bạn đã sử dụng tên người dùng làm khóa, hầu như không mất thời gian để tìm và tìm giá trị phù hợp. Nó chỉ đơn giản là tái băm tên người dùng và viola của bạn, có chỉ mục của dữ liệu bạn đang tìm kiếm. Bạn không phải lặp qua toàn bộ mảng tìm kiếm giá trị cụ thể đó.

Để tham khảo một số trang Wikipedia trên Hash tables là khá tốt.

Answer 4

Hashing là kỹ thuật hữu ích để tra cứu chính nhanh. Nó cho phép tìm kiếm một giá trị hiệu quả hơn là quét danh sách từ đầu đến cuối.

Answer 5

Bạn đã bao giờ sử dụng từ điển hoặc bộ chưa? Chúng thường được triển khai dưới dạng một hashtable vì giá trị được liên kết với một khóa có thể được tìm thấy nhanh chóng.

{ 
'WA': 'Washington', 
'WV': 'West Virginia', 
'WY': 'Wyoming' 
}