5

我想看看我在这里的概念是否正确。.

如果我试图避免必须为someExpensiveFun(x)浮点数据数组中的每个元素计算计算量大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？

4

5 回答 5

4

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

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

于 2012-09-19T19:19:08.233 回答
4

我个人认为这是对术语的滥用。它缺乏人们自然期望从哈希表中获得的属性，尤其是对具有相等哈希的非相等键执行某些操作的能力。而且我很确定您的“哈希函数”必须被视为floor(x*1000.f)or (int)floor(x*1000.f)，而不仅仅是x*1000.f.

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

它与哈希表有一些共同的属性（将键映射到整数的非内射函数，所述整数用作数组中的索引）。如果有人想确定这两个东西共同表征“哈希表”，好吧，祝他们好运，这是一个哈希表:-)

于 2012-09-19T19:32:32.837 回答
2

你倒过来了。哈希表总是可以用作数组的慢替代品，但数组不能用作哈希表的替代品（除非满足一些非常严格的先决条件）。

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

于 2012-09-19T20:02:42.627 回答
1

是的，如果您接受 Wikipedia 对hash table的定义。引用该定义：

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).

您选择了一个数组，因为您的函数的域定义明确且相对较小，并且适合作为数组的索引 - 函数的域具有到数组索引的到映射。您可以将索引视为keyto，hash table而函数输出是关联的值。

于 2012-09-19T20:10:03.560 回答
1

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

类似地，列表可以被认为是二维表的一种特殊形式（只有一列）。

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

然而（再一次），当一个特定的数据结构被证明是有用的时，它通常有自己的名字。正如这里所说，有了这样的名称，就会对功能产生相关的期望。甚至可能对所需的最低功能有严格的定义。如果您希望其他人可以阅读您的代码，则最好遵守已知术语。因此，您应该将您的查找表称为查找表，即使从技术上讲它是一种特殊形式的哈希表。

于 2012-09-20T07:31:03.993 回答