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? 65, 76, 96, 205

Đáp án đúng: "(4)", tức bảng có 65 ở ô 5, 76 ở ô 6, 96 ở ô 7 và 205 ở ô 9, các ô khác rỗng. Dò bậc hai thử lần lượt các vị trí (h(x) + i^2)%10 với i = 1, 2, 3: 65 vào ô 5, 76 vào ô 6; 96 băm về ô 6 đã kín nên i = 1 cho (6+1)%10 = 7 và nằm ở ô 7; 205 băm về ô 5 kín, i = 1 cho ô 6 cũng kín, i = 2 cho (5+4)%10 = 9 còn rỗng. "(1)" sai vì nó đặt 96 ở ô 8, tức cộng thêm 2 vốn không phải số chính phương, và đưa 205 về ô 1 ứng với i = 4 dù ô 9 ở bước i = 2 đã rỗng. "(2)" sai vì cho 205 xuống ô 0, ứng với i = 5, cũng bỏ qua ô rỗng tìm được sớm hơn. "(3)" sai vì xếp 205 vào ô 8: đó là kết quả của dò tuyến tính, khi các ô 5, 6, 7 kín thì lấy ngay ô 8, chứ bước nhảy bậc hai không bao giờ cho khoảng cách 3.