Given the division hash function h(x) = x%M, where M = 10 and Collision Resolution is linear probing. How the hash table looks like after inserting the following keys sequentially? 95,64,21, 203, 44, 144

Đáp án đúng: "(1)", tức bảng có 21 ở ô 1, 203 ở ô 3, 64 ở ô 4, 95 ở ô 5, 44 ở ô 6 và 144 ở ô 7. Hàm băm lấy số dư cho 10 nên 95 vào ô 5, 64 vào ô 4, 21 vào ô 1, 203 vào ô 3, các ô này đều trống nên nhận ngay. Khoá 44 băm về ô 4 đã có 64, dò tuyến tính sang ô 5 cũng đầy vì có 95, sang ô 6 trống nên dừng ở đó. Khoá 144 cũng băm về ô 4, dò qua ô 5, ô 6 rồi đậu ở ô 7. Bảng "(2)" đổi chỗ 44 với 144, nhưng 44 được chèn trước nên chính nó mới chiếm ô trống gần nhất là ô 6. Bảng "(3)" để trống ô 6 và ô 7 rồi đặt 44 ở ô 8, trái với dò tuyến tính vì phép dò này luôn nhận ô trống đầu tiên về phía sau. Bảng "(4)" vừa bỏ qua hai ô trống đó vừa đảo thứ tự hai khoá, sai cả bước dò lẫn trình tự chèn.