Hash table (Java)

From LiteratePrograms

Other implementations: C | Java

This is an implementation of a hash table. For all practical purposes, you should use Java's HashMap class instead.

Contents 1 Description 2 Structures and functions 2.1 Initialisation 2.2 Adding a new element 2.3 Removing an element 2.4 Searching 2.5 Resizing 3 Test

Description

This implementation uses generics to allow keys and values to be any class type. The size is specified when creating the hash table. The hash function used is the default hashCode() method in Java. To handle hash collisions, each entry in the table is a reference to a linked list, so that multiple values with the same hash can be stored.

Automatic resizing is not included in this implementation. A function for manual resizing is provided.

Structures and functions

Hashtbl is the class for the hash table. It contains all information necessary to manipulate and look up the elements. All hash table functions are methods of Hashtbl.

<<Hashtbl class>>=
public class Hashtbl<K,V> {
    private Hashnode<K,V>[] nodes;
    Hashtbl methods
    main method
}

The nodes member of Hashtbl is an array of references to the first element of a linked list. This element is represented by the class Hashnode:

<<Hashnode class>>=
class Hashnode<K,V> {
    K key;
    V data;
    Hashnode<K,V> next;
    public Hashnode(K k, V v, Hashnode<K,V> n)
    { key = k; data = v; next = n; }
}

These are the functions used to manipulate and look up the hash table:

<<Hashtbl methods>>=
Hashtbl constructor
get index method
insert method
remove method
get method
resize method

<<Hashtbl.java>>=
Hashnode class
Hashtbl class

Initialisation

The constructor of Hashtbl sets up the initial structure of the hash table. The user specified size will be allocated and elements are automatically initialized to null.

<<Hashtbl constructor>>=
@SuppressWarnings("unchecked")
public Hashtbl(int size)
{
    nodes = new Hashnode[size];
}

(Due to issues with how arrays were designed, we cannot create an array of a generic type, so we perform an unchecked conversion, and then suppress the warning.)

Adding a new element

We will add a method for obtaining the index into our table for a particular hash key. To make sure the hash value is not bigger than the size of the table, the result of the user provided hash function is used modulo the length of the table. We need the index to be non-negative, but the modulus operator (%) will return a negative number if the left operand (the hash value) is negative, so we have to test for it and make it non-negative.

<<get index method>>=
private int getIndex(K key)
{
    int hash = key.hashCode() % nodes.length;
    if (hash < 0)
        hash += nodes.length;
    return hash;
}
<<insert method>>=
public V insert(K key, V data)
{
    int hash = getIndex(key);

We have to search the linked list to see if data with the same key has been inserted before, in which case we just replace the data member of the Hashnode object.

<<insert method>>=
//    System.err.printf("insert() key=%s, hash=%d, data=%s\n", key, hash, data);
    for (Hashnode<K,V> node = nodes[hash]; node != null; node = node.next) {
        if (key.equals(node.key)) {
            V oldData = node.data;
            node.data = data;
            return oldData;
        }
    }

If we didn't find the key, we insert a new element at the start of the linked list.

<<insert method>>=
    Hashnode<K,V> node = new Hashnode<K,V>(key, data, nodes[hash]);
    nodes[hash] = node;

We return the previous value associated with the key, or null if there was no such key.

<<insert method>>=
    return null;
}

Removing an element

To remove an element from the hash table, we just search for it in the linked list for that hash value, and remove it if it is found. We return true if it was found; ff it was not found, we return false.

<<remove method>>=
public boolean remove(K key)
{
    int hash = getIndex(key);
    Hashnode<K,V> prevnode = null;
    for (Hashnode<K,V> node = nodes[hash]; node != null; node = node.next) {
        if (key.equals(node.key)) {
            if (prevnode != null)
                prevnode.next = node.next;
            else
                nodes[hash] = node.next;
            return true;
        }
        prevnode = node;
    }
    return false;
}

Searching

Searching for an element is easy. We just search through the linked list for the corresponding hash value. null is returned if we didn't find it.

<<get method>>=
public V get(K key)
{
    int hash = getIndex(key);
//    System.err.printf("get() key=%s, hash=%d\n", key, hash);
    for (Hashnode<K,V> node = nodes[hash]; node != null; node = node.next) {
        if (key.equals(node.key))
            return node.data;
    }
    return null;
}

Resizing

The number of elements in a hash table is not always known when creating the table. If the number of elements grows too large, it will seriously reduce the performance of most hash table operations. If the number of elements are reduced, the hash table will waste memory. That is why we provide a function for resizing the table.

Resizing a hash table is not as easy as a copying to a larger array. All hash values have to be recalculated and each element must be inserted into their new position.

We create a temporary Hashtbl object (newtbl) to be used while building the new hashes. This allows us to reuse insert() and remove() methods, when moving the elements to the new table. After that, we can just copy the elements from newtbl to the current table.

<<resize method>>=
public void resize(int size)
{
    Hashtbl<K,V> newtbl = new Hashtbl<K,V>(size);
    for (Hashnode<K,V> node : nodes) {
        for ( ; node != null; node = node.next) {
            newtbl.insert(node.key, node.data);
            remove(node.key);
        }
    }
    nodes = newtbl.nodes;
}

Test

To test that it works, we create a hash table containing some European countries mapped to their respective capitals.

<<main method>>=
public static void main(String[] args)
{
    Hashtbl<String,String> hashtbl = new Hashtbl<String,String>(16);
    hashtbl.insert("France", "Paris");
    hashtbl.insert("England", "London");
    hashtbl.insert("Sweden", "Stockholm");
    hashtbl.insert("Germany", "Berlin");
    hashtbl.insert("Norway", "Oslo");
    hashtbl.insert("Italy", "Rome");
    hashtbl.insert("Spain", "Madrid");
    hashtbl.insert("Estonia", "Tallinn");
    hashtbl.insert("Netherlands", "Amsterdam");
    hashtbl.insert("Ireland", "Dublin");
    System.out.println("After insert:");
    String italy = hashtbl.get("Italy");
    System.out.println("Italy: " + (italy != null ? italy : "-"));
    String spain = hashtbl.get("Spain");
    System.out.println("Spain: " + (spain != null ? spain : "-"));

We use remove() on the "Spain" element, and use get() to ensure it has actually been removed.

<<main method>>=
    hashtbl.remove("Spain");
    System.out.println("After remove:");
    spain = hashtbl.get("Spain");
    System.out.println("Spain: " + (spain != null ? spain : "-"));

To test resizing, we call resize(), and then get() to see if the hash table still works.

<<main method>>=
    hashtbl.resize(8);
    System.out.println("After resize:");
    italy = hashtbl.get("Italy");
    System.out.println("Italy: " + (italy != null ? italy : "-"));
}

The output is, as expected:

After insert:
Italy: Rome
Spain: Madrid
After remove:
Spain: -
After resize:
Italy: Rome

Download code