In order to get ready for a technical interview, I’ll post some of the topics related to my blog. The content that I got is all from HackerRank’s Cracking The Coding Interview Tutorial with Gayle Laakmann McDowell YouTube Video which is linked. Their videos are extremely helpful and everything I posted down below is my notes on it.

What is a hash table?

A hash table basically maps key to values.

Given a key associate a value for it for a quick lookup.

The basic concept is that each key, which in this case is represented as a string, is mapped to a hashcode to an index.

We jump from a string to an index in an array through hashcode.

int hashCode(String s){
// Some implementations
}

String → Hashcode → Index

Collisions

There will be problems that we can run into when using hashtables. The number one is that there will be collisions.

Collisions happen when 2 different keys can have the same hash codes but the same index.

One solution to this is “Chaining,” where you put the values in linked lists.

Here’s a sample code:

class Hashtable {
Linked List[] data // array of Linked Lists of values
   boolean put(String key, Person value){
      int hashcode = getHashCode(key)
      int index = convertToIndex(hashCode)
      LinkedList list = data[index]
      list.insert(key,value)
   }
}