问题标签 [linear-probing]

因此，我使用 Java 中的线性探测从头开始构建哈希表，方法如下：put(int key, String value)、get(int key)、remove(int key) 和 size()。所以我成功地实现了这些方法，但是我有一个理论问题。例如，我执行以下操作：

我的 put 方法工作正常，并根据线性探测算法放置键值对。现在我的输出是：

[空, 1=a, 13=e, 3=b, 4=c] 空

所以我的问题是，如果我的“get”方法理论上失败（因为线性探测）来获取键值对 13=e，因为删除方法在索引 0 处放置了一个空值。另外，如果我不使用删除，我已成功获得 13=e 对。

我正在尝试为 C 中的哈希表实现冲突解决的线性探测。我正在使用 RRN（记录相对编号）从文件中插入和检索信息，以定位将插入/检索每个寄存器的索引。最初，我将所有索引值设置为“_”作为将它们标记为空的一种方式。到目前为止，一切都很好。我遇到的问题是当我实际尝试实施碰撞解决方案时。该程序似乎正在覆盖那里的记录，而不是寻找下一个可用位置。此外，当我有目的地查找不存在键（名称）的记录时，程序会卡住。

每当 fd=0 时（换句话说，当它到达文件末尾时），我都会将指针设置回文件的开头，但有些东西告诉我这可能是问题所在。大家可以看看吗？提前致谢：

为了清楚起见，我省略了一些代码，但这是我实现 while 循环以验证寄存器是否为空的地方：

当用于线性探测散列技术的数组已满时，我可以添加更多元素吗？

我理解线性探测中的问题，即由于后续索引将存在元素簇。但我不明白这句话The bigger the cluster gets, more it reduces the performance.如何降低散列的性能？

所以我有一个任务是在 c 中创建一个读取几个句子（一个 140mb 文件）的程序，并且基于第二个输入，它是一个数字，我需要返回第 N 个最常见的单词。我的想法是建立一个带有线性探测的哈希表，每次我得到一个新元素时，我都会根据它的位置和 djb2 对它进行相应的哈希处理，否则如果发生冲突，我会重新哈希处理。之后，我根据出现应用快速排序，然后最终按索引访问。我在用 c 中的线性探测完成哈希表时遇到问题。我很确定我已经完成了它，但每次我运行时，我都会在 lldb 上遇到堆缓冲区溢出。我试图发现这个问题，但我仍然无法弄清楚。

我的堆栈内存不足了吗？该文件相对较小以消耗如此多的内存。我使用了地址清理程序，并且在插入时出现了堆缓冲区溢出。

我认为我没有触及分配区域之外的内存，但我不是 100% 确定。

知道出了什么问题吗？这是 table.c 实现，您可以在下面看到结构的形式。

这是来自地址消毒器的更详细信息：

表.c：

实体.h：

这是我从文件中读取并处理文本的方式：

有什么建议我的代码有什么问题吗？我相信调整大小可能有问题，我还没有正确删除，因为我在内存管理方面遇到了很多问题。

提前致谢！

一旦阈值超过预定量 0.65，此方法应该调整数组的大小。问题是在调整大小后，析构函数会删除包含所有新复制信息的数组。我不知道如何解决它。

关于那里的一些评论只是我集思广益可能是什么问题。

我在 python 中实现哈希表时正在观看有关线性探测的教程，并遇到了线性探测来解决冲突。

据我了解，使用线性探测，如果已经为现有键获取索引，我们需要从分配的内存开始搜索空槽，将值插入到找到的第一个空槽中。

我的问题是，如果将来填充插槽的地址由新密钥的哈希解决怎么办？它将在哪里存储价值？

例如： 如果对于一个键 - 3，哈希解析到地址 3000 并且它已经被占用，我们从 0000 开始进行线性探测，发现 0011 有一个空槽，并将值插入到那里。如果将来，我们想要插入一个键的值 - 9，其哈希被解析为地址 0011。如果我们已经从上一步插入了键 - 3 的值，会发生什么。

给定 n 个数字和一个大小为 m 的数组。当所有键使用线性探测散列到表中不同的偶数索引时，所需的最大比较次数是多少。

我知道我没有工作代码/最低限度，但我不是在代码中寻求更多帮助。我将尽可能地总结一下。该测试运行了1000多次尝试将50人员插入表中。试验随机生成基于 的密钥getRandomPersonalNumber。

如果有任何冲突，线性探测函数会返回，如果需要更新索引，并搜索键是否与索引匹配。现在在结果中，唯一看起来很奇怪的是Table 1我向一些朋友询问了结果，他们说可能模数100正在做某事，这就是为什么我得到高共谋结果的原因Table 1。

我担心这可能与我的计算有关，但话又说回来，它只发生在100 modulo，所以我不知道我能否在不依赖代码的情况下精确计算碰撞量？最后，有没有办法计算存储量与共谋量（负载因子）的良好中间立场？

表测试。

我的教授让我写一个关于线性探测的实际应用的代码。谁能帮我吗？