Why it is called "hash table", or "hash function"? Hash doesn't make any sense to me here [closed]

Question

It's now about 4 years of development that I'm using, hearing, talking about, and implementing hash tables and hash functions. But I really never understand why it's called hash?

I remember the first days I started programming, this term was kind'of cumbersome terminology to me. I never figured out what is it, based on its name. I just experimentally understood what it does and why and when should we use it.

However, I still sometimes try to figure out why it's called hash. I have no problem with table or function and to be honest, they are pretty deductive, rational terms. However, I think better words could be used instead of hash, like key, or uniqueness. Don't key table or uniqueness table.

According to my dictionary, hash means:

1. Fried dish of potato and meats (highly irrelevant)
2. # symbol (AKA number sign, pound sign, etc.) (still irrelevant, maybe just a mis-nomenclature)
3. Apply algorithm to character string (still has nothing to do with uniqueness, which is the most important feature of a hash table)
4. Cut food
5. Another term for hashish

Does anyone know why it's called hash?

Answer 1

According to wikipedia, it refers to the hash function. If you want to go a step further, the wiki page for hash function says that the use of the word "hash" in hash function originated like so:

The term "hash" comes by way of analogy with its non-technical meaning, to "chop and mix". Indeed, typical hash functions, like the mod operation, "chop" the input domain into many sub-domains that get "mixed" into the output range to improve the uniformity of the key distribution.

Answer 2

In French, a hash table is called "table de hachage", the related verb "hacher" means to chop/to mince (food mostly). The verb to hash has the same meaning in English.

So as other have pointed out it is called hash, because you chop your input that you put in pieces in different places (your table entries).

Answer 3

Number 3 has everything to do with it. From Wikipedia:

At the heart of the hash table algorithm is a simple array of items; this is often simply called the hash table. Hash table algorithms calculate an index from the data item's key and use this index to place the data into the array. The implementation of this calculation is the hash function, f:

index = f(key, arrayLength)

The hash function calculates an index within the array from the data key. arrayLength is the size of the array. For assembly language or other low-level programs, a trivial hash function can often create an index with just one or two inline machine instructions.

So a hash table doesn't really store values based on a key; it stores values based on a hashed version of that key.

Answer 4

hash tables are called that way because of using hash code and it's related to "cut food".

Think of it like this - you take your nice pretty object, like a fruit, then hash it so that it starts looking just like anything else - just a number - there's no more structure in it anymore. That piece of "cut food" is used in hash table to find out your nice pretty object.

• It looks uglier than your pretty object? maybe - but it helps to find it fast - that's the point. oh and it's not unique that's for sure.
   
  Hash code finds a bucket in the table where your pretty object sits in a small company of others with same hash code. Within this small company, object is looked up using equality check - which is expected to be much slower than hash lookup but it's not a big deal since there are only a few of them (most of other objects are already ignored thanks to fast hash).

Answer 5

Hashing (as in cutting into small pieces, shredding, etc.) takes an input (food or sometimes supervillains) and transforms it into a relatively homogeneous output. I.e. no matter what you had in the beginning, in the end you just have hash. And a spoonful of the hash is about as helpful as all the hash in determining, what the input was (assuming your hashing machine hashes well).
So hashing can reduce any edible or evil object into a spoonful of hash, where two different objects yield different hashes, whereas two equal objects yield equal hashes. Which means if two supervillains fell into your hashing machine, it suffices comparing their hashes to determine whether one was a clone of the other.

In a way hashing functions in computer science are a bit alike. They take a whole input of different size and semantics, and -very simply put- they just cut it into pieces and mix those around and cut the resulting sequence back into pieces and mix that around and so on. In the end you have a spoonful (n bytes) of the input you hashed.