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? 26, 97, 36, 106

Đáp án đúng: "(4)", tức bảng có 36 ở ô 0, 106 ở ô 5, 26 ở ô 6 và 97 ở ô 7, các ô còn lại rỗng. Với h(x) = x%10 và dò bậc hai (h(x) + i^2)%10: 26 băm về ô 6 đang trống nên vào ô 6; 97 băm về ô 7 và vào ô 7; 36 cũng băm về 6 nhưng ô 6 đã có 26, thử i = 1 được ô 7 đang có 97, thử i = 2 được (6 + 4)%10 = 0 nên 36 vào ô 0; 106 lại băm về 6, i = 1 cho ô 7 và i = 2 cho ô 0 đều kẹt, i = 3 cho (6 + 9)%10 = 5 nên 106 vào ô 5. Phương án "(1)" ghi 26 ở cả ô 6 và ô 8 rồi đặt 106 ở ô 9, tức đã đọc 36 thành 26 và dò tuyến tính thay vì bậc hai. Phương án "(2)" đặt 106 ở ô 4, chỉ đúng nếu bước i = 3 cộng 8 thay vì cộng 9. Phương án "(3)" đặt 36 ở ô 1, chỉ đúng nếu bước i = 2 cộng 5 thay vì cộng 4.