hash-tables.md

Hash Tables

Projected Time

About 2 hours and 30 minutes

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

Prerequisites

• JavaScript prototypal inheritance
• Runtime complexity

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 Teach

• 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

• Understanding and Using Hash Tables Slides
• Implementing Hash Tables Slides

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.

• Hash Tables and Hash Maps are not the same thing!

• hashmap implementation

Guided Practice

Let's understand how to make hash tables and 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: put(), get(), hash(), 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

• What is the difference between a hash map and a hash table? The two terms are often used interchangeably.
• Explain how a hash table uses hashing.
• What is a real-world use case for a hash table? What are the advantages?

Supplemental Materials

• How to implement simple hash table?
• Difference Between HashMap And HashTable
• Hash Tables in JavaScript
• Objects and Hash Tables in JavaScript
• Javascript implementation of Java's String.hashCode() method