CSD201 - Phần 7: Băm và bảng băm

Ứng với CLO7, buổi 49-52. Tương ứng Chương 10 của Goodrich ấn bản 6. Phần khái niệm giải thích ý tưởng băm là biến khoá thành chỉ số để truy cập trực tiếp, nhờ đó tìm kiếm đạt thời gian hằng số trung bình thay vì tuyến tính hay lôgarit, cùng định nghĩa hàm băm, bảng băm và các ứng dụng. Phần hàm băm trình bày các cách xây dựng thông dụng gồm phương pháp chia lấy dư và phương pháp gấp, cùng tiêu chí của một hàm băm tốt là phân bố đều và tính nhanh. Phần va chạm là trọng tâm: giải thích vì sao va chạm là không thể tránh và hai họ giải pháp. Địa chỉ mở gồm dò tuyến tính với hiện tượng gom cụm và dò bậc hai. Nối chuỗi gồm nối chuỗi riêng bằng danh sách liên kết tại mỗi ô và nối chuỗi hợp nhất. Khép lại bằng hệ số tải, tái băm khi bảng quá đầy, hàm băm hoàn hảo, băm mở rộng và cách Java hiện thực bảng băm.