2

我对哈希概念有一些理解问题，如下所示：

假设，我已经实现了将键作为数字的哈希表（一维数组，比如A[100] ）。我有一个简单的哈希函数H(Key) % Table_Size，它将目标索引返回到哈希表中（同时访问与此特定键关联的值）。

假设，我想将0（键）存储到表中。当我将此键传递给H（哈希函数）时，它会返回随机索引，例如 25。

数组 A 中的这个位置有 2 种可能性（索引为 25）：

  1. A[25] 包含除0以外的一些键，已存储（以前）
  2. A[25] 包含0

第一种可能性有冲突并且很容易识别（因为当前密钥：0 和已存储的密钥：k 不同），所以第一个没有问题。

但是，对于第二个，我怎么知道天气是否有碰撞？

据我所知，哈希表或数组将是主内存的一部分。假设 A[25] 存储在内存位置 500 中。

我怎么知道这个位置（500）实际上是空的还是已经被其他键填充了？

存储单元的什么状态或值代表EMPTY或NULL或UNUSED位置？

而且，如果我想将0作为密钥存储到此位置进行碰撞检查怎么办？

我目前假设如果任何内存位置是EMPTY或NULL或UNUSED，那么它将处于 RESET 状态（所有单元格都是 0）。这是真的 ？

这可能是个愚蠢的问题，但我想知道在这种情况下如何检查碰撞。

--

提前致谢！！（海得拉巴海泰因）

4

3 回答 3

2

这里的想法是您必须找到空单元格的表示。通常有以下三种：

第一个是：选择一个值，通常是 0 或 -1，你知道它永远不会出现在表格中来表示一个空单元格。然后，如果值在那里，你就知道你有一个空闲空间，你可以在那里放一些东西。

第二种是：使用指针数组：例如 int *array[100]。将指针初始化为 NULL。如果它们为 NULL，您可以分配一个整数并将位置设置为指向那里。

第三个是：使用辅助数组来判断位置 i 是否为有效位置。然后将所有初始化为空。每当您将某人放入数组 [i] 时，您就会设置为有效的有效 [i] 位置。

于 2012-10-26T18:12:54.430 回答
0

这是一个建议，可以节省内存并允许整数键的所有值。

将哈希表一分为二，使用密钥中的一个位，该位具有大约相等的 0 或 1 概率，并使用它来选择要搜索的哈希表的哪一半。从密钥中删除该位...如果您的密钥是 32 位，那么您现在有一个 31 位tag，您可以在哈希表中搜索。使用哈希表条目中的一位来指示空 (0) 或有效 (1)，最初都是 0。添加条目时，您设置标签（键减去用于选择哪一半的位），然后设置有效位。

于 2012-10-26T18:43:45.893 回答
0

要么用你知道永远不会出现的数字填充你的哈希表，显然不是 0，也许是 -1，或者使用指向 int 的指针并将它们设置为 null 为空。

于 2012-10-26T18:21:50.037 回答