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.
In many contexts, the terms "hash map" and "hash table" are used interchangeably to refer to the same concept. The distinctions often come from specific language implementations rather than fundamental conceptual differences.:
- 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
Hashing, hash maps, and hash tables are fundamental concepts in computer science that are often used interchangeably, but they have distinct meanings and applications. Understanding these differences is crucial for efficient data structure selection and algorithm design.
- Hashing is the process of converting data into a fixed-size value using a hash function.
- Hash Maps and Hash Tables are data structures that use hash functions to map keys to values, providing efficient lookup, insertion, and deletion operations.
- The terms "hash map" and "hash table" are often used interchangeably, with differences typically coming from specific language implementations rather than fundamental concepts.
- Both hash maps and hash tables must handle collisions when different keys hash to the same index.
- These data structures offer O(1) average-case time complexity for basic operations, making them extremely efficient for many applications.
Hash Tables are data structures that use a hash function to map keys to values, similar to hash maps. The term is often used interchangeably with hash map, but there can be implementation differences.
Key characteristics of hash tables:
- Store key-value pairs
- Use hashing to map keys to array indices
- Provide O(1) average time complexity for basic operations
- Must handle collisions through techniques like chaining or open addressing
- In some languages (like C#), Hashtable is a specific implementation
Hash Maps are data structures that implement an associative array abstract data type, a structure that can map keys to values using a hash function to compute an index into an array of buckets or slots.
Key characteristics of hash maps:
- Store key-value pairs
- Use hashing to convert keys into array indices
- Provide average O(1) time complexity for search, insert, and delete operations
- Often implemented as a dynamic array of linked lists or other data structures
- In some languages (like Java), HashMap is a specific implementation
Hashing is a process or function that converts an input of any size into a fixed-size value, typically a string of characters or a number. The output is called a hash value, hash code, or simply a hash.
Key characteristics of hashing:
- Converts data of arbitrary size to fixed-size values
- Should be deterministic (same input always produces same output)
- Ideally minimizes collisions (different inputs producing same output)
- Used in cryptography, data retrieval, and data structures
Collisions occur when two different keys hash to the same index. There are several strategies to handle collisions:
- Database Indexing: Hash tables are used to create indexes for database systems, allowing for quick data retrieval.
- Caching: Web browsers and web servers use hash tables to implement caches for faster content delivery.
- Symbol Tables: Compilers and interpreters use hash tables to keep track of variables, functions, and their attributes.
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?