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)
   }
}

Runtime:

O(1) for a “good” hash table, Usually what we assume for interviews

O(n) for a terrible hash table, i.e. lots of collisions

Honestly, in reality, the runtime depends on a number of other factors as well.

Topics to dive into deeper (I’ll make blog posts about later)

• Collision handling for Hash Tables
• How Hash Tables grow/shrink
• Implement a simple Hash Table
• Practice Questions!