What is a hash map in programming and where can it be used

Question

I have often heard people talking about hashing and hash maps and hash tables. I wanted to know what they are and where you can best use them for.

Solution 1

First you shoud maybe read this article.

When you use lists and you are looking for a special item you normally have to iterate over the complete list. This is very expensive when you have large lists.
A hashtable can be a lot faster, under best circumstances you will get the item you are looking for with only one access.
How is it working? Like a dictionary ... when you are looking for the word "hashtable" in a dictionary, you are not starting with the first word under 'a'. But rather you go straight forward to the letter 'h'. Then to 'ha', 'has' and so on, until you found your word. You are using an index within your dictionary to speed up your search.
A hashtable does basically the same. Every item gets an unique index (the so called hash). You use this hash for lookups. The hash may be an index in a normal linked list. For instance your hash could be a number like 2130 which means that you should look at position 2130 in your list. A lookup at a known index within a normal list is very easy and fast.
The problem of the whole approach is the so called hash function which assigns this index to each item. When you are looking for an item you should be able to calculate the index in advance. Just like in a real dictionary, where you see that the word 'hashtable' starts with the letter 'h' and therefore you know the approximate position.
A good hash function provides hashcodes that are evenly distrubuted over the space of all possible hashcodes. And of course it tries to avoid collisions. A collision happens when two different items get the same hashcode.
In C# for instance every object has a GetHashcode() method which provides a hash for it (not necessarily unique). This can be used for lookups and sorting with in your dictionary.

When you start using hashtables you should always keep in mind, that you handle collisions correctly. It can happen quite easily in large hashtables that two objects got the same hash (maybe your overload of GetHashcode() is faulty, maybe something else happened).

Solution 2

Basically, a HashMap allows you to store items with identifiers. They are stored in a table format with the identifier being hashed using a hashing algorithm.

Typically they are more efficient to retrieve items than search trees etc.

You may find this helpful: http://www.relisoft.com/book/lang/pointer/8hash.html

Hope it helps,

Chris

Solution 3

Hashing (in the noncryptographic sense) is a blanket term for taking an input and then producing an output to identify it with. A trivial example of a hash is adding the sum of the letters of a string, i.e:

f(abc) = 6

Note that this trivial hash scheme would create a collision between the strings abc, bca, ae, etc. An effective hash scheme would produce different values for each string, naturally.

Hashmaps and hashtables are datastructures (like arrays and lists), that use hashing to store data. In a hashtable, a hash is produced (either from a provided key, or from the object itself) that determines where in the table the object is stored. This means that as long as the user of the hashtable is aware of the key, retrieving the object is extremely fast.

In a list, in comparison, you would need to in some way search through the list in order to find your sought object. This also represents the backside of hashtables, which is that it is very complicated to find an object in it without knowing the key, because where the object is stored in the table has no relevance to its value nor when it was inputed.

Hashmaps are similar to hashtables, but only one example of each object is stored in it (hence no key needs to be provided, the object itself is the key).

This is of course a very simple explanation, so I suggest you read in depth from this point on. I hope I didn't make any silly mistakes. =)

Comments

[Kasun Siyambalapitiya]

A well explained answer

[Teddy]

What do you mean "you (should) handle collisions correctly"? As fas as I know, we should just try to minimise collisions by writing good hash functions (for better performance). But, there is no need to "handle collisions". If hashes collide, it will just resort to next level of checking by doing equals comparison.

[tanascius]

@Teddy: Hash functions just do the hashing. There is no "next level". That's what I meant by "take care of collisions". When there is more than one match, you have to select by e.g. equal comparision.

[Teddy]

@tanascius I meant that the inbuilt collection HashMap uses hashCode function as first level check. If two items have same hashCode, HashMap will proceed to the next level check which is equals check. So, our job is to just write a decent implementation of hashCode for our custom object.

[tanascius]

@Teddy HashMap is Java specific, I don't know the exact behaviour. But the question overall is not Java specific. But you are right, certain implementations can differ and already have a built-in next level check.