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? 75,12,110, 103, 32, 132

Đáp án đúng: "(3)". Đó là bảng có 110 ở ô 0, 12 ở ô 2, 103 ở ô 3, 32 ở ô 4, 75 ở ô 5, 132 ở ô 6 và các ô 1, 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: 75 vào ô 5, 12 vào ô 2, 110 vào ô 0, 103 vào ô 3; 32 băm về ô 2 đã có 12 nên dò ô 3 có 103 rồi dừng ở ô 4; 132 cũng băm về ô 2 nên dò 3, 4, 5 đều đầy và dừng ở ô 6. Vì vậy "(1)" sai vì nó đặt 132 ở ô 4 và 32 ở ô 6, chỉ xảy ra nếu 132 được chèn trước 32, trái thứ tự đề cho; "(2)" sai vì nó để trống ô 4 rồi nhét 132 vào ô 6 và 32 vào ô 7, trong khi dò tuyến tính phải nhận ô trống đầu tiên gặp được; "(4)" sai vì nó đặt 132 ở ô 8 và 32 ở ô 9, tức bước dò không phải 1 và lại bỏ qua các ô trống 4, 6 nằm ngay trên đường dò.