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

Question

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

如果我试图避免为 float 据数组 x 中的每个元素计算计算量大的 someExpensiveFun(x)，假设有界值在 0 和 1 之间，可以先预先计算昂贵函数的输出并将其存储在表中。 . .

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 称为相关的哈希函数在概念上是否正确(而不是滥用术语)？

Answer 1

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

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

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