HashTable / Python dict 什么时候停止探测？

Question

在 Java 中，我正在构建一个类似于 Python 中的字典的数据结构。（据我所知，这在 java 上下文中称为“哈希表”。）

我已阅读 the following Python documentation 以获得探测函数（因为我希望避免使用线性探测）

现在我已经到了我试图从我的“dict”中检索其内部数组中不存在的元素的地步。看来我的探测功能将无休止地寻找不存在的元素，因此我希望在某个时候中断并 return null。

我什么时候应该停止探测并且return null？

我目前的解决方案是对每个探测进行计数。曾经probeCount > size我break。然而，这似乎是一个糟糕的解决方案，因为确定元素不存在的时间复杂度为 O(n)，n 是我的数组的大小。

我的探测代码如下：

public Object get(long id) {

        int count = 0;

        int hashedIndex = (int) id;
        if (hashedIndex < 0) hashedIndex = -hashedIndex;
        hashedIndex = hashedIndex % size;
        int perturb = hashedIndex;
        while(true) {
            if (nodes[hashedIndex] != null || count > size) {
                if (count > size) {
                    System.out.println("null");
                    break;
                }
                if (nodes[hashedIndex].identifier == id) {
                    break;
                }
            }                       
            hashedIndex = (5*hashedIndex + 1 + perturb) % size;
            perturb >>= 5;
            count++;
        }
        return nodes[hashedIndex];
}

Answer 1

A Python dict 一旦发现一个空的、非“虚拟”插槽 - 一个不包含密钥且不包含指示密钥已删除的“虚拟”标记的插槽，它就会停止探测那里。

dict 实现确保至少有一个这样的插槽始终存在（通常更多），并且保证探测序列最终检查所有插槽，因此这保证了终止。

HashTable / Python dict 什么时候停止探测？

When does a HashTable / Python dict stop probing?

python

java

dictionary

hashmap

hashtable