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? 34, 65, 94, 204

Đáp án đúng: "(3)", tức bảng có 204 ở ô 3, 34 ở ô 4, 65 ở ô 5 và 94 ở ô 8, các ô còn lại rỗng. Với h(x) = x%10 và dò bậc hai (h(x) + i^2)%10: 34 băm về ô 4 đang trống nên vào ô 4; 65 băm về ô 5 và vào ô 5; 94 cũng băm về 4 nhưng ô 4 đã có 34, thử i = 1 được ô 5 đang có 65, thử i = 2 được (4 + 4)%10 = 8 nên 94 nằm ở ô 8; 204 lại băm về 4, i = 1 cho ô 5 và i = 2 cho ô 8 đều kẹt, i = 3 cho (4 + 9)%10 = 3 nên 204 vào ô 3. Phương án "(1)" đặt 94 ở ô 9 thay vì ô 8, chỉ đúng nếu bước i = 2 cộng 5 thay vì cộng 4. Phương án "(2)" đặt 204 ở ô 2, chỉ đúng nếu bước i = 3 cộng 8 thay vì cộng 9. Phương án "(4)" bỏ trống ô 3 và đẩy 204 xuống ô 9, hợp với dò tuyến tính đi liên tiếp 4, 5, 6, 7, 8, 9 chứ không hợp với các bước nhảy 1, 4, 9 của dò bậc hai.