查找表是哈希表的一种形式吗？

Question

我想确认一下我的理解是否正确 . .

如果我想避免为浮点数据数组 x 中的每个元素计算一个计算复杂度高的 someExpensiveFun(x)，比如设定在零到一之间。那么可以先预计算昂贵函数的输出结果，并将其存储在表格中 . . .

for (int nn = 0; nn < 1000; ++nn)
{
    float tmp = ((float)nn) / 1000.f;
    lookup[nn] = someExpensiveFun(tmp);
}

在性能关键代码的主体部分，我可以使用...

y = lookup[(int)floor(x*1000.f)];

把lookup称为哈希表的一种形式，x*1000则是相应的哈希函数这样说概念上是正确的（不算术语滥用）吗？

- learnvst

---

我会说不，但不确定其他人怎么想。 - Steven

相反，我更愿意说哈希表是查找表的一种类型。 - user529758

(int) floor(x * 1000.f) 可以被视为哈希函数。@H2CO3 在指出哈希表仅是一种查找表的形式方面是正确的。 - obataku

有几种类型的哈希表，但关键（双关语）是它们使用某个哈希函数将关键字转换为索引。在这种情况下，您使用了一个避免冲突的最小完美哈希函数，因此这会被翻译为array[hash(key)]，就像您对于x [0,1)的lookup[x*1000]一样。 - obataku

@SteveJessop 线性哈希函数（注意我说的话）只是用来举例说明的，吹毛求疵的人 ;P - learnvst

Answer 1

个人认为这是对术语的滥用。它缺少人们自然期望从哈希表中得到的属性，特别是能够处理具有相等哈希值但不相等键的能力。而且我非常确定你的“哈希函数”必须被视为floor(x*1000.f)或(int)floor(x*1000.f)，而不仅仅是x*1000.f。

哈希表通常可以接受其键类型的任何值作为键，而不仅仅是范围内的值，但也许我在那里太挑剔了。我不会把不能将NaN作为键的普通哈希表称为“不是哈希表”。

它与哈希表有一些共同点（一个非单射函数，将键映射到整数，这些整数用作数组中的索引）。如果有人想决定这两个条件共同表征“哈希表”，好的，祝他们好运，这就是一个哈希表 :-)

- Steve Jessop

---

同意，但完美哈希不需要冲突解决 ;-） - obataku

@oldrib：是的，我想到了这一点，也认为我不需要提及它。完美哈希通过在第一次选择不同的哈希值来处理冲突！它还具有仅适用于键类型中选定值的属性。 - Steve Jessop

感谢您认真的回复+1。我正在努力寻找区分的关键特征，但我找不到简明的定义。 - learnvst

@leanvst：确实，当你将变体归为一个通用名称时，数据结构甚至算法也可能会出现这种情况。我可能无法精确定义“哈希表”或“快速排序”，但我知道看到它们时该怎么做。 - Steve Jessop

Answer 2

不，称查找表为哈希表在概念上是不正确的：在您的情况下，查找表是一个简单的数组。称呼某物为哈希表意味着在哈希函数不完美时（即存在哈希冲突的情况下）会有某些行为；数组没有这些行为，因此将其称为“哈希查找”可能会误导听众或读者。

通常，任何类型的关联存储，包括哈希表、各种树等，都可以用于执行查找操作。在您的情况下，数组的索引与存储在该索引处的值相关联，让您能够在常数时间内查找该值。

- Sergey Kalinichenko

---

我不同意。楼主认为这可以被视为哈希表，这是有道理的。哈希表将输入键与唯一输出值关联起来（即它们是映射）-- 在这种情况下，通过使用极小完美哈希函数，每个 x 都与 someExpensiveFun(x) 关联。请注意，哈希表并不一定需要使用传统的哈希函数来实现，只要满足上述条件即可。 - obataku

@oldrinb 我想你可以称数组索引为“最小完美哈希函数”，尽管我认为这会使事情变得更加复杂。称其为“数组查找”能更好地传达意思。 - Sergey Kalinichenko

Answer 3

你的想法有些倒错了。哈希表总是可以用作数组的慢速替代，但是数组不能用作哈希表的替代（除非满足某些非常严格的前提条件）。

在你的情况下，查找甚至不能产生与计算相同的结果，只能产生接近的近似值。真正的哈希表将区分哈希到相同索引的不同输入。

- Mark Ransom

Answer 4

是的，如果您接受维基百科对哈希表的定义。引用该定义：

Ideally, the hash function should map each possible key to a unique slot index,
but this ideal is rarely achievable in practice (unless the hash keys are fixed;
i.e. new entries are never added to the table after it is created).

您选择了数组，因为函数域定义良好且相对较小，适合作为数组的索引 - 函数域具有映射到数组索引的特性。您可以将索引视为哈希表的键，而函数输出则是相关联的值。

- amdn

Answer 5

您可以通过哈希表替换所有查找表，但不能通过查找表替换所有哈希表。因此，是的，查找表可以被认为是哈希表的一种特殊形式，而哈希表可以被认为是查找表的一般形式。

同样地，列表可以被认为是一个具有单列的二维表的特殊形式。

然而，我们在这里谈论的是软件。对于给定问题，有无数种不同的解决方案和构建数据结构的可能性。例如，使用静态大小或动态增长，需要唯一条目或冲突处理，使用固定或可配置的哈希函数等。在纯查找表和完整哈希表之间有很多方法，没有明确的边界可以说这里是这个，那里已经变成了那个。

然而（再次），当特定的数据结构被证明是有用的时，它通常会得到自己的名称。正如在这里所说的那样，这个名称与功能有关的期望。甚至可能有关于所需最小功能的严格定义。如果您希望您的代码能够被其他人阅读，请坚持使用已知的术语。因此，即使从技术上讲它是哈希表的一种特殊形式，您也应该将您的查找表称为查找表。

- Secure