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.

Junoesque

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

Occasionally

A well explained answer – Disastrous

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. – Thomson

@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. – Occasionally

@Occasionally 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. – Thomson

@Thomson 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. – Occasionally

Answer 2

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

Earlie

Answer 3

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

Tutti

Answer 4

Hashmap is used for storing data in key value pairs. We can use a hashmap for storing objects in a application and use it further in the same application for storing, updating, deleting values. Hashmap key and values are stored in a bucket to a specific entry, this entry location is determined using Hashcode function. This hashcode function determines the hash where the value is stored. The detailed explanantion of how hashmap works is described in this video: https://youtu.be/iqYC1odZSNo

Caboodle

Answer 5

Hash maps saves a lot of time as compared to other search criteria. We have a hash key that corresponds to a hash code which further helps to find its index value. In terms of implementation, hash maps takes a string converts it into an integer and remaps it to convert it into an index of an array which helps to find the required value.

To go in detail we can look for handling collisions in hash maps. Like instead of using array we can go with the linked list.

There is a short video available to understand it. Available here : Implementation example --> https://www.youtube.com/watch?v=shs0KM3wKv8

Sample: int hashCode(String s) { logic }

Measurable