Hàm băm

Bách khoa toàn thư mở Wikipedia

Một hàm băm tiêu biểu đang hoạt động
Một hàm băm tiêu biểu đang hoạt động

Một hàm băm (tiếng Anh: hash function) hay một giải thuật băm là một phương pháp sinh một địa chỉ trong phần bộ nhớ dành cho các khóa được sắp thứ tự. Các hàm này cung cấp một cách tạo một "vân tay" số nhỏ từ bất kỳ loại dữ liệu nào. Hàm này cắt và trộn (thay thế và chuyển vị) dữ liệu để tạo một giá trị thường được gọi là giá trị băm. Giá trị băm thường được biểu diễn trong hệ cơ số 16. Hàm băm tốt là hàm cho ra ít đụng độ băm (hash collision) trong các miền dữ liệu trông đợi. Trong các bảng băm và việc xử lý dữ liệu, các đụng độ này dẫn đến chi phí cao hơn cho việc tìm kiếm các bản ghi trong cơ sở dữ liệu.

Các phép toán trên các cấu trúc dữ liệu như danh sách, cây nhị phân... phần lớn được thực hiện bằng cách so sánh các phần tử của cấu trúc, do vậy thời gian truy xuất không nhanh và phụ thuộc vào kích thước của cấu trúc. Một hàm băm tốt phải thỏa mãn các điều kiện sau:

  • Tính toán nhanh.
  • Các khoá được phân bố đều trong bảng.
  • Ít xảy ra đụng độ.
  • Xử lý được các loại khóa có kiểu dữ liệu khác nhau.

[sửa] Ứng dụng

Các hàm băm được ứng dụng trong nhiều lĩnh vực, chúng thường được thiết kế phù hợp với từng ứng dụng. Ví dụ, các hàm băm mật mã học giả thiết sự tồn tại của một đối phương - người có thể cố tình tìm các dữ liệu vào với cùng một giá trị băm. Một hàm băm tốt là một phép biến đổi "một chiều", nghĩa là không có một phương pháp thực tiễn để tính toán được dữ liệu vào nào đó tương ứng với giá trị băm mong muốn, khi đó việc giả mạo sẽ rất khó khăn. Một hàm một chiều mật mã học điển hình không có tính chất hàm đơn ánh và tạo nên một hàm băm hiệu quả; một hàm trapdoor mật mã học điển hình hàm đơn ánh và tạo nên một hàm ngẫu nhiên hiệu quả.

Bảng băm, một ứng dụng quan trọng của các hàm băm, cho phép tra cứu nhanh một bản ghi dữ liệu nếu cho trước khóa của bản ghi đó (Lưu ý: các khóa này thường không bí mật như trong mật mã học, nhưng cả hai đều được dùng để "mở khóa" hoặc để truy nhập thông tin.) Ví dụ, các khóa trong một từ điển điện tử Anh-Anh có thể là các từ tiếng Anh, các bản ghi tương ứng với chúng chứa các định nghĩa. Trong trường hợp này, hàm băm phải ánh xạ các xâu chữ cái tới các chỉ mục của mảng nội bộ của bảng băm.

Các hàm băm dành cho việc phát hiện và sửa lỗi tập trung phân biệt các trường hợp mà dữ liệu đã bị làm nhiễu bởi các quá trình ngẫu nhiên. Khi các hàm băm được dùng cho các giá trị tổng kiểm, giá trị băm tương đối nhỏ có thể được dùng để kiểm chứng rằng một file dữ liệu có kích thước tùy ý chưa bị sửa đổi. Hàm băm được dùng để phát hiện lỗi truyền dữ liệu. Tại nơi gửi, hàm băm được tính cho dữ liệu được gửi, giá trị băm này được gửi cùng dữ liệu. Tại đầu nhận, hàm băm lại được tính lần nữa, nếu các giá trị băm không trùng nhau thì lỗi đã xảy ra ở đâu đó trong quá trình truyền. Việc này được gọi là kiểm tra dư (redundancy check).

Các hàm băm còn được ứng dụng trong việc nhận dạng âm thanh, chẳng hạn như xác định xem một file MP3 có khớp với một file trong danh sách một loại các file khác hay không.

Thuật toán tìm kiếm xâu Rabin-Karp là một thuật toán tìm kiếm xâu kí tự tương đối nhanh, với thời gian chạy trung bình O(n). Thuật toán này dựa trên việc sử dụng băm để so sánh xâu.

[sửa] Liên kết ngoài