Buzz
Hàm băm (tiếng Anh: hash function) là thuật toán dùng để tạo ra các giá trị băm cho từng khối dữ liệu (như chuỗi ký tự, đối tượng trong lập trình hướng đối tượng, v.v...). Giá trị băm đóng vai trò như một khóa để phân biệt các khối dữ liệu, nhưng hiện tượng trùng khóa hay đụng độ có thể xảy ra và các nhà phát triển nỗ lực cải thiện thuật toán để giảm thiểu vấn đề này. Hàm băm thường được sử dụng trong bảng băm để giảm chi phí tính toán khi tra cứu một khối dữ liệu
Với sự phổ biến của bảng băm, hiện nay hầu hết các ngôn ngữ lập trình đều tích hợp thư viện hỗ trợ bảng băm, thường được gọi là thư viện collection, bao gồm các cấu trúc như: tập hợp (collection), danh sách (list), bảng (table), ánh xạ (mapping), từ điển (dictionary). Thường thì các lập trình viên chỉ cần xây dựng hàm băm cho các đối tượng để kết hợp với thư viện bảng băm đã có sẵn.
Một hàm băm chất lượng cần đáp ứng các tiêu chí sau:
- Tính toán nhanh chóng.
- Các khóa phân bố đồng đều trong bảng.
- Ít xảy ra hiện tượng đụng độ.
- Đáp ứng được các loại khóa với kiểu dữ liệu khác nhau.
Ứng dụng
Hàm băm được áp dụng trong nhiều lĩnh vực khác nhau và thường được điều chỉnh để phù hợp với từng mục đích sử dụng cụ thể. Ví dụ, các hàm băm trong mật mã học được thiết kế để đối phó với tình huống có đối thủ cố gắng tìm ra dữ liệu đầu vào tương ứng với cùng một giá trị băm. Một hàm băm lý tưởng phải là một phép biến đổi 'một chiều', tức là không thể dễ dàng tính ngược từ giá trị băm để lấy dữ liệu đầu vào, làm cho việc giả mạo trở nên khó khăn. Hàm băm mật mã học điển hình không phải là hàm đơn ánh và tạo ra hàm băm hiệu quả; ngược lại, hàm trapdoor mật mã học là hàm đơn ánh và tạo ra hàm băm ngẫu nhiên hiệu quả.
Bảng băm là một ứng dụng quan trọng của hàm băm, cho phép tra cứu nhanh một bản ghi dữ liệu dựa trên khóa của bản ghi đó (Lưu ý: các khóa này thường không được bảo mật như trong mật mã học, nhưng cả hai đều được sử dụng để 'mở khóa' hoặc truy cập thông tin.) Ví dụ, trong từ điển điện tử Anh-Anh, khóa có thể là các từ tiếng Anh, và bản ghi tương ứ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 chuỗi ký tự thành các chỉ mục trong mảng nội bộ của bảng băm.
Hàm băm dùng để phát hiện và sửa lỗi tập trung vào việc phân biệt các trường hợp dữ liệu bị thay đổi do các quá trình ngẫu nhiên. Khi sử dụng hàm băm cho các giá trị tổng kiểm, giá trị băm nhỏ có thể được dùng để kiểm tra xem một tập tin dữ liệu có bị thay đổi hay không. Hàm băm cũng được sử dụng để phát hiện lỗi truyền dữ liệu. Tại đầu gửi, giá trị băm được tính cho dữ liệu gửi đi và gửi cùng với dữ liệu đó. Tại đầu nhận, hàm băm được tính lại, nếu giá trị băm không trùng khớp thì lỗi đã xảy ra trong quá trình truyền. Điều này được gọi là kiểm tra dư (redundancy check).
Các hàm băm còn được sử dụng trong nhận diện âm thanh, ví dụ như kiểm tra xem một file MP3 có trùng khớp với một file nào đó trong danh sách hay không.
Thuật toán tìm kiếm xâu Rabin-Karp là một phương pháp 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 sử dụng hàm băm để so sánh các xâu ký tự.
Liên kết bên ngoài
- Các hàm băm cho mục đích tổng quát (C/C++/Pascal/Java/Python/Ruby)
- Hàm băm dùng cho tra cứu bảng băm của Bob Jenkins
- Mã nguồn hàm LOOKUP3 của Bob Jenkins
- Hàm băm Goulburn của Mayur Patel
- Các hàm băm do Paul Hsieh phát triển
- HSH 11/13 của Herbert Glarner
- Công cụ trực tuyến mã hóa/giải mã dữ liệu dạng Char (ASCII), HEX, Binary, Base64, v.v... bằng các thuật toán băm MD2, MD4, MD5, SHA1+2 v.v.. Lưu trữ 2010-05-30 tại Portuguese Web Archive
