Is a lookup table a hash table form?

Question

I'm trying to figure out if I'm really conceptually right.,

If I try to avoid computing the computationally expensive someExpensiveFun(x) for each element of the x floating-point data array, say limited to values ​​between zero and one, you can first compile 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 part of the critical performance code I can use.,.

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

Is it conceptually correct (and not an abuse of terminology) to call a lookup hash table shape and x*1000 related hash function?

Answer 1

Personally, I would say that this is an abuse of terminology. It lacks the properties that people naturally expect from a hash table, in particular the ability to do something unequal keys with equal hashes. And I am sure that your "hash function" should be considered as floor(x*1000.f) or (int)floor(x*1000.f) , and not just x*1000.f

Hash tables can also usually take as a key any value of their key type, not just the values ​​in the range, but maybe I'm too picky. I would not name the hash table otherwise, which did not allow NaN as a key, and not the hash table.

It has some common properties with hash tables (a non-injection function that maps keys to integers, specified integers used as an index in an array). If someone wants to decide that these two things together characterize a “hash table”, well, good luck to them, this is a hash table :-)

Answer 2

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

In general, any auxiliary storage, including hash tables, various trees, etc., can be used to perform search operations. In your case, the array index is associated with the value stored in that index, which allows you to look up the value in constant time.

Answer 3

You have it in the opposite direction. A hash table can always be used as a slow replacement for an array, but an array cannot be used as a replacement for a hash table (unless some very strict prerequisites are met).

In your case, the search does not even yield the same results as the calculation, only a close approximation. A true hash table will distinguish between different inputs that are hashed with the same index.

Answer 4

Yes, if you accept the definition of a Wikipedia hash table . A quote from this 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; ie 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 the index of the array - the function area has a mapping to the array index. You can represent the index as key in the hash table , and the function output is the associated value.

Answer 5

You can replace all hash tables with hash tables, but you cannot replace all hash tables with lookup tables. Thus, a lookup table can be considered as a special form of a hash table, and a hash table can be considered as a general form of a lookup table.

Similarly, a list can be considered as a special kind of 2D table (with a single column).

However, we are talking about software here. There are various options for solving this problem, as well as various options for building your data structures. For example, with a static size or dynamic growth, with the required unique records or with conflict handling, with a fixed or custom hash function, etc. There are many ways between a simple lookup table and a complete hash table without a clear boundary, where you could say here that it is, but it has become there.

However (again), when a particular data structure proves useful, it usually gets its own name. As mentioned here, this name is associated with expectations regarding functionality. There may even be a strict definition of the required minimum functionality. If you want your code to be read by others, you must adhere to well-known terms. So you have to call your lookup table into the lookup table, although technically this is a special form of the hash table.