Hash Tables

Projected Time

About 2 hours and 30 minutes

60 mins Lesson
30 mins Independent Practice
30 mins Check for Understanding

Prerequisites

Motivation

Hash tables are one of the most frequently used data structures. You’ll use them in your code a lot, so knowing how and when to use hash tables is important.

Knowing how hash tables work will give you a deeper understanding of why hash tables are used and what they’re good for. Hash tables are also often used in the solution to interview questions.

Uses of Hashing:

Authentication - Cryptographic hash functions let you log in to a system without storing your password anywhere vulnerable.
Search - Hashing is useful for indexing large storage spaces, so that you can look things up in them without reading their entire contents every time. Developers usually do the indexing of big data sets to reduce the time of processing operations over them.
Programming languages - Hash tables are a convenient way to implement the mechanism that connects a variable’s name to its memory location. (quora.com)

Objectives

Understand basic hashing algorithms
Know the runtime of hash table operations
Be able to identify problems where hash tables could be used
Be able to write code that uses hash tables to solve problems
Understand how hash tables are implemented and how this implementation leads to the runtime properties

Specific Things to Learn

A hash table is used to store key-value pairs or tuples.
Why is this called a hash table? The hash of the key determines where the value is stored.
All objects in JavaScript are hash tables.
Look-up in a hash table is on average O(1). Worst case look-up is O(n).
Using different hashing algorithms on the keys will affect the hash table’s performance.

Materials

Lesson

Read through lesson slides Understanding and Using Hash Tables
Read through lesson slides Implementing Hash Tables

Common Mistakes / Misconceptions

When should I use an array instead of a hash table? If your keys are sequential integers.

Preamble

Languages call this type of data structure by many names:

ES2015 JS calls it a Map but historically, since all Objects allow lookup by property name, folks just used plain Object
Python calls it a Dict for Dictionary since you look it up by a key, just like a dictionary’s have an index for each letter
Java calls is a HashMap or Hashtable
Ruby calls it a Hash

Guided Practice

Let’s understand how to make hash maps using JavaScript.

How to implement hash table in javascript
Here is the link for the video on how to make hash tables using JavaScripts.
The another link for what hash tables are and how to implement them is Basics of Hash Tables. It contains the code for how different types of hashing can be done by coding in JS. The apprentices should be able to code different type of hashtables like linear probing, quadratic probing etc. They can start tutorial where coding begins provided that they know the basics of hashing.

Independent Practice

Coding questions that use hash tables

A person is represented in a JSON string, and the person’s name is specified. Say hello to this person.

Implement a hash table

Basics: set(), get(), print() Challenge 1: Handle collisions with chaining Challenge 2: Make the table larger when enough items are added to the table

Challenge

Compare implementations of bucket collisions with a peer. Brainstorm different data structures one can use for implementing buckets. Code review others’ hash table implementations: Are clear parameter and method names used? Is the code DRY? Compare hashing algorithm choices with a peer.

Check for Understanding

Explain how a hash table uses hashing.
What is a real-world use case for a hash table? What are the advantages?