HashMap Implementation from Scratch in DSA C - 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 compute an index where the value is 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 to quickly find where the value is stored without searching the whole structure.

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 index in the array holds a linked list of key-value pairs that share the same index.

beginner

What is the average time complexity for searching a value in a well-implemented HashMap?

The average time complexity is O(1), meaning it takes constant time to find a value using its key.

What does a hash function do in a HashMap?

A Converts a key into an index

B Sorts the keys alphabetically

C Stores values in a linked list

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 the HashMap is empty

B When two keys have the same value

C When a key is not found

D When two keys produce the same index

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

Which method can handle collisions in a HashMap?

A Chaining with linked lists

B Binary search

C Sorting keys

D Using arrays only

Chaining uses linked lists at each index to store multiple key-value pairs that collide.

What is the average time complexity to find a value in a HashMap?

A O(n)

B O(log n)

C O(1)

D O(n log n)

A well-implemented HashMap allows constant time O(1) lookup on average.

In a HashMap, what data structure is commonly used to store multiple values at the same index due to collisions?

A Array

B Linked list

C Stack

D Queue

Linked lists are commonly used to store multiple key-value pairs at the same index in chaining.

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 efficiency when finding values.