Understanding the Hash Table

In Computer Science, a Hash Table is a Data Structure. There are many data structures available such as Stack, Queue, Linked List, Set. Hash Table is another one which stores data in an associative manner.

Hash Table

Lets say we have an array of users. We will implement the hash table using array. The users array has a fixed size of 10. We want to insert user into the users array. But wait we can’t just insert directly into the array, first we need to make a hash function which will give us an index based on user. For example, if the user is “John” a simple hash function can be,

function generateHash(table_size, user) {
  let index
  let user_length = user.length

  index = user_length % table_size
  return index
}

generateHash(10, 'john')
generateHash(10, 'david')

The generateHash function took table_size & user, inside the function it returned the user_length % table_size. So for input 10 & “john” the output is (4 % 10) which is 4 and for input 10 & “david” the output is (5 % 10) which is 5.

Note that the generateHash is not very good hashing example it is just for understanding purpose and remember for the same input the hash function should return the same output every time.

As we get the indexes 4 and 5 from generateHash function, we can add the items in the indexes 4 and 5. The time complexity for this is O(1).

What if we want to add another(same length of “john”) user “mark”? When you call the generateHash function for both “john” and “mark”, the output is 4, same output for both input. This is called Collision.

When input grows big and the length of array is fixed there is a possibility of collision. As a result of that collision “mark” will be attached itself at the end of “john”.

Now inserting is finished. What about search? Suppose we need to search “david” in our hash table. We just pass the item(“david”) into generateHash function which will return the index, we can get this item by accessing that index in our Hash Table. So the time complexity is O(1) or constant amount of complexity.

Same way we can perform the delete operation. Just pass the item(we need to delete) into the generateHash, then we get the index and by accessing this index we can perform the delete operation. So for deleting an item the time complexity is O(1).

The average time complexity for Hash Tables are O(1), but for worst case scenario the time complexity is O(n). Why O(n)? It is because, when too many elements were hashed into the same key, we need to iterate everything from 0 to n-1 if we want to perform a search or delete operation. For example, if we want to search “mark”, we need to go index 4 and iterate from 0 to n-1.

So the biggest advantage of Hash Table is Complexity. We can perform operation like insert, search, delete in O(1).