The fundamentals of Hash tables?

I'm quite confused about the basic concepts of a Hash table. If I were to code a hash how would I even begin? What is the difference between a Hash table and just a normal array?

Basically if someone answered this question I think all my questions would be answered: If I had 100 randomly generated numbers (as keys), how would I implement a hash table and why would that be advantageous over an array?

Psuedo-code or Java would be appreciated as a learning tool...

The answers so far have helped to define hash tables and explain some theory, but I think an example may help you get a better feeling for them.

What is the difference between a hash table and just a normal array?

A hash table and an array are both structures that allow you to store and retrieve data. Both allow you to specify an index and retrieve a value associated with it. The difference, as Daniel Spiewak noted, is that the indices of an array are sequential, while those of a hash table are based on the value of the data associated with them.

Why would I use a hash table?

A hash table can provide a very efficient way to search for items in large amounts of data, particularly data that is not otherwise easily searchable. ("Large" here means ginormous, in the sense that it would take a long time to perform a sequential search).

If I were to code a hash how would I even begin?

No problem. The simplest way is to invent an arbitrary mathematical operation that you can perform on the data, that returns a number N (usually an integer). Then use that number as the index into an array of "buckets" and store your data in bucket #N. The trick is in selecting an operation that tends to place values in different buckets in a way that makes it easy for your to find them later.

Example: A large mall keeps a database of its patrons' cars and parking locations, to help shoppers remember where they parked. The database stores make, color, license plate, and parking location. On leaving the store a shopper finds his car by entering the its make and color. The database returns a (relatively short) list of license plates and parking spaces. A quick scan locates the shopper's car.

You could implement this with an SQL query:

SELECT license, location FROM cars WHERE make="$(make)" AND color="$(color)"

If the data were stored in an array, which is essentially just a list, you can imagine implementing the query by scanning an array for all matching entries.

On the other hand, imagine a hash rule:

> Add the ASCII character codes of all the letters in the make and color, divide by 100, and use the remainder as the hash value.

This rule will convert each item to a number between 0 and 99, essentially sorting the data into 100 buckets. Each time a customer needs to locate a car, you can hash the make and color to find the one bucket out of 100 that contains the information. You've immediately reduced the search by a factor of 100!

Now scale the example to huge amounts of data, say a database with millions of entries that is searched based on tens of criteria. A "good" hash function will distribute the data into buckets in a way that minimizes any additional searching, saving a significant amount of time.

First, you have to understand a what a hash function is. A hash function is a function that takes a key (for example, an string of arbritrary length) and returns a number as unique as possible. The same key must always return the same hash. A really simple string hashing function in java might look like

public int stringHash(String s) {
    int h = s.length();
    for(char c : s.toCharArray()) {
        h ^= c;
    }
    return h;
}

You can study a good hash function at http://www.azillionmonkeys.com/qed/hash.html

Now, the hash map uses this hash value to place the value into an array. Simplistic java method:

public void put(String key, Object val) {
    int hash = stringHash(s) % array.length;
    if(array[hash] == null) {
        array[hash] = new LinkedList<Entry<String, Object> >();
    }
    for(Entry e : array[hash]) {
        if(e.key.equals(key)){
            e.value = val;
            return;
        }
    }
    array[hash].add(new Entry<String, Object>(key, val));
}

(This map enforces unique keys. Not all maps do.)

It is possible for two different keys to hash to the same value, or two different hashes to map to the same array index. There exists many techniques for dealing with this. The simplest is to use a linked list (or binary tree) for each array index. If the hash function is good enough, you will never need a linear search.

Now to look up a key:

public Object get(String key) {
    int hash = stringHash(key) % array.length;
    if(array[hash] != null) {
        for(Entry e : array[hash]) {
            if(e.key.equals(key))
                return e.value;
        }
    }

    return null;
}

Hashtables are associative. This is a huge difference from arrays, which are just linear data structures. With an array, you might do something like this:

int[] arr = ...
for (int i = 0; i < arr.length; i++) {
    System.out.println(arr[i] + 1);
}

Notice how you are getting an element out of the array by specifying an exact memory offset (i). This contrasts with hashtables, which allow you to store key/value pairs, later retrieving the value based on the key:

Hashtable<String, Integer> table = new Hashtable<String, Integer>();
table.put("Daniel", 20);
table.put("Chris", 18);
table.put("Joseph", 16);

With the above table, we can make the following call:

int n = table.get("Chris");

...and be assured that n will be valued at 18.

I think this will probably answer most of your questions. The implementation of a hashtable is a fairly interesting topic, one which Wikipedia addresses passably well.

"I'm more interested in the way Hash Tables look up the key and how the key is generated."

1. Hashing transforms a key object to a number. This is called "hashing" -- it makes a hash out of the object. See Hash Function. Summing the bytes of a string, for example, is a standard hash technique. You compute the sum modulo 2³² to keep the hash to a manageable size. Hash always gives the same answer. This is O(1).

2. The number gives you a "slot" in the HashTable. Given an arbitrary key object, the hash value computes a hash value. The hash value then gives you the slot in table. Usually mod( hash, table size ). This is O(1), also.

That's the general solution. Two numeric calculations and you've gone from arbitrary object as key to arbitrary object as value. Few things can be as fast.

The transformation from object to hash value happens in one of these common ways.

1. If it's a "primitive" object of 4 bytes, then the object's native value is a number.

2. The object's address is 4 bytes, then the object's address can be used as a hash value.

3. A simple hash function (MD5, SHA1, whatever) accumulates the bytes of the object to create a 4-byte number. The advanced hashes aren't simple sums of bytes, a simple sum doesn't reflect all the original input bits fairly enough.

The slot in the hash table is mod( number, size of table ).

If that slot has the desired value, you're done. If that's not the desired value, you need to look somewhere else. There are several popular probing algorithms to look for a free spot in the table. Linear is a simple search for the next free spot. Quadratic is a non-linear hopping around looking for a free slot. A random number generator (with a fixed seed) can be used to generate a series of probes that will spread data evenly but arbitrarily.

The probing algorithms are not O(1). If the table's big enough, the odds of collision are low, and probes don't matter. If the table's too small, then collisions happen and probing happens. At that point, it becomes a matter of "tuning and tweaking" to balance probing and table size to optimize performance. Usually we just make the table bigger.

See Hash Table.

Something I didn't see specifically noted yet:

The point of using a hash table over an array is performance.

Iterating through an array would typically take anywhere from O(1) to O(x) where x is the number of items in the array. However the time to find your item will be extremely variable, expecially if we are talking about hundreds of thousands of items in the array.

A properly weighted hash table typically has an almost constant access time of just over O(1), no matter how many items are in the hash table.

You wouldn't want to use a hash table for 100 randomly generated numbers.

A good way to think about hash tables is to think about value pairs. Let's use students, and say everyone has a student ID number. In your program you store information on students (names, phone numbers, bills, etc). You want to find all of the information about a student using only basic information (name or student ID, for example).

Let's say you have 10,000 students. If you store them all in an array, then you have to loop through the entire array comparing each entry's student ID with the one you are looking for.

If, instead, you "hash" (see below) their student ID number to a position in the array, then you only have to search student's who's numbers have the same hash. Much less work to find what you wanted.

In this example, let's say student IDs are just 6 digit numbers. Our hash function could be use only the bottom 3 digits of the number as the "hash key". Thus 232145 is hashed to array location 145. So then you only need an array of 999 element (each element being a list of students).

That should be a good start for you. You should, of course, read a text book or wikipedia for this kind of info. But I assume you've already done that and are tired of reading.

Here is, in short, how a hash table works.

Imagine you have a library, full of books. If you were to store the books in an array, you would put each book on a spot on a shelf, and then when someone asked you to find a book, you'd look through all the shelves -- pretty slow. If someone said "book #12345", you could find it pretty easily, though.

Let's say instead you say, if the book title starts with 'A', it goes in row 1. If the second letter is 'B', it goes in row 1, rack 2. If the third letter is 'C', it goes in row 1, rack 2, shelf 3... and so on until you identify the book position. Then, based on the title of the book, you could know exactly where it should be.

Now, there are some problems in the simplistic "hashing" algorithm I described -- some shelves are going to be way overloaded while others stand empty, some books will be assigned to the same slot.. so the real hash functions are carefully constructed to try to avoid such problems.

But this is the basic idea.

I'll answer that part about the difference between a hash table and an array... but since I've never implemented a hashing algorithm of any import before, I'll leave that to somebody more knowledgeable :)

An array is just an ordered list of objects. The object itself doesn't really matter... what's important is that if you want to list the objects in order of insertion, it is always the same (meaning that the first element always has an index of 0).

As for a hashtable, that's indexed by keys, not order... I think that a basic search on hashing algorithms will give you a lot more insight than I can... Wikipedia has a very decent one... that determines "bucket" that the keys go into for quick retrieval on arbitrary objects used as keys.

As for advantages: If order of insertion is important, an array or some kind of ordered list is necessary. If fast look-up by arbitrary key (keyed by various hash functions) is important, then a hash table makes sense.

[This is the reply to a comment made by me.yahoo.com/a above]

That depends on your hash function. Lets suppose that your hash function hashes a word as per the length of your word, the key for chris will be 5. Similarly, key for yahoo will also be 5. Now, both values (chris and yahoo) will go under 5 (i.e. in a 'bucket' keyed by 5). This way you don't have to make an array equal to the size of your data.

The question, I believe, is answered quite clearly and in many different ways by now.

I would just like to add another perspective (which may confuse a new reader as well)

At a level of least abstraction, arrays are just contiguous block of memory. Given the starting address (startAddress), size (sizeOfElement) and the index of a single element, the address of element is computed as:

elementAddress = startAddress + sizeOfElement * index

The interesting thing to note here is that arrays can be abstracted/viewed as hash tables with index as key and the above function as a hash function which calculates the location of a value in O(1)

Hash table is a data structure that is created for quick look up.

The hash tables are not effective when the number of entries are very small.

reference

Some examples:

    import java.util.Collection;
    import java.util.Enumeration;
    import java.util.Hashtable;
    import java.util.Set;

    public class HashtableDemo {

    public static void main(String args[]) {

// Creating Hashtable for example

     Hashtable companies = new Hashtable();


// Java Hashtable example to put object into Hashtable
// put(key, value) is used to insert object into map

     companies.put("Google", "United States");
     companies.put("Nokia", "Finland");
     companies.put("Sony", "Japan");


// Java Hashtable example to get Object from Hashtable
// get(key) method is used to retrieve Objects from Hashtable

     companies.get("Google");


// Hashtable containsKey Example
// Use containsKey(Object) method to check if an Object exits as key in
// hashtable

     System.out.println("Does hashtable contains Google as key: "+companies.containsKey("Google"));


// Hashtable containsValue Example
// just like containsKey(), containsValue returns true if hashtable
// contains specified object as value

      System.out.println("Does hashtable contains Japan as value: "+companies.containsValue("Japan"));


// Hashtable enumeration Example
// hashtabl.elements() return enumeration of all hashtable values
    
      Enumeration enumeration = companies.elements();

      while (enumeration.hasMoreElements()) {
      System.out.println("hashtable values: "+enumeration.nextElement());
      }


// How to check if Hashtable is empty in Java
// use isEmpty method of hashtable to check emptiness of hashtable in
// Java

       System.out.println("Is companies hashtable empty: "+companies.isEmpty());


// How to find size of Hashtable in Java
// use hashtable.size() method to find size of hashtable in Java
     
      System.out.println("Size of hashtable in Java: " + companies.size());


// How to get all values form hashtable in Java
// you can use keySet() method to get a Set of all the keys of hashtable
// in Java

      Set hashtableKeys = companies.keySet();


// you can also get enumeration of all keys by using method keys()

      Enumeration hashtableKeysEnum = companies.keys();


// How to get all keys from hashtable in Java
// There are two ways to get all values form hashtalbe first by using
// Enumeration and second getting values ad Collection

      Enumeration hashtableValuesEnum = companies.elements();


      Collection hashtableValues = companies.values();


// Hashtable clear example
// by using clear() we can reuse an existing hashtable, it clears all
// mappings.

       companies.clear();
      }
     }

Output:

Does hashtable contains Google as key: true

Does hashtable contains Japan as value: true

hashtable values: Finland

hashtable values: United States

hashtable values: Japan

Is companies hashtable empty: false

Size of hashtable in Java: 3