HashTable

Hash Table implementation

Pinterest LinkedIn Tumblr

A hash table is a data structure. It uses to store keys and values. The hash table does not allow to duplicate the keys. It allows to lookup the value based on the key.

Hash tables are used frequently in the database index, cache. The image shows the dictionary which build on top of the hash table. Hash collisions are practically unavoidable when hashing a random subset of a large set of possible keys. The following collision resolution strategy used for resolving the key collision.

  • Separate chaining
  • Open addressing
  • Linear probing
  • Double hashing
  • Hopscotch hashing
  • Robin Hood hashing

Hashtable section explains how to implement the Hashtable and various applications related with Hash operation.

A hash table is a data structure used to store keys and values. Keys cannot duplicate and values can duplicate. Hash table value lookup by unique key.

The hash table uses key and value format to store the data. If the same key position used by more than one value, name collision occurs. Open addressing, chaining and perfect hashing are the few mechanism to avoid the hashing collision.

Write a program to implement the hash table?

Algorithm Explanation

Hashtable is a container to store the key and value pair. It uses buckets to store the records. The hash table keys calculated based on the hashing function.
The hash table uses linked list when the key collision happens. If the key collision happens, the values stored in linked list.
The hash table uses many techniques to avoid the name collision (Separate chaining, open addressing, robin hood hashing and 2 choice hashing).
A collision occurs when two different keys hash to the same value.

Source Code

package com.dsacode.DataStructre.hashtable;
 
class Item {
    public String key;
    public Object element;
 
    public Item(String key, Object element) {
        this.key = key;
        this.element = element;
    }
 
    public String toString() {
        String s = " < Item ( ";
        s += this.key + "," + this.element + ")>";
        return s;
    }
}
 
public class HashTableImpl {
    private Item[] data;
    private int capacity;
    private int size;
    private static final Item AVAILABLE = new Item("Available", null);
 
    public HashTableImpl(int capacity) {
        this.capacity = capacity;
        data = new Item[capacity];
        for (int i = 0; i < data.length; i++) {
 
            data[i] = AVAILABLE;
        }
        size = 0;
    }
 
    public int size() {
        return size;
    }
 
    public int hashThis(String key) {
        return key.hashCode() % capacity;
    }
 
    public Object get(String key) {
        int hash = hashThis(key);
        while (data[hash] != AVAILABLE && data[hash].key != key) {
            hash = (hash + 1) % capacity;
        }
        return data[hash].element;
    }
 
    public void put(String key, Object element) {
        if (key != null) {
            size++;
            int hash = hashThis(key);
            while (data[hash] != AVAILABLE && data[hash].key != key) {
                hash = (hash + 1) % capacity;
            }
            data[hash] = new Item(key, element);
        }
    }
 
    public Object remove(String key) {
        throw new UnsupportedOperationException("Can't remove");
    }
 
    public String toString() {
        String s = " < HashTable[";
        for (int i = 0; i < this.capacity; i++) {
            if (data[i].element != null) {
                s += data[i].toString();
                if (i < this.size - 1) {
                    s += ",";
                }
            }
        }
        s += "]>";
        return s;
    }
  
     
    public static void main(String[] args) {
        HashTableImpl ht = new HashTableImpl(10);
        ht.put("1", "aaa");
        ht.put("2", "bbb");
        ht.put("3", "ccc");
        System.out.println(ht.toString());
    }
 
     
}

Output

<hashtable[<item(2,bbb)>,<item(3,ccc)>,<item(1,aaa)>]>
</item(1,aaa)></item(3,ccc)></hashtable[<item(2,bbb)>

Source Explanation

Each Item contains the value and key pair. The toString method uses to print the element and key value.
The hash table implementation uses an array of items, capacity and size to store the data.
The hash this operation returns the hash code. The get takes the key as input and returns the corresponding value. The put operation put the key and value object to the hash tables
The string method uses to print the string representation.

Complexity

OperationsBest CaseAverage Caseworst Case
SearchO(1)O(n)
InsertionO(1)O(n)
DeletionO(1)O(n)

Real Applications

  1. Array of key-value pairs
  2. Sparse arrays
  3. Internet routers tables
  4. Driver license record management
  5. Dictionaries
  6. Compiler symbol tables
  7. Telephone book databases
  8. Internet search engines
  9. Associative arrays
  10. Database indexing
  11. Caches
  12. Sets
  13. Object representation
  14. Unique data representation
  15. String interning

Reference

  1. http://visualgo.net/hashtable.html
  2. https://www.cs.auckland.ac.nz/software/AlgAnim/hash_tables.html
  3. https://en.wikipedia.org/wiki/Hash_table
  4. https://www.andrew.cmu.edu/course/15-310/applications/ln/hashing-review.html

Write A Comment