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.

I was just wondering if there were some "standard" examples that everyone uses as a basis for explaining the nature of a problem that requires the use of a Hash table. What are some well-known problems in the real world that can see great benefits from using a Hash table?

Also, a little background or explanation as to why the problem benefits from using a Hash Table would be of help!

share|improve this question

closed as too broad by MichaelT, psr, Robert Harvey, gnat, Bart van Ingen Schenau Aug 6 '13 at 11:10

There are either too many possible answers, or good answers would be too long for this format. Please add details to narrow the answer set or to isolate an issue that can be answered in a few paragraphs.If this question can be reworded to fit the rules in the help center, please edit the question.

3  
Is this homework? –  Loki Astari Nov 25 '11 at 3:36
    
In the real world: en.wikipedia.org/wiki/Mail_sorter –  Patrick Nov 25 '11 at 12:20
add comment

8 Answers

Internet routers is a good example of why hash tables are required.

A router table (especially in those routers in the backbone networks of internet operators) may contain hundreds of thousands or millions of entries. When a packet has to be routed to a specific IP address, the router has to determine the best route by querying the router table in an efficient manner. HashTables are used as an efficient lookup structure having as key the IP address and as value the path that should be follow for that address.

share|improve this answer
add comment

Here's some common examples:

  1. T f(int); functions which should be modifiable on runtime
  2. sparse arrays, dynamic switch-cases etc
  3. array of pairs, [(a,b)]
  4. array of key-value pairs
  5. non-persistent databases with [(id, (a,b,c,d))]
share|improve this answer
add comment

Any form of search on strings needs Hash.

Consider for example, you have a list of tokens (basically each token is a string) is used as an index of a table with some property.


URL_index["google"] = { "http://www.google.com", 100} 
URL_index["yahoo"] = { "http://www.yahoo.com", 90} 
URL_index["amazon"] = { "http://www.amazon.com", 85} 

Now, you have a search string s is either of the above, you need to match the most relevant string. A brute force match will require StringCompare against each. However, you can make the Hash table of the URL_index and quickly make the search possible.

All search mechanisms in side databases, uses Hash table based indexes.

share|improve this answer
add comment

Dictionaries, a.k.a. maps or associative arrays, are often implemented using a hash table. A dictionary lets you map from a set of keys to a set of values; if you know a key, you can access, insert, or delete the associated value in constant time.

share|improve this answer
add comment

Vasilis's answer is really good. I'm going to volunteer something a little more general.

Even on a sorted array or binary search tree, the fastest a value can be found is Olog(n) (I think). Even this isn't fast enough, some times. If lookup speed is more important than anything else, hash tables are used. In something like an array, you have a list of references to objects (in object-oriented languages). To find an item, you need to first find it's reference in the list, and this is equivilent to running up and down the aisles of a grocery store looking for a particular product. Certain algorithms make this faster (binary search, for example) but these have certain requirements that might not be practical (the array must be sorted, for example). Hash tables, on the other hand, take the 'key' (the reference to an object) and 'hash it', or convert it to a mostly-unique value - that value is then used as the address of for the object that key points to.

What does this mean? Instead of needing to 'run up and down the aisles', a hash table implementation can take a given key and literally transform it into the address of whatever you're looking for, providing extremely fast lookups.

share|improve this answer
add comment

Here's a code example:

void Main()
{
    for(var i = 1; i < 100; i++)
    {
        Console.WriteLine(Factorial(i));
    }
}

private Dictionary<int, int> m_AlreadyCalculated = new Dictionary<int, int>();
private int Factorial(int num)
{
    if(m_AlreadyCalculated.ContainsKey(num))
        return m_AlreadyCalculated[num];

    if(num == 1)
        return 1;

    var result = num * Factorial(num - 1);
    m_AlreadyCalculated[num] = result;
    return result;
}

Rather than calculate 5! for every num > 5, we can just cache it and return the value.
Of course this is a very simple example, it can be used for complex calculations which never change.

share|improve this answer
add comment

Here's a practical example of a system I wrote (in Java, but the concepts are the same) a few years ago: It would take share prices coming in from various price feeds and perform calculations on those prices.

There were a few things to bear in mind:

  • different shares would have different calculations applied
  • prices had to be processed in the order they arrived relative to other quotes for the same share, but all the prices for share A could be processed before any of the prices for share B

So a price arrives as a piece of information like this (in this case for BP):

BP/1.23

How do we find which calculation to use? We look in a HashMap<String,CalculationRule> where the key is BP. What about processing all the prices for a particular share in order? HashMap<String,Queue<Price>>.

So the Hashmap is great for finding associated objects.

We never got this far as the project was canned, but there was talk of sharding the price system so that the load on each instance of the system could be reduced. Client systems would need to know where to look to get the price of a Share.

To achieve this, on the client system:

String shareName = "BP";
int hashCode = shareName.hashCode();
int serverID = hashCode % 3; //by taking the modulo we know we will only ever get 0, 1 or 2

Then, using a HashMap we could use the serverID int to lookup which server to talk to. Again, a use of HashMap.

share|improve this answer
add comment

There are so many situations where you have one piece of information (key) and want a system to give you more information based on that key.

This is the need behind the evolution and implementation of several computing structures such as databases, binary trees, hash tables, and supporting algorithms.

Hash Tables have the following features:

0 - They facilitate a quick and sometimes inexpensive way to retrieve information. They consume little CPU and if small-enough can fit in RAM. The speed is gained from the way the data location is calculated from the key, this is done in almost a linear fashion which outperforms other methods like binary search and linear search.

1 - They can store information based on a key.

2 - They are language/technology independent. They don't require special hardware or software to implement them as the majority of programming languages would be sufficient to create the necessary algorithms for them.

3 - They have friendly interface - to get data, you pass a key and to store data, you pass a key in addition to the data.

4 - The theory allows the storage and retrieval of data based on numeric as well as non-numeric key values.

Hash tables are used in memory during the processing of a program (they can be persisted to disk but that is a different topic), some usages are (not sure if all have not been already listed in other posts...):

0 - facilitation of Associative Arrays - see the post by @Dipan Mehta in this thread.

1 - Lookup values (states, provinces, etc.). You could load small amounts from database into hash tables for quick lookups (decoding an encoding of data) - This is of paramount effect in large batch jobs for Extract Load and Transform scenarios. It is also very valuable for data validation.

2 - Data Buffering. You could store frequently used data from a database in a hash table to facilitate quick access.

3 - Uniqueness Checking - You can use hash tables to ensure that no value is duplicate in a list.

4 - Keyword Recognition - In cases you want to identify if a given text has certain keywords in it or not, instead of checking the database with each value, you could use a hash table

5 - Decision tables - Large conditional flows may be stored in an array where given a condition id, you could retrieve and execute related code segments (this may be used in interpreted languages).

6 - Game programming could use Hash tables to keep track of player scores, weapons of a player, etc.

Note that a hash table is different from a hash map - See: differences-between-hashmap-and-hashtable

Hash maps have their own separate usages and properties as well.

share|improve this answer
add comment

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