Data Structures: Hash Table, a High-Level Overview

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.

Screen Shot 2018-01-29 at 1.23.10 PM

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!

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.