Data structures hash tables and collisions study guide

Hash Table

A data structure that stores key-value pairs, enabling fast data retrieval based on unique keys.

Key

A unique identifier that maps to a specific value in a hash table.

Value

The data associated with a key in a hash table, which can be of any data type.

Hash Function

A function that converts a key into an index for the hash table, ideally distributing keys uniformly.

Load Factor

The ratio of the number of entries to the number of buckets in a hash table, typically denoted as $\displaystyle LF = \\frac{n}{m}$.

Bucket

A storage location in a hash table where one or more key-value pairs can reside.

Collision

Occurs when two keys hash to the same index in a hash table, leading to conflicts in storage.

Chaining

A collision resolution technique where each bucket contains a linked list of entries that hash to the same index.

Open Addressing

A collision resolution strategy where a new index is searched for an entry in case of a collision.

Resize Operation

An action that increases the size of the hash table and rehashes existing entries, typically when the load factor exceeds a threshold.

Hash Table vs. Array

Hash tables allow for constant-time average complexity for lookups, while arrays require linear time for searches.

Best Case Performance

In an ideal scenario with no collisions, the time complexity for lookups in a hash table is O(1).

Worst Case Performance

In extreme cases, such as all keys colliding, lookups degrade to O(n), where n is the number of entries.

Dynamic Resizing Cause

When the load factor exceeds a certain threshold, a resize operation is triggered to maintain efficiency.

Example of a Hash Function

A simple hash function could be: $\displaystyle h(k) = k \mod m$, where $\displaystyle k$ is the key and $\displaystyle m$ is the size of the table.

True or False: Hash tables allow duplicate keys.

False: Each key must be unique within a hash table.

What is a collision in hash tables?

A collision occurs when two different keys hash to the same index in a hash table.

Explain separate chaining.

Separate chaining is a collision resolution technique where each index in the hash table points to a linked list of entries that hash to the same index.

True or False: Open addressing uses linked lists.

False. Open addressing resolves collisions within the hash table itself, not through linked lists.

What is linear probing?

Linear probing is an open addressing technique where the algorithm checks the next index sequentially until an empty slot is found.

Define quadratic probing.

Quadratic probing is an open addressing method where the interval between probes is the square of the attempt number, e.g., $\displaystyle i^2$.

How does double hashing work?

Double hashing uses a second hash function to calculate the step size for probing when a collision occurs.

Compare separate chaining and open addressing.

- Separate chaining uses linked lists. - Open addressing searches within the table. - Separate chaining can handle high load factors better.

What is a load factor?

The load factor is the ratio of the number of entries to the size of the hash table, typically denoted as $\displaystyle \frac{n}{m}$.

Explain rehashing.

Rehashing involves creating a new, larger hash table and re-inserting all existing entries to decrease collisions as the load factor increases.

What happens during a collision?

When a collision occurs, the hash table must apply a resolution technique to find an alternative place for the new entry.

What is chaining's main limitation?

Chaining can lead to increased overhead due to pointers in linked lists and might degrade performance if lists grow too long.

How does open addressing affect table size?

Open addressing can require larger tables, often needing to maintain a load factor below a certain threshold, typically 0.7.

Give an example of double hashing.

If the primary hash function is $\displaystyle h_1(key)$ and the secondary is $\displaystyle h_2(key)$, the probing sequence is $\displaystyle h_1(key) + i imes h_2(key)$.

What is a primary clustering problem?

Primary clustering occurs in open addressing when a sequence of filled slots causes long runs of occupied slots, leading to performance degradation.

True or False: All collision resolution techniques are equally efficient.

False. Efficiency varies based on the load factor and the number of collisions.

Fill in the blank: In separate chaining, the hash table entries point to ___ .

linked lists.

What is the disadvantage of linear probing?

Linear probing can cause clustering, making it inefficient as occupied indices group together, slowing down the search.

Define the term 'resize' in hash tables.

Resizing a hash table involves changing its size to maintain efficient performance, often triggered by exceeding a load factor threshold.

How does quadratic probing avoid clustering?

Quadratic probing reduces the likelihood of clustering by using squared increments, spreading out the occupied slots more evenly.

What is the purpose of a hash function?

A hash function transforms input data into a fixed-size hash code, determining the index for storing values in a hash table.

What is time complexity of hash table search?

Average case: O(1) - Constant time due to direct indexing. Worst case: O(n) - Occurs during collision scenarios.

Load factor definition?

The load factor, denoted as $\displaystyle \frac{n}{m}$, represents the ratio of the number of elements (n) to the number of buckets (m) in a hash table.

True or false: Higher load factor improves performance.

False - A higher load factor increases the likelihood of collisions, which can degrade performance.

Compare open addressing and chaining.

Open addressing: Collision resolution by finding next available slot. Chaining: Each bucket holds a linked list of entries.

Define amortized analysis in hash tables.

Amortized analysis evaluates the average time per operation over a sequence of operations, rather than the worst-case for each operation.

What does resizing a hash table involve?

Resizing involves creating a new larger table and rehashing all existing keys to fit the new table size.

Impact of poor hash function?

A poor hash function can lead to clusters of collisions, resulting in degraded performance and increased time complexity.

What is the purpose of a hash function?

The hash function converts keys into hash codes, which determine the index for storing elements in the hash table.

What is a collision in hash tables?

A collision occurs when two different keys hash to the same index in the hash table.

Fill in the blank: Efficiency of hash tables is greatly affected by _____ .

The choice of hash function and load factor.

Describe worst-case performance scenario.

Worst-case performance occurs when all keys hash to the same index, leading to linear time complexity O(n) for operations.

What is the expected time for insertion in a well-designed hash table?

Expected time for insertion is O(1) when the load factor is maintained at a reasonable level.

Hash tables in web caching

Hash tables store frequently accessed web data for quick retrieval, reducing load times and server stress.

True or False: Hash tables can store unique keys only.

True. Each key in a hash table must be unique to ensure correct value indexing.

Use of hash tables in databases?

Hash tables enable fast data retrieval by using keys for indexed access, enhancing database performance. - Key-value storage - Quick lookups

Fill in the blank: Hash tables are used in ________ for managing user sessions.

Hash tables are used in web applications for managing user sessions.

How do hash tables support spell check?

Hash tables store dictionaries of words. When checking spelling, the application hashes the input word to quickly find it in the table.

Comparison of hash tables and arrays?

Hash tables provide faster lookups (O(1) average) compared to arrays (O(n)). Arrays require sequential access while hash tables allow direct index access.

Use of hash tables in social media?

Hash tables manage user profiles and connections efficiently, facilitating quick searches and updates. - Fast user lookup - Relationship mapping

Question: Why are hash tables used in caches?

Hash tables allow quick data retrieval, reducing access times for frequently needed data and improving application performance.