Tôi đang triển khai một lớp Hashtable trong C++. Phương pháp xử lý sự va chạm mà tôi đang sử dụng là dò tìm tuyến tính với thao tác xóa lười. Tôi đã thấy các triển khai này nhưng có một câu hỏi liên quan đến phương pháp chèn. Mỗi ô của hashtable có trạng thái (hoạt động, đã xóa, trống). Đối với một số lý do trong việc thực hiện tôi đã thấy khi chèn một phần tử mới, họ băm khóa và sau đó thăm dò bảng cho đến khi một ô EMPTY được tìm thấy (hoặc cho đến khi một ô đã chứa cùng một khóa được tìm thấy).Thực hiện các hashtables trong C++ (chèn và xóa lười)
Ví dụ Code:
int findPos(const string &key){
int currentPos=hash(key);
while(data[currentPos].state!=EMPTY && data[currentPos].key!=key){
currentPos++;
if (currentPos>=data.size())
currentPos-=data.size()
}
return currentPos;
}
bool insert(const string &key){
int currentPos=findPos(key);
if (isActive(currentPos))
return false; //already exists
data[currentPos]=hashEntry(key,ACTIVE);
if (++currentSize>data.size()/2)
rehash();
return true; //element inserted
}
Câu hỏi của tôi là: Có một lý do không phải dừng lại và chèn vào một tế bào đã được gắn thẻ như đã bị xóa? Nói cách khác, trong phương thức findPos, tại sao không thay đổi câu lệnh while thành while(data[currentPos].state==ACTIVE && data[currentPos].key!=key) để vòng lặp kết thúc khi chúng tôi tìm thấy ô có khóa hoặc ô đã xóa/ô trống đầu tiên. Sau đó, trong chèn, kiểm tra trạng thái của ô. Nếu hoạt động mục nhập đã tồn tại, vì vậy trả về false; khác chèn phần tử.