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

Question

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

如果我试图避免必须为someExpensiveFun(x)浮点数据数组中的每个元素计算一个计算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)or (int)floor(x*1000.f)，而不仅仅是x*1000.f。

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

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

Answer 2

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

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