Take the 2-minute tour ×

I am writing a program that will hash words from a document along with their frequency of use and line numbers. I thought that I had finished it when I was told that you have to create a hash table from scratch. I do not know where to begin. Any suggestions as to where and how to start would be appreciated.

share|improve this question

closed as too localized by home, Hovercraft Full Of Eels, user7116, George Cummins, Graviton Oct 28 '11 at 2:06


Is this a homework assignment? –  ewok Oct 27 '11 at 16:58
I'd start here: en.wikipedia.org/wiki/Hashtable –  home Oct 27 '11 at 16:58
Start with an array and a hash function. –  larsmans Oct 27 '11 at 16:58

4 Answers 4

up vote 6 down vote accepted

A hash table is an important and fundamental data structure. You can read more about it at Wikipedia's Hash table article. Fortunately, they are fairly easy to implement.

Basically a hash table is a data structure that takes a key and returns or stores a value for that key.

At their core, they are usually implemented using an array, which we shall call arr such that key-value pairs are stored at arr[key.hashCode()%arr.length]. Notice that since your array is not of infinite length, and that hashCode is not guaranteed to produce unique values you will eventually end up with keys that map to the same index of the array. This is called a collision.

One way of resolving these collisions is to store a linked list for each member of arr. Then the definition of arr would look like this

LinkedList<Object> arr[];

All objects which map to arr[key.hashCode()%arr.length] will be added to the list at that position. When you want to retrieve an object from the hashtable, jump to the linked list found at arr[key.hashCode()%arr.length] and iterate through each member of the linked list until you find a key-value pair where the keys are .equals.

A good hash table implementation might do things like resize arr once it gets too full.

share|improve this answer

To create a hashtable, You need to keep in mind the structure of what it is that you want to build. A hashtable has 2 elements, a key set and a value set. Think about how you would represent these and how you would make sure that the keys always map to the appropriate value.

Next, think about your hash function. Remember that There is no "correct" hash function. You just need to come up with one that works well for you.

Once these two things are taken care of, the rest is simple. Writing methods to work on the two sets are basically just a matter of cleverly using the hash function.

Good Luck!

Extra hint: Remember that the value set of the hashtable is not necessarily the same size as the key set. Remember the concept of buckets. That is very important.

share|improve this answer

Start with studying the HashMap Java class. Notice that it is an extension of the AbstractMap, and that AbstractMap provides a lot of basic capabilities you want. Not all of them, however. The most important method, put(), always throws UnsupportedOperationException. That is by design. To make it a MyHashMap, you need to override this method. Inside of put() will be where you will do all your hashy stuff referred to in Jack's great answer.

public class MyHashMap<K,V> extends AbstractMap<K,V> implements Map<K,V> {

  // your implementation goes in here, including the override of put()


By doing it this way, you can test your implementation more easily. Run a series of tests in which you provide a HashMap as a parameter. Then run the same code with an object of your MyHashMap. Since both are implementations of Map, you can substitute one for the other without changing any code, and you'll be confident about what your tests are telling you.

share|improve this answer
That clears up quite a bit, thank you! –  Bill Oct 27 '11 at 17:31

Just use an array for your table. You'll need a hash function, and a load factor. The load factor will determine when you resize the table to keep it efficient. A simple hash function for a string is to sum up each character's ascii value multiplied by 2^(character index) and mod that sum by the table length. e.g.

static int hash(String s) {
    int len = 30;
    int sum = 0;
        sum += ((int)s.charAt(i)) * (1<<i);
    return sum%len;

You could use String.hashCode too. To resolve collisions the simplest method to use is linear probing, but clustering will occur quickly. You can implement double hashing for better performance.

share|improve this answer
thank you very much –  Bill Oct 27 '11 at 17:31
