Master Hashing Collision Resolution: Open Addressing and Chaining

Question 1

In open addressing, which technique is used to resolve collisions by placing the colliding element in the next available slot?

Accepted Answer

Linear probing

Answer

Quadratic probing

Answer

Double hashing

Answer

Separate chaining

Question 2

What does the load factor represent in a hash table?

Accepted Answer

Ratio of occupied slots to total slots

Answer

Ratio of total slots to occupied slots

Answer

Number of collisions divided by the number of insertions

Answer

Size of the hash table in bytes

Question 3

When using quadratic probing, what is the formula for calculating the step size for each successive probe?

Accepted Answer

i^2

Answer

i

Answer

i(i+1)

Answer

i^3

Question 4

What is the primary purpose of rehashing in open addressing?

Accepted Answer

To resize the hash table when the load factor exceeds a certain threshold

Answer

To improve the distribution of elements in the hash table

Answer

To reduce the number of collisions

Answer

To eliminate the need for collision resolution techniques

Question 5

Which of the following is a potential performance issue associated with chaining?

Accepted Answer

Cache misses due to pointer following

Answer

Primary clustering

Answer

Difficulty handling large keys

Answer

Excessive memory allocation

Question 6

Open addressing stores data in the same array as the hash table. Which of the following is NOT a consequence of this approach?

Accepted Answer

Uses linked lists to handle collisions

Answer

Can result in primary clustering

Answer

May suffer from performance degradation due to collisions

Answer

Potentially slower search operations

Question 7

Open addressing and chaining are two primary collision resolution strategies in hashing. Which approach is generally more efficient in terms of memory utilization?

Accepted Answer

Open addressing, as it stores data directly in the hash table array

Answer

Chaining, as it uses linked lists to store data, reducing the overall size of the hash table

Answer

Both approaches have comparable memory efficiency

Answer

Neither approach is particularly efficient in terms of memory utilization

Question 8

Identify a limitation of quadratic probing:

Accepted Answer

Potential for primary clustering

Answer

Additional storage requirement for quadratic coefficients

Answer

Slower operation compared to linear probing

Answer

Inapplicable to hash tables with keys of varying sizes

Question 9

What is the primary purpose of a collision-resolution policy in hashing?

Accepted Answer

Determining the approach for handling collisions when keys map to the same hash value

Answer

Ensuring the insertion of all keys into the hash table

Answer

Improving the average search time of the hash table

Answer

Reducing the memory consumption of the hash table

Question 10

In chaining, how are collisions resolved?

Accepted Answer

Inserting colliding elements into a linked list at the corresponding hash value

Answer

Overwriting the existing element at the corresponding hash value

Answer

Consecutive probing until an empty slot is found

Answer

Random probing until an empty slot is found

Question 11

Define the load factor in the context of hashing.

Accepted Answer

The ratio of the number of elements in the hash table to the size of the hash table

Answer

The number of collisions that occur during a hash table operation

Answer

The average number of elements in a bucket

Answer

The maximum capacity of the hash table

Question 12

What is the role of a hash function in hashing?

Accepted Answer

Mapping input keys to a fixed-size representation

Answer

Resolving collisions in the hash table

Answer

Determining the size of the hash table

Answer

Searching for a specific key in the hash table

Question 13

The load factor of a hash table represents:

Accepted Answer

The ratio of stored keys to the hash table size.

Answer

The ratio of the hash table size to the number of stored keys.

Answer

The number of collisions divided by the number of stored keys.

Answer

The number of empty slots in the hash table.

Question 14

In linear probing for collision resolution, the probe sequence follows a:

Accepted Answer

Linear pattern.

Answer

Quadratic pattern.

Answer

Double hashing pattern.

Answer

Random pattern.

Question 15

The fundamental objective of collision resolution techniques in hashing is to:

Accepted Answer

Minimize the negative impact of collisions.

Answer

Prevent collisions from occurring.

Answer

Completely eliminate collisions.

Answer

Detect and report collisions.

Question 16

What is the primary role of the hash function in chaining?

Accepted Answer

To distribute elements evenly across buckets

Answer

To resolve collisions by creating linked lists in each bucket

Answer

To determine the size of the hash table

Answer

To prevent overflow by dynamically resizing the hash table

Question 17

What action can lead to primary clustering in an open-addressed hash table?

Accepted Answer

Inserting a large number of elements with consecutive keys

Answer

Deleting elements from the hash table

Answer

Updating the values of existing elements

Answer

Probing for an empty slot

Question 18

Which collision resolution technique is utilized in chaining?

Accepted Answer

Separate chaining

Answer

Linear probing

Answer

Quadratic probing

Answer

Double hashing

Question 19

What is a key benefit of employing a linear probing sequence in open addressing?

Accepted Answer

Simplicity and efficiency

Answer

Minimal memory overhead

Answer

Guaranteed to find an empty slot

Answer

Improved search performance in the presence of clustering

Question 20

How does load factor affect the performance of open addressing and chaining collision resolution techniques?

Accepted Answer

High load factor increases collisions in open addressing and lengthens chains in chaining, slowing down search and insert operations.

Answer

High load factor improves search performance in both open addressing and chaining.

Answer

Load factor has no impact on the performance of open addressing or chaining.

Answer

High load factor shortens chains in chaining and reduces collisions in open addressing.

Question 21

When dealing with scenarios where keys are likely to be inserted and deleted sequentially, why is chaining a preferred method for resolving collisions?

Accepted Answer

Chaining effectively handles dynamic sets.

Answer

Chaining prevents primary and secondary clustering.

Answer

Chaining reduces the need to manage tombstone records.

Question 22

In chaining, collisions are resolved by:

Accepted Answer

Inserting colliding keys into a linked list at the same hash location

Answer

Probing for an empty location in the hash table

Answer

Replacing existing keys with colliding keys

Answer

Storing all keys in the same hash location

Question 23

Given a table size of m and a hash function h(k), the probe sequence used in linear probing is:

Accepted Answer

h(k), h(k)+1, h(k)+2, ...

Answer

h(k), h(k)+m, h(k)+2m, ...

Answer

h(k), h(k-1), h(k-2), ...

Answer

h(k), h(k) mod m, h(k) mod m + 1, ...

Question 24

One potential drawback of open addressing with linear probing is:

Accepted Answer

Primary clustering

Answer

It is generally less efficient than chaining

Answer

It is unaffected by the load factor

Answer

It always finds an empty location for a key

Question 25

What is the formula for calculating the load factor of a hash table?

Accepted Answer

Number of elements in the table divided by the size of the table

Answer

Number of collisions divided by the number of elements

Answer

Average number of probes required to find an element

Answer

Maximum number of elements that can be stored in the table

Question 26

Which technique is primarily used by hash tables to manage collisions?

Accepted Answer

Employing open addressing or chaining

Answer

Storing multiple elements in the same location

Answer

Creating an overflow area to hold colliding elements

Answer

Ignoring the colliding elements

Question 27

In linear probing, which of the following is used to handle collisions?

Accepted Answer

Inserting a new entry into the next available slot in the hash table

Answer

Creating a linked list for each collision in the hash table

Answer

Rehashing the key using a different hash function

Answer

Splitting the hash table into multiple, smaller hash tables

Question 28

In chaining, each slot in the hash table contains a:

Accepted Answer

Pointer to the first element in a linked list

Answer

Value associated with the key

Answer

Flag indicating whether the slot is occupied

Answer

Hash function used to generate the slot

Question 29

What is the primary benefit of using a secondary hash function in double hashing?

Accepted Answer

Reduces the likelihood of primary clustering

Answer

Eliminates the need for linked lists in chaining

Answer

Speeds up the search process

Answer

Simplifies the insertion and deletion of elements

Question 30

Which data structure is used to implement chaining in hash tables?

Accepted Answer

Linked list

Answer

Array

Answer

Queue

Answer

Stack

Question 31

What is the worst-case time complexity of searching for an element in a hash table using chaining?

Accepted Answer

O(n)

Answer

O(1)

Answer

O(log n)

Answer

O(n^2)

Question 32

What primary advantage does chaining offer over open addressing?

Accepted Answer

Enhanced efficiency for searching operations.

Answer

Reduced likelihood of losing elements.

Answer

Optimized space utilization.

Answer

Accelerated insertion performance.

Question 33

Identify a potential drawback associated with linear probing.

Accepted Answer

Clustering of elements that collide.

Answer

Increased search time in worst-case scenarios.

Answer

Requirement for a larger hash table.

Answer

Challenges in deleting elements.

Question 34

What is the primary purpose of a hash function in the context of chaining?

Accepted Answer

To determine the specific bucket where an element should be inserted.

Answer

To prevent collisions from occurring altogether.

Answer

To calculate the key associated with an element.

Answer

To store the location of an element within the table.

Question 35

Which of the following is considered a type of secondary clustering?

Accepted Answer

Double hashing.

Answer

Primary clustering.

Answer

Quadratic probing.

Question 36

What is the primary purpose of a hash function in the context of open addressing?

Accepted Answer

To distribute keys evenly across the hash table, minimizing collisions

Answer

To detect and resolve collisions by generating unique probe sequences

Answer

To determine the optimal size of the hash table based on the number of keys

Answer

To store the key-value pairs securely within the hash table

Question 37

Which of the following accurately describes the process of linear probing in open addressing?

Accepted Answer

Systematically increments the probe index by a constant value until an empty slot is found

Answer

Uses a complex mathematical formula to determine the next probe index

Answer

Performs a random search for an empty slot within the hash table

Answer

Rehashes the key if no empty slot is available

Question 38

In chaining, which data structure is commonly used to store the colliding elements associated with a given key?

Accepted Answer

Linked list: A dynamic collection of elements connected by pointers

Answer

Array: A fixed-size collection of elements

Answer

Hash table: A data structure that uses keys to store and retrieve data

Answer

Binary search tree: A sorted binary tree used for efficient searching and insertion

Question 39

What is the fundamental distinction between open addressing and chaining in a hash table?

Accepted Answer

Open addressing uses a single array, while chaining employs a collection of linked lists

Answer

Open addressing permits duplicate keys, whereas chaining does not

Answer

Open addressing has a higher average search time compared to chaining

Answer

Open addressing is less memory-efficient than chaining

Question 40

What is the key difference between linear probing and quadratic probing in open addressing?

Accepted Answer

Linear probing increments the hash function output by a constant, while quadratic probing increments it by a quadratic function of the probe number.

Answer

Linear probing uses a random offset, while quadratic probing uses a deterministic offset.

Answer

Linear probing is more efficient for low load factors, while quadratic probing is more efficient for high load factors.

Answer

Linear probing allows duplicate keys, while quadratic probing does not.

Question 41

What is the purpose of a load factor in open addressing?

Accepted Answer

To control the trade-off between collision resolution time and space utilization

Answer

To determine the maximum number of keys that can be inserted into the hash table

Answer

To estimate the probability of a collision occurring

Answer

To determine the size of the hash table

Question 42

What is the purpose of a dummy head in a singly linked list used for chaining?

Accepted Answer

To avoid special cases when searching for the first element

Answer

To simplify the implementation of collision resolution

Answer

To reduce the space overhead

Answer

To improve the performance of insertion operations

Question 43

What is the primary use of a bloom filter in hashing?

Accepted Answer

To determine if an element is definitely not in a set

Answer

To improve the space efficiency of a hash table

Answer

To reduce the number of collisions

Answer

To provide a guaranteed insertion order

Question 44

Quadratic probing, another type of open addressing, involves:

Accepted Answer

Probing the hash table with a quadratic sequence to find an empty slot

Answer

Inserting new elements into the next available slot in the hash table

Answer

Inserting new elements into a linked list attached to the collided slot

Answer

Rehashing the table with a different hash function to avoid collisions

Question 45

In open addressing with linear probing, what action is taken when a collision occurs?

Accepted Answer

The next available slot in the hash table is examined.

Answer

The element is discarded.

Answer

A new hash function is generated.

Question 46

Which of the following is a potential disadvantage of chaining in hash tables?

Accepted Answer

Increased memory overhead

Answer

Faster lookup and insertion

Answer

Reduced search time

Answer

Reduced cache locality

Question 47

Which technique is used to reduce clustering in open addressing?

Accepted Answer

Double hashing

Answer

Chaining

Answer

Linear probing

Answer

Extendible hashing

Question 48

In chaining, how are elements stored?

Accepted Answer

In a linked list or another appropriate data structure

Answer

In a separate hash table

Answer

In the same slot as the key