Hash Tables have three major components.

  1. The table itself (aka, an array)
  2. Each element in the array (LinkedList)
  3. A Hash function – which takes some input and outputs an integer value

Hash Table’s are arrays that operate just like any other arrays. However, the index’s are calculated through a hash function that, when given input data, spits out an array location at which to store / access the data. If that particular array location already contains an object, we store our data in the next LinkedList value in that array location.

0 1 2 3
element 1 element 2 element 3 element 4
element 5

Alright, so say we wanted to add element 5 to this hash table. We would take the hash function, and input element 5: hash(element_5), which would output 1. When we probe over index 1, we find that element 2 is already stored there. So we set element 5 equal to element_2.next (remember, its a LinkedList) and we’re done!

Something you may have noticed here is that arrays have a limited size. Let’s say our array has a size of 10 (a very poor hash table). How do we make sure that the value spit out by the hash function sits within those bounds? Simple, we mod the values by 10.101 % 10 = 1145 % 10 = 5And so forth.Now that you’ve got a general idea of how hash tables work, let’s start to write one!First thing’s first – we need a LinkedList.

Let’s code one:

 

class Link{ 
    Link next; 
    String data; 

    public Link(String data){ 
        this.data = data; 
    } 

    public void appendToTail(String data){ 
 
        Link end = new Link(data); 
        Link n = this; 
        while(n.next != null){ 

            n = n.next; 
        } 
        n.next = end; 
    } 
}

These Links are going to be what our array’s are going to store in each cell. As you can see, one Link can point to another, allowing us to ‘chain’ together items in our hash table at each index. This is known as chaining.

Let’s write up out HashTable class:

class HashTable{ 
    Link [] hashtable = new Link[10]; 

    // we're going to initialize out data values with 
    // #empty# so that we know nothing is currently stored 
    // in each section 
    public HashTable(){ 

        for(int i = 0; i < hashtable.length; i++){ 
            
            hashtable[i].data = "#empty#"; 
        } 
    } 

    public static int hash(String data){ 

        int hash = 0; 

        for(int i = 0; i < data.length(); i ++){ 

            // add the integer value of each character 
            // to our hash value hash += (int) data.charAt(i); 

        } 

        // mod the hash value by the number of elements 
        // inside our hash table array 
        return (hash % hashtable.length); 
    } 

    public void addItem(String data){ 

        // calculate the index value 
        int index = hash(data); 

        // while the value stored isn't empty 
        // set the index equal to an available slot 
        while(!hashtable[index].data.equals("empty")){ 

            map[index] = map[index].next; 

        } 

        // store the value in that available slot 
        map[index].value = data; 
    } 

    // get's the value stored in the hash table by index 
    String [] getValue(String data){ 

        int index = hash(data); 
        String[] values = new String[10]; 
        int i = 0; 

        while(hashtable[index].next.data.equals("empty")){ 

            values[i] = hashtable[index].data; 
            i++ 
        } 
        return values; 
     } 
} 

And that’s all there is to Hash Tables! Essentially, they’re a key-value store that uses a hash function for quick lookup times (typically O(1)) because they just jump to keys directly in one fell swoop. However, if a chain exists at that index, lookup times by be longer – but typically we don’t care too much about that assuming the table is large enough and the hash function is good enough.

Advertisements