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? 25, 96, 35, 105

Đáp án đúng: "(2)", tức bảng có 105 ở ô 4, 25 ở ô 5, 96 ở ô 6 và 35 ở ô 9. Hàm băm chia lấy dư cho 10 nên 25 vào ô 5 và 96 vào ô 6, hai ô này còn trống. Khoá 35 cũng băm về ô 5 đã có 25 nên phải dò bậc hai: i = 1 cho (5+1)%10 = 6 vẫn bị 96 chiếm, i = 2 cho (5+4)%10 = 9 còn trống nên 35 nằm ở ô 9. Khoá 105 lại băm về ô 5: i = 1 ra ô 6 đã đầy, i = 2 ra ô 9 nay đã có 35, i = 3 cho (5+9)%10 = 4 còn trống nên 105 nằm ở ô 4. "(3)" đặt 35 ở ô 7 và 105 ở ô 8, đó là kết quả của dò tuyến tính cộng thêm 1 mỗi bước. "(4)" đặt 35 ở ô 7, chỉ đúng nếu bước dò thứ hai cộng 2 thay vì cộng bình phương của 2. "(1)" đặt 35 ở ô 0, tức (5+25)%10 với i = 5, nghĩa là đã bỏ qua ô 9 vốn còn trống ngay ở bước i = 2.