Lazy Deletion in Linear Probing Hashtable

之前一段时间在准备上海交通大学软件学院的上机考试。2019年的题目是实现Linear Probing Hashtable和Cuckoo Hashtable。在实现Linear Probing Hashtable的删除操作时，遇到了一个非常棘手的问题。

假如我们现在哈希表存储的是键值对，且其长度为8. Hash函数为 key % 8。首先插入键值对{key: 2, val: 5}，哈希表的状态如下所示(此处只显示key值)：

现在再其中插入键值对{key: 10, val: 7}。由于hashFunc(10)和hashFunc(2)的值相同，都为2，所以键值对{key: 10, val: 7}不能插入到index为2处，根据Linear Probing Hashtable的探测算法，需要将这个键值对插入到2后面的3处，现在哈希表的状态如下图所示：

此后我们从哈希表中删除key值为2的键值对，hashFunc(2)的值为2，而且数组index为2处的键值对，key值的确为2，只需要将此处清空即可，现在哈希表的状态如下图所示：

但是如果我们尝试删除key值为10的键值对时，会发现一个问题。hashFunc(10)的值为2，但是在index为2处没有找到键值对，为空，直接返回，但是key值为10的键值对在index为3处，删除操作失败。

所以如何解决这个问题？如果说每次进行删除的时候，都要从开始的位置不断向后遍历哈希表，直到找到有对应的键值对？但是如果说要删除的键值对本来就不在哈希表里面，那么删除操作需要将整个哈希表遍历一遍，时间复杂度为\(O(n)\)，这显然是不能接受的。

重新翻阅Data Structures and Algorithm Analysis in C++的Hashtable部分后，才了解到，删除线性哈希表中的元素直接删除，而是应该懒惰删除(Lazy deletion)，来防止出现上面的情况。懒惰删除的实现也比较简单，只需要为我们的Hashtable Entry新添加一个bool字段，表示这个entry是否已经被删除了，已经删除置为true，未被删除置为false。

将lazy deletion应用到我们的算法中：在第二步删除key值为2的键值对之后，再删除key值为10的键值对；由于index 2处entry不为空，我们需要继续向后寻找，找到key值为10的键值对，将其deleted域置为true。问题得到完美解决。

需要注意的是，被标记删除的entry会一直留在哈希表中，不能被清空，也不能被替换。在哈希表中元素个数过多，进行rehash操作时，被懒惰删除的entry被丢弃，不会进入到rehash之后的哈希表中。

允许清空懒惰删除的entry导致的问题如上所述。如果允许替换懒惰删除的entry，也会带来棘手的问题。

在上面的例子中，懒惰删除index为2的键值对之后，再向哈希表中插入键值对{key: 10, val: 20}；允许替换懒惰删除的entry后，那么这键值对会直接被放置在index为2处，现在哈希表的状态为：

哈希表中有两个键值为10的键值对，这是不能接受的。我们插入键值对{key: 10, val: 20}的目的，是想替换原来已经有的键值为10的键值对，其实就是想改变一下key值对应的value，但是如果允许替换懒惰删除的entry，得到的结果会与我们的目的背道而驰。

附：Linear Probing Hashtable的Java实现

仓库地址：https://github.com/TimeSea05/sjtu-se/tree/master/hashtable-2019

HashTable.java

class HashTableEntry {
    public int key;
    public int value;
    public boolean deleted;
    HashTableEntry(int key, int value) {
        this.key = key;
        this.value = value;
        this.deleted = false;
    }
}

public interface HashTable {
    public void Set(int key, int value);
    public String Get(int key);
    public void Delete(int key);
}

LinearHashTable.java

public class LinearHashTable implements HashTable {
    private HashTableEntry[] table;
    private int nElem;
    private int cap;
    final int INITIAL_CAP = 8;
    public LinearHashTable() {
        table = new HashTableEntry[INITIAL_CAP];
        nElem = 0;
        cap = INITIAL_CAP;
    }
    
    private int hashFunc(int key) {
        return key % cap;
    }
    
    private void expandCap() {
        cap *= 2;
        rehash();
    }
    
    private void rehash() {
        HashTableEntry[] oldTable = table;
        table = new HashTableEntry[cap];

        nElem = 0;
        for (HashTableEntry entry: oldTable) {
            if (entry != null && !entry.deleted) {
                Set(entry.key, entry.value);
            }
        }
    }
    
    public void Set(int key, int value) {
        if (nElem >= cap / 2) {
            expandCap();
        }

        int pos = hashFunc(key);
        int firstTombstone = -1;

        while (table[pos] != null) {
            if (table[pos].deleted && firstTombstone == -1) {
                firstTombstone = pos;
            }
            if (table[pos].key == key && !table[pos].deleted) {
                table[pos].value = value;
                return;
            }
            pos = (pos + 1) % cap;
        }
        if (firstTombstone != -1) {
            table[firstTombstone] = new HashTableEntry(key, value);
        } else {
            table[pos] = new HashTableEntry(key, value);
            nElem++;
        }
    }

    public String Get(int key) {
        int pos = hashFunc(key);
        while (table[pos] != null) {
            if (table[pos].key == key && !table[pos].deleted) {
                return Integer.toString(table[pos].value);
            }
            pos = (pos + 1) % cap;
        }
        return "null";
    }

    public void Delete(int key) {
        int pos = hashFunc(key);
        while (table[pos] != null) {
            if (table[pos].key == key) {
                table[pos].deleted = true;
            }
            pos = (pos + 1) % cap;
        }
    }
}