hashtable - 人们说“搜索哈希表”是什么意思？

Question

假设您有一个哈希表，其中包含员工姓名作为键，每个桶中包含员工工资。

当人们说要写一些东西来搜索这个哈希表时，他们指的是什么？搜索功能的输入是什么？

他们的意思是搜索特定员工的薪水吗？在这种情况下如何处理碰撞？

我的问题有所不同，因为我要求澄清我经常听到的一个口语术语，特别是在示例问题的上下文中。

我并不是真的要求代码实现。关于碰撞的问题可能是与实现相关的最接近的问题，例如提供的可能重复的答案，但即便如此，这个问题也可以在理论上得到回答。

标签： hashtable

Answer 1

您要求猜测人们所说的不准确的术语是什么意思。除了确定是否已经存储了关联值之外，哈希表在任何真正意义上都没有真正“搜索”。

在您的示例中，键是员工姓名。

• 作为输入的名称哈希计算解析为存储桶的值。
• 那个桶可以是空的。
• 如果存储桶不为空，则返回存储在存储桶中的值。

这有一个明显的问题，您可能会注意到作为许多流行语言的标准数据类型或类库的一部分的关联数组无法处理这个问题。

如果您有“John Smith”作为员工并雇用了名为“John Smith”的第二名员工，则哈希表无法区分两人之间的区别。所以要明确一点，如果您尝试添加新的 John Smith，它将拒绝新的 John Smith 或覆盖第一次存储的工资值。这是一个可能属于您的问题范围的实现细节，并解释了为什么我们将 id# 与我们的身份或基本上任何数据库系统相关联。

哈希表必须处理的主要问题是哈希冲突。这是当有 2 个或更多输入散列到相同的值时。

通常发生的情况是，在散列计算发生后，它会查看存储桶数据结构。有2种可能：

• 桶是空的
• Bucket 有一个或多个条目

那么解决多个条目需要什么？其他一些答案列举或详细介绍了用于处理冲突的方案。显而易见且简单的答案是，存储的数据结构通常包含键：值对。

假设“Bob Jones”和“Sam Smith”都散列到桶“Z”。在存储桶 Z 中，您可能会找到如下值的链接列表：

Bucket Z:  ["Sam Smith": 23000] -> ["Bob Jones": 48500]

->表示实现用于查找下一个条目的指针。

希望这说明了存储桶实际上可以为不同名称存储多个薪水值并仍然返回与原始键关联的正确薪水的方式。这可以被认为是实际的“搜索”，因为系统需要搜索与原始键关联的值，但散列本身只是一个计算。以众所周知的哈希算法为例，例如 MD5 或 SHA1。哈希是计算而不是搜索。哈希表是一种将哈希值组合为索引的数据结构，用于查找先前存储的值或存储新值。