Hash Table

tejender7
Sep 12, 2022
3 min read

Updated: Feb 2, 2023

In computing, a hash table, also known as hash map, is a data structure that implements an associative array or dictionary. It is an abstract data type that maps keys to values.

Hash Function

A hash table uses a hash function to compute an index, also called a hash value, into an array of lists, from which the desired value can be found. During lookup, the key is hashed and the resulting hash indicates where the corresponding value is stored.

Ideally, the hash function will assign each key to a unique list, but most hash table designs employ an imperfect hash function, which might cause hash collisions where the hash function generates the same index for more than one key. Such collisions are typically accommodated in some way.

Let's take an example,

We have an empty hash table and we add a new value "Ronaldo" with key 3.

In this example our hash function simply divides the key by 7 and remainder is the hash value. For our key 3, the remainder is 3. Hence the key value pair is added to the list at index 3.

Now we add another value "Messi" to the table with key 30.

This time, key = 30. hash value = 30 % 7 = 2. Key value pair are added to list at index 2.

Now let's add another value "Xavi" with key 16.

This time key = 16. hash value = 16 % 7 = 2. Collision! since there is already a value "Messi" at index 2. So we add it to the list. Now the list at index 2 has 2 key value pairs - "Messi",30 and "Xavi",16. If we add another value "Iniesta" with an existing key (e.g. key = 16). The value for the key 16 will be overridden with new value.

Code for put operation:

put(key, value){
  const hashValue = this.hash(key);
  const linkedList = this.lists[hashValue];
  let keyExists = false;
  let currentNode = linkedList.start;
  while(currentNode!==null){
    if(currentNode.item.key === key){
      //override existing value
      currentNode.item.value = value;
      keyExists = true;
      break;
    } 
    currentNode = currentNode.next;
  }
  if(!keyExists){
    // add new key and value
    this.keys.push(key);
    linkedList.append({key, value});
  }
}

Delete

In delete operation we provide the key we want to delete from the table.

delete(key) {
  const hashValue = this.hash(key);
  const linkedList = this.lists[hashValue];
  let currentNode = linkedList.start;
  let previousNode = currentNode;
  while(currentNode!==null){
    if(currentNode.item.key === key){
      this.keys.splice(this.keys.indexOf(key), 1);
      if(currentNode === linkedList.start){
        linkedList.start = currentNode.next;
      }
      else {
        previousNode.next = currentNode.next;
      }
      return true;
    } 
    previousNode = currentNode;
    currentNode = currentNode.next;
  }
  return false;
}

Get

In get operation we provide the key to fetch the value from the hash table.

get(key){
  const hashValue = this.hash(key);
  const linkedList = this.lists[hashValue];
  let currentNode = linkedList.start;
  while(currentNode!==null){
    if(currentNode.item.key === key){
      return currentNode.item.value;
    } 
    currentNode = currentNode.next;
  }
  return null;
}

HasKey

In haskey operation we check if a key already exists in the hash table.

hasKey(key){
  const hashValue = this.hash(key);
  const linkedList = this.lists[hashValue];
  let currentNode = linkedList.start;
  while(currentNode!==null){
    if(currentNode.item.key === key){
      return true;
    } 
    currentNode = currentNode.next;
  }
  return false;
}

Practical Application - File System

The hashing is used for the linking of the file name to the path of the file. When you interact with a file system as a user, you see the file name, maybe the path to the file. But to actually store the correspondence between the file name and path, and the physical location of that file on the disk, the System uses a map, and that map is usually implemented as a hash table.