Hash Table Concept and Hash Functions in DSA Python - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a hash table?

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

beginner

What is the role of a hash function in a hash table?

A hash function takes a key and returns an integer index. This index tells where to store or find the value in the hash table.

intermediate

What is a collision in a hash table?

A collision happens when two different keys produce the same index from the hash function. The hash table must handle collisions to store both values correctly.

intermediate

Name one common method to handle collisions in hash tables.

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

intermediate

Why should a hash function distribute keys uniformly?

Uniform distribution helps avoid many keys clustering at the same index, which keeps data retrieval fast and efficient.

What does a hash function do in a hash table?

A Converts a key into an index

B Sorts the keys alphabetically

C Stores values directly

D Deletes keys from the table

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

What is a collision in a hash table?

A When two keys produce the same index

B When a key is missing

C When two keys have the same value

D When the table is empty

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

Which method stores multiple key-value pairs at the same index to handle collisions?

A Linear probing

B Sorting

C Chaining

D Rehashing

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

Why is uniform distribution important in a hash function?

A To reduce memory usage

B To make the table smaller

C To speed up sorting

D To avoid clustering of keys at the same index

Uniform distribution avoids many keys clustering at the same index, keeping retrieval fast.

What type of data structure is a hash table?

A A tree structure

B A key-value store

C A list of values

D A queue

A hash table stores data as key-value pairs for fast access.

Explain how a hash table uses a hash function to store and retrieve data.

Think about how a key becomes a position in the table.

Describe what a collision is in a hash table and one way to handle it.

Imagine two friends trying to sit on the same chair.