# 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.

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!

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