HashMap Implementation from Scratch in DSA Python - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a HashMap?

A HashMap is a data structure that stores key-value pairs. It uses a hash function to convert keys into an index where values are stored, allowing fast data retrieval.

beginner

Why do we use a hash function in a HashMap?

A hash function converts a key into an index in an array. This helps quickly find where the value for that key is stored, making lookups fast.

intermediate

What is a collision in a HashMap?

A collision happens when two different keys produce the same index from the hash function. We need a way to handle collisions to store both values correctly.

intermediate

Name one common method to handle collisions in a HashMap.

One common method is chaining, where each array index holds a list of key-value pairs. If multiple keys map to the same index, they are stored in that list.

intermediate

What is the average time complexity for get and put operations in a well-implemented HashMap?

The average time complexity is O(1), meaning it takes constant time to get or put a value, thanks to direct indexing using the hash function.

What does a hash function do in a HashMap?

A Sorts the keys alphabetically

B Stores the value directly

C Converts a key into an index

D Deletes duplicate keys

A hash function converts a key into an index to store or find the value quickly.

What is a collision in a HashMap?

A When two keys have the same value

B When two keys map to the same index

C When a key is missing

D When the HashMap is empty

A collision happens when two different keys produce the same index from the hash function.

Which method can handle collisions by storing multiple key-value pairs at the same index?

A Hashing

B Sorting

C Binary Search

D Chaining

Chaining stores multiple key-value pairs in a list at the same index to handle collisions.

What is the average time complexity for searching a key in a good HashMap?

A O(1)

B O(log n)

C O(n log n)

D O(n)

A well-implemented HashMap provides average O(1) time for searching keys.

In a HashMap, what happens if two keys produce the same index and chaining is not used?

A One value overwrites the other

B Both values are stored separately

C The HashMap resizes automatically

D The keys are merged

Without collision handling like chaining, one value overwrites the other at the same index.

Explain how a HashMap stores and retrieves data using a hash function and handles collisions.

Think about how keys become positions and what happens if two keys want the same spot.

Describe the advantages of using a HashMap compared to a simple list for storing key-value pairs.

Focus on speed and how data is found quickly.