Hash Table Concept and Hash Functions in DSA C - 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

Why do collisions happen in a hash table?

Collisions happen when two different keys produce the same index from the hash function. This means both values want to be stored in the same place.

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 hash to the same index, they are stored in the list at that index.

advanced

What properties make a good hash function?

A good hash function distributes keys evenly across the table, is fast to compute, and minimizes collisions.

What does a hash function output in a hash table?

A The original key

B An index to store the value

C The value associated with the key

D A random number

The hash function outputs an index where the value is stored or retrieved.

What is a collision in a hash table?

A When a key is not found

B When two keys have the same value

C When two keys produce the same index

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 Chaining

B Open addressing

C Linear search

D Sorting

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

Why should a hash function distribute keys evenly?

A To reduce collisions and improve speed

B To make the table smaller

C To store keys in order

D To use less memory

Even distribution reduces collisions and makes data retrieval faster.

What is stored in a hash table?

A Only keys

B Only values

C Indexes only

D Key-value pairs

Hash tables store key-value pairs for fast lookup.

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

Think about how a key becomes a place to find the value.

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

Imagine two people trying to sit in the same chair.