Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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?

share|improve this question
28  
You seem to slightly misunderstand what hashes are. Uniqueness is explicitly not a feature of hash functions (i.e. they are never injective). –  Peter Taylor Sep 14 '11 at 7:21
    
@Peter Taylor: hash tables do define injective mappings. –  reinierpost Sep 14 '11 at 7:24
2  
@Peter Taylor: to be a little nitpicky, they dont need to be injective, but sometimes they are even bijective. Think of the typical implementation of an hashing function for an integer :) –  keppla Sep 14 '11 at 7:26
4  
A hash can be unique, as long as either the key space is not larger than the hash value space (for table hashes), or the hash value space is that large that collisions are mathematically infeasible (for cryptographic hashes). –  Secure Sep 14 '11 at 7:55
1  
Also, a "key table" sounds more like any "key/value" datastructure (also called "dictionnary"). Not all key/value datastructures are hash tables. –  barjak Sep 14 '11 at 11:46
show 2 more comments

7 Answers

up vote 39 down vote accepted

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.

share|improve this answer
2  
Not sure what the 'sub-domains' are doing in there. It's just that the hash function thoroughly 'mixes up' the values of its domain. –  reinierpost Sep 14 '11 at 7:26
add comment

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.

share|improve this answer
1  
it depends on what you mean by hash table. The data structure as offered in languages such as Perl, Java and C# does give you a key-to-value mapping, using the kind of hash table you refer to internally. –  reinierpost Sep 14 '11 at 7:30
add comment

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).
share|improve this answer
add comment

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

share|improve this answer
2  
It's actually written "hachage" and "hacher" without an accent. –  Ptival Sep 14 '11 at 8:29
    
@Ptival : Thanks. –  Xavier T. Sep 14 '11 at 13:53
add comment

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.

share|improve this answer
    
+1 for the supervillain example –  WaelJ Sep 14 '11 at 15:13
    
However with the caveat the super villain can also return the same hash as a super hero with a given set of parameters since hashing doesn't seem to dictate uniqueness. There are hash collisions after all...its what you do after the collision... –  Rig Dec 2 '12 at 5:09
add comment

If we are looking for the meaning of HashTable first we should understand what is the meaning of hashing. Oxford dict. meaning of hashing is to cut,chop and later mix to produce homogeneous product, now if you see your HashTable its nothing but the bricks of keys & values representing the single uniform object.

:)

share|improve this answer
add comment

I see it has been answered, yet my add-on is: 'HASH' also means 'SLASH' as a verb/noun. That's why I call my hashers slashers. Just imagine a sword/chopper/cleaver cutting something into pieces.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.