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? 63, 74, 94, 203

Đáp án đúng: "(1)". Đó là bảng có 63 ở ô 3, 74 ở ô 4, 94 ở ô 5 và 203 ở ô 7. Hàm băm lấy số dư cho 10 nên 63 vào ô 3, 74 vào ô 4; 94 cũng cho dư 4 nên va chạm, bước dò bậc hai thử ô 4 cộng 1 bằng ô 5 và ô ấy còn trống nên 94 nằm ở đó; 203 cho dư 3, ô 3 đã có 63, bước dò thứ nhất tới ô 4 cũng đã có 74, bước thứ hai cộng 4 tới ô 7 và ô này trống nên 203 nằm ở ô 7. Bảng "(2)" đặt 94 vào ô 6, muốn vậy phải cộng 2 vào ô gốc 4, mà dãy dò bậc hai từ ô 4 chỉ đi qua ô 5 rồi ô 8. Bảng "(3)" đặt 94 đúng ở ô 5 nhưng đẩy 203 vào ô 6, tức cộng 3 vào ô gốc 3, trong khi các bước dò chỉ cộng 1 rồi cộng 4. Bảng "(4)" đặt 94 ở ô 7 và 203 ở ô 0, cả hai ô đều không nằm trên dãy dò bậc hai xuất phát từ ô gốc 4 và ô gốc 3.