About 2 hours and 30 minutes
- 60 mins Lesson
- 30 mins Independent Practice
- 30 mins Check for Understanding
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)
- 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
- 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.
- Read through lesson slides Understanding and Using Hash Tables
- Read through lesson slides Implementing Hash Tables
- When should I use an array instead of a hash table? If your keys are sequential integers.
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
Dictfor Dictionary since you look it up by a key, just like a dictionary's have an index for each letter - Java calls is a
HashMaporHashtable - Ruby calls it a
Hash
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. You 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.
- A person is represented in a JSON string, and the person's
nameis specified. Say hello to this person.
Basics: set(), get(), print()
Challenge 1: Handle collisions with chaining
Challenge 2: Make the table larger when enough items are added to the table
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.
- Explain how a hash table uses hashing.
- What is a real-world use case for a hash table? What are the advantages?