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? 74,111,110,32,101,131

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