Is a lookup table a form of hash table?

Question

I am trying to see if I am conceptually correct here . .

If I'm trying to avoid having to compute a computationally expensive someExpensiveFun(x) for every element in an array of floating point data x, say bounded to values between zero and one, one can first precompute the output of the expensive function and store it in a table . . .

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

Then in the main body of performance critical code I can use . . .

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

Is it conceptually correct (and not an abuse of terminology) to call lookup a form of hash table and x*1000 the associated hashing function?

Answer 1

Personally I'd say it's an abuse of terminology. It lacks properties that people naturally expect from a hash table, notably the ability to do something about non-equal keys with equal hashes. And I'm pretty sure your "hash function" has to be considered as floor(x*1000.f) or (int)floor(x*1000.f), not just x*1000.f.

Hash tables also normally can accept as key any value of their key type, rather than just values in a range, but maybe I'm being too picky there. I wouldn't call an otherwise-normal hash table that didn't allow NaN as a key, "not a hash table".

It has some properties in common with hash tables (a non-injective function that maps keys to integers, said integers used as an index in an array). If someone wants to decide that those two things together characterize "a hash table", OK, good luck to them, it's a hash table :-)

Answer 2

No, it is not conceptually correct to call a lookup table a hash table: in your case a lookup table is a simple array. Calling something a hash table implies certain behavior in cases when the hash function is not perfect (i.e. in the presence of hash collisions); arrays have none of this behavior, so calling this a "hash lookup" would likely mislead your listeners or readers.

In general, any kind of associative storage, including hash tables, various trees, and so on, can be used to perform lookup operations. In your case, the index of the array is associated with the value stored at that index, letting you look up the value in constant time.

Answer 3

You have it backwards. A hash table can always be used as a slow substitute for an array, but an array cannot be used as a substitute for a hash table (unless some very strict preconditions are met).

In your case the lookup doesn't even produce the same results as the calculation, only a close approximation. A true hash table would differentiate between different inputs that hashed to the same index.

Answer 4

Yes, if you accept Wikipedia's definition of hash table. Quoting from that definition:

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

You have chosen an array because the domain of your function is well defined and relatively small and lends itself to be the index of the array - the domain of the function has an onto mapping to the index of the array. You can think of the index as the key to the hash table and the function output is the associated value.