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? 25, 21, 14, 32, 41, 191

Đáp án đúng: "(2)". Đó là bảng có 21 ở ô 1, 32 ở ô 2, 41 ở ô 3, 14 ở ô 4, 25 ở ô 5, 191 ở ô 6 và các ô 0, 7, 8, 9 trống. Với h(x) bằng x chia 10 lấy dư và dò tuyến tính bước 1, theo đúng thứ tự chèn: 25 vào ô 5, 21 vào ô 1, 14 vào ô 4, 32 vào ô 2; 41 băm về ô 1 đang có 21 nên dò ô 2 có 32 rồi dừng ở ô 3 đang trống; 191 cũng băm về ô 1 nên dò 2, 3, 4, 5 đều đầy và dừng ở ô 6. Vì vậy "(1)" sai vì nó đặt 191 vào ô 3 và 41 vào ô 6, chỉ xảy ra nếu 191 được chèn trước 41, trái thứ tự đề cho; "(3)" sai vì nó chỉ giữ 21, 32, 14, 25 và làm mất hai khoá va chạm, trong khi dò tuyến tính luôn tìm được ô trống khi bảng chưa đầy; "(4)" sai vì nó đặt 41 ở ô 9 và 191 ở ô 8, bỏ qua các ô trống 3 và 6 nằm ngay trên đường dò bước 1.