Given the division hash function h(x) = x%M, where M = 10 and Collision Resolution is quadratic probing, i.e. when inserting a key x, the collision is resolved by finding an available position at (h(x) + i^2)%M), i=1, 2, ... How the hash table looks like after inserting the following keys sequentially? 64, 75, 95, 204

Đáp án đúng: "(2)", tức bảng có 64 ở ô 4, 75 ở ô 5, 95 ở ô 6 và 204 ở ô 8, các ô khác trống. Hàm băm lấy số dư cho 10: khoá 64 về ô 4 đang trống nên nhận ngay; khoá 75 về ô 5 cũng trống nên nhận ngay; khoá 95 cũng băm về ô 5 nhưng ô đã đầy, bước dò bậc hai thứ nhất cộng 1 cho ô 6 và ô này trống nên 95 đậu ở ô 6; khoá 204 băm về ô 4 đã đầy, bước dò thứ nhất cộng 1 cho ô 5 cũng đầy, bước dò thứ hai cộng 4 cho ô 8 và ô này trống nên 204 đậu ở ô 8. Bảng "(1)" đặt 204 ở ô 7, chỉ đúng nếu dò từng ô một như dò tuyến tính thay vì cộng bình phương của số bước. Bảng "(3)" đặt 95 ở ô 7, nhưng bước dò đầu tiên của 95 chỉ cộng 1 vào ô 5 nên đích phải là ô 6 đang trống. Bảng "(4)" vừa đẩy 95 tới ô 7 vừa đặt 204 ở ô 9, mà ô 9 lệch 5 so với ô 4 và 5 không phải bình phương của bước dò nào.