Hàm băm

Hàm băm chuyển dữ liệu thành một giá trị trong miền đích hữu hạn. Đầu vào khác nhau có thể trùng giá trị băm: Đó là va chạm. Hàm băm cần phù hợp với mục tiêu: Tra cứu, chia phân vùng hay bảo mật có các yêu cầu khác nhau.

Lĩnh vực: Giải thuật & cấu trúc dữ liệu

Định nghĩa trên trang này được dùng trong lĩnh vực vừa nêu. Một từ giống nhau ở môn khác có thể mang nghĩa khác.

Bài giảng dùng khái niệm này

• Dữ liệu lớn & mô hình thuật toánGiải thuật dữ liệu

Giải thích kỹ thuật

Va chạm cần xử lý. Bảng băm phải có cách phân biệt các khóa rơi vào cùng vùng, chẳng hạn liên kết danh sách hoặc tìm vị trí khác. Một hash hữu hạn không thể đảm bảo không va chạm cho miền đầu vào vô hạn.

Hàm băm dùng để chia phân vùng không tự đáp ứng yêu cầu bảo mật. Kiểm tra mục đích, phân bố dữ liệu và chi phí tính trước khi lựa chọn.

Ví dụ

$h(x)=x$ mod 4: 2 và 6 đều băm thành 2. Không thể suy ra hai đầu vào bằng nhau chỉ vì hash bằng nhau.

Khi nào cần dùng?

Hiểu bảng băm, phân vùng dữ liệu và Shuffle.

Câu hỏi ôn lại

Hash giống nhau có chứng minh dữ liệu giống nhau không?

Xem đáp án

Không, vì có thể có va chạm.

Thuật ngữ liên quan

• Đồ thị
• Đệ quy