Bài giảng Cấu trúc dữ liệu và giải thuật: Bảng băm

Tài liệu này giới thiệu về phép băm (hashing), một quá trình ánh xạ một giá trị khóa vào một vị trí cụ thể trong bảng. Nó định nghĩa hàm băm (ký hiệu h) là công cụ thực hiện ánh xạ này, và bảng băm (ký hiệu HT) là một mảng dùng để lưu trữ các bản ghi. Bảng băm HT có M vị trí được đánh chỉ mục từ 0 đến M-1, với M là kích thước của bảng băm.

Tài liệu này hướng đến sinh viên, giảng viên, và các nhà nghiên cứu trong lĩnh vực khoa học máy tính và công nghệ thông tin, đặc biệt là những người đang học tập hoặc làm việc với cấu trúc dữ liệu và giải thuật, muốn tìm hiểu sâu về bảng băm và các hàm băm.

Tài liệu này cung cấp một cái nhìn tổng quan chi tiết về khái niệm bảng băm và các hàm băm trong lĩnh vực cấu trúc dữ liệu và giải thuật. Bắt đầu với định nghĩa cơ bản về phép băm là quá trình ánh xạ một giá trị khóa vào một vị trí cụ thể trong bảng, tài liệu sau đó giải thích hàm băm (h) là công cụ thực hiện ánh xạ này và bảng băm (HT) là mảng lưu trữ các bản ghi với M vị trí được đánh chỉ mục từ 0 đến M-1. Một phần quan trọng được đề cập là hiện tượng đụng độ (collision), xảy ra khi hai khóa khác nhau được ánh xạ tới cùng một địa chỉ trong bảng băm. Tài liệu nhấn mạnh các yêu cầu đối với một hàm băm hiệu quả, bao gồm việc giảm thiểu đụng độ, tốc độ tính toán nhanh, và khả năng phân bố đều các khóa trên bảng băm. Hai phương pháp chính để xây dựng hàm băm được trình bày là phương pháp chia (sử dụng phép toán modulo) và phương pháp nhân (sử dụng công thức h(k) = M * (k*A % 1) với A là số thực trong khoảng (0, 1)). Cuối cùng, tài liệu giới thiệu các phương pháp giải quyết đụng độ, tập trung vào phương pháp nối kết (separate chaining), trong đó các phần tử bị đụng độ tại cùng một địa chỉ được tổ chức thành một danh sách liên kết. Các ví dụ minh họa và đoạn mã giả (hoặc mã C) được cung cấp để làm rõ cách triển khai các phép toán cơ bản trên bảng băm như khởi tạo, kiểm tra rỗng và thêm phần tử vào bảng băm sử dụng phương pháp nối kết.