问题标签 [linear-probing]

线性探测的主要问题是聚类，许多连续的元素形成组，并且开始花费时间来寻找空闲槽或搜索元素。

为什么组中的连续元素以及它如何影响找到空闲槽的时间？

我正在尝试在处理多个“动物”的哈希表中编写线性探测的解决方案，类似于下面给我的那个。

但有人告诉我，这只是一种动物的解决方案，在一个位置。所以这是我目前针对多种动物的解决方案：

但是我在考虑找到一个自由职位的解决方案时遇到了问题。我应该使用另一个 for 循环吗？如果我只是在我的代码中复制了上面的第二个 if 语句，我相信如果索引已经被占用，我试图添加的“动物”将被跳过，并且“i”将在末尾递增到下一个动物循环。

我正在查看这个StackOverflow 答案以更好地理解散列并看到以下内容（关于我们需要在恒定时间内获取存储桶大小的事实）：

如果您使用线性探测或双散列等方法，找到所有散列到相同值的项目意味着您需要对值进行散列，然后遍历表中非空项目的“链”以查找其中有多少哈希到相同的值。但是，这与散列到相同值的项目数量不是线性的——它与散列到相同或冲突值的项目数量成线性关系。

这意味着它“与散列到相同或冲突值的项目数量呈线性关系”是什么意思？它对哈希表中的项目总数不是线性的吗，因为它可能需要在线性探测期间遍历每个值？我不明白为什么它只需要通过那些相撞的。

例如，如果我在散列表上使用线性探测（步长 1）并且我有不同的键（不冲突，所有散列到唯一值）映射到奇数索引槽1,3,5,7,9.....然后，我想插入许多所有散列的键到 2，所以我用这些键填充了所有偶数索引点。如果我想知道有多少键哈希为 2，我不需要遍历整个哈希表吗？但我不只是遍历散列到相同或冲突值的项目，因为奇数索引槽没有冲突。

嗨，我是 Python 新手，我实现了一个哈希表类，它通过线性探测来解决冲突。

现在我正在尝试编写一个函数来跟踪碰撞次数和探头长度。我已经编写了函数来跟踪碰撞次数，但我不知道如何跟踪探头长度，因为我以为他们是一样的？

编辑：好吧，显然碰撞意味着 hash(key) 给出的位置已经被占用。探测长度是在那之后你做了多少次尝试，直到你找到一个位置（在开放寻址中）。

所以我猜应该是这样的：

我正在创建一个哈希图，它进行线性探测以找到键的索引。如果键已经在索引中，我想增加它的值，而不是在新索引中添加一个。

例如，如果我得到字符串“五、五、五”的字数，我的输出是五个 1、五个 1、五个 1，而不是五个 3。

我认为它一定是我的 containsKey 方法，它使用 get 方法检查我的密钥是否已经在地图中。下面是我的 Hashmap.java 类。

关于线性探测（哈希表）有一件事对我来说并不直观。如果我将 key1 其哈希结果放入数组索引 1。然后我放入 key2 -> 数组索引 2。然后我将 key3 -> 再次放入数组索引 1，这将转到数组索引 3。然后当我搜索 key3 我应该去通过包含与我的哈希完全不同的键的索引。这不是浪费吗？如果序列真的很大并且包含许多键（例如，我有 20 个元素，然后为 null，对于导致数组索引从 0 到 20 的任何键，我必须遍历所有索引，尽管它们与我的哈希值不同我可以通过单独的链接来消除它）。

或者我们的散列函数（如果写得足够好）在索引之间平均分配键并且我们不断调整数组的大小以最大半满这一事实减轻了这种情况？

长度为 10 的散列表使用散列函数 h(k)=k mod 10 和线性探测的开放寻址。将8个值插入一个空的hash表后，表如下图

使用相同的散列函数和线性探测，有多少个不同的键值插入序列会产生如上所示的散列表？

答案 - 128。

我知道 91,2,13,24,77 是 5！= 120 但我不知道其他 8 种组合是什么？

请有人通过告诉我使用线性探测搜索条目的通用算法来提供帮助。

我有以下内容，但我认为它是伪代码而不是算法：1）使用哈希函数查找项目应该在哪里的索引。2）如果不存在，则搜索该哈希位置之后的记录，直到找到它，或者直到找到一个空记录。3）如果在找到记录之前表中有空位，则表示该记录不存在。

我在hackerearth 上研究哈希表，在那里我遇到了使用线性探测实现哈希表的代码。我对这段代码有两个疑问：-

1）为什么他们声明大小为 21（而不是大小为 20）的 hashTable 最多可容纳 20 个元素？

2) 在 Insert 函数中，如果在连续迭代后 index 的值与 Index 的初始值相同，while 循环是否会无限运行？

链接到hackerearth页面：- https://www.hackerearth.com/practice/data-structures/hash-tables/basics-of-hash-tables/tutorial/

这是我对线性探测的理解。

对于插入： - 我们散列到某个位置。如果该位置已经有值，我们线性递增到下一个位置，直到我们遇到一个空位置，然后我们插入那里。那讲得通。

我的问题围绕着查找。从我读过的描述中，我相信查找是这样的：

• 我们查看我们正在寻找哈希的项目的位置。
• 如果位置为空，我们返回 Not Found
• 如果位置已满，我们会线性移动到位置，直到遇到我们要查找的值，或者遇到空位置（意味着未找到）

那么当我们从散列中删除一个项目时，这是如何工作的呢？这不会弄乱这个查找吗？说两个项目散列到相同的位置。我们添加这两个项目，然后删除我们添加的第一个项目。所以现在，第二个项目的预期位置（必须移动到不同的位置，因为第一个项目最初占据了它）是空的。删除是否以某种方式处理这个问题？