如何创建一个散列表

我想在继续之前提到我已经看过其他问题，在本网站以及其他网站上询问同样的事情。我希望我能得到一个很好的答案，因为我的目标是双重的：如何创建一个散列表

首先，我想了解如何创建一个哈希表。
其次，我发现Stack Overflow上的很多答案倾向于假设对某个主题的某种程度的知识，而这个主题经常不存在，特别是对于较新的类型。话虽如此，我希望编辑我的主要信息，以便在我自己弄清楚的情况下，更深入地解释这一过程。

到主过程：

正如我理解他们到目前为止，哈希表是列出的阵列（或类似的数据结构），该希望，最佳，具有少碰撞以尽可能地保持它被称赞的O（1）复杂性。以下是我的当前进程：

所以我的第一步是建立一个指针数组：

Elem ** table; 
table = new Elem*[size];//size is the desired size of the array

我的第二个步骤是创建一个散列函数（一个非常简单的一个）。

int hashed = 0; 
hashed = (atoi(name.c_str()) + id) % size; 
//name is a std string, and id is a large integer. Size is the size of the array.

我的第三个步骤是创建一些检测碰撞，这是目前在我的部分。

下面是一些伪代码：

while(table[hashedValue] != empty) 
    hashedValue++ 

else 
    put in the list at that index.

这是比较粗俗，但我仍然在“这是什么”的阶段。忍受着我。

还有别的吗？我错过了什么或者做错了什么？

由于

来源

2011-11-20 Joshua

看起来不错，有点。散列值索引到一个固定数组中，每个数组元素是一个实际值列表。 –

手柄发现没有空闲时隙，并调整表。

来源

2011-11-20 23:42:28

你错过了Elem的定义。这不是微不足道的，因为它取决于你是想要一个chaining还是一个探测哈希表。

来源

2011-11-20 23:44:01

对不起，我有一个我没有提供的定义。这是一个链表。 – Joshua

@Joshua：假设你不想存储重复数据，那么碰撞检测只是一个走这个列表的问题。 –

散列函数为相同的数据产生相同的值。然而，您的碰撞检查会修改该值，这意味着哈希值不仅取决于输入，还取决于哈希映射中其他元素的存在。这很糟糕，因为您几乎永远无法通过遍历地图来实际访问之前放入的元素。其次，你的碰撞检查容易出现溢出/范围错误，因为你只是增加散列值而不检查映射的大小（尽管如前所述，你甚至不应该这样做）。

来源

2011-11-21 00:44:59 Xeo

我想我没有提供足够的信息，对不起。我哈希的对象有一个私有名称和ID，所以它们都始终存在于对象中。 – Joshua

@Joshua：这不是我的意思。在你的碰撞检查中，如果你的计算点不是免费的（只要下一个点不是免费的），就可以改变哈希值。这意味着，根据哈希映射的负载，对于相同的数组大小，如果在生成相同哈希值之前插入的另一个元素（即发生冲突），则可以将该元素插入到不同的位置。这将不允许您通过插入它的同一个键访问该元素。 – Xeo

如何创建一个散列表

回答

相关问题