Hash table applications in Data Structures Theory - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a hash table?

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

beginner

How do hash tables help in implementing a dictionary?

Hash tables allow quick lookup, insertion, and deletion of words and their meanings by using the word as a key and the meaning as the value, making dictionary operations very efficient.

intermediate

Why are hash tables useful for caching?

Hash tables store cached data with keys representing requests or queries. This allows quick access to previously computed results, improving performance by avoiding repeated calculations.

beginner

Explain how hash tables are used in counting frequencies.

Hash tables can count how often items appear by using the item as a key and increasing the value each time the item is found. This is useful in tasks like counting word occurrences in text.

intermediate

What is a common challenge when using hash tables and how is it handled?

A common challenge is collisions, where two keys hash to the same index. This is handled by methods like chaining (storing multiple items in a list at one index) or open addressing (finding another empty slot).

What does a hash function do in a hash table?

A Encrypts the data for security

B Converts a key into an index

C Sorts the data alphabetically

D Deletes duplicate entries

A hash function converts a key into an index where the value is stored in the hash table.

Which of these is NOT a typical use of hash tables?

A Storing data in sorted order

B Counting item frequencies

C Implementing caches

D Fast data lookup

Hash tables do not store data in sorted order; they focus on fast access using keys.

How do hash tables handle collisions?

A By using chaining or open addressing

B By ignoring the new data

C By deleting the old data

D By sorting the keys

Collisions are handled by chaining (storing multiple items at one index) or open addressing (finding another slot).

In a dictionary application, what is typically used as the key in a hash table?

A The page number

B The meaning

C The word

D The author name

The word is used as the key to quickly find its meaning stored as the value.

Why are hash tables preferred for caching?

A They use less memory

B They sort data by time

C They automatically update data

D They provide fast access to stored results

Hash tables allow fast access to cached data, improving performance by avoiding repeated work.

Describe three common applications of hash tables in everyday computing.

Think about how hash tables help with quick access and organizing data.

Explain what a collision is in a hash table and how it can be resolved.

Consider what happens when two items want to use the same spot.