Hashing: 32 MCQs with answers

To map keys to indices in an array

A hash function computes an index from a key, enabling O(1) average-time access in a hash table.

key % table_size

The modulo operation (key % table_size) is a simple and widely used hash function to map keys into the range of table indices.

Two different keys map to the same hash index

A collision occurs when a hash function produces the same index for two or more distinct keys.

Separate chaining

Separate chaining stores all elements that hash to the same index in a linked list (or similar structure) at that slot.

Database indexing

Hashing is widely used in database indexing, symbol tables, caches, and many other applications requiring fast lookups.

True

Yes, this is called a collision, which is inevitable when the number of possible keys exceeds the table size.

False

Hash tables do not preserve insertion order; elements are placed based on their hash values, not their insertion sequence.

To map keys to array indices

A hash function's main role is to convert a key into an array index, enabling direct access to the table slot.

Key modulo table size ($k \mod m$)

The modulo operation ($k \mod m$) is a standard and simple hash function for integer keys, producing an index in the range $[0, m-1]$.

When two different keys map to the same index

A collision occurs when a hash function maps two distinct keys to the same array index, requiring a resolution strategy.

Separate chaining

Separate chaining stores all elements that hash to the same index in a linked list at that slot.

It probes alternative slots until an empty one is found

Open addressing resolves collisions by searching for the next available slot using a probe sequence, unlike chaining which uses extra memory outside the table.

The ratio of the number of stored elements to the table size

The load factor $\alpha = n/m$ (where $n$ is the number of keys and $m$ is the table size) indicates how full the table is, affecting performance.

It distributes keys uniformly across the table

A good hash function minimizes collisions by spreading keys evenly over the table, leading to near O(1) average operations.

O(1)

With a good hash function and low load factor, the average search time is constant, O(1), independent of the number of elements.

h(k) + 1 (mod table size)

Linear probing checks consecutive slots: $(h(k) + i) \mod m$ for $i = 1, 2, \ldots$, so the next slot is $h(k)+1$ modulo the table size.

It requires extra memory for pointers or linked lists

Separate chaining uses additional memory to store linked list nodes, which can be a drawback compared to open addressing that uses the table itself.

It maps keys to array indices.

A hash function takes a key and computes an array index where the corresponding value is stored. This mapping enables average O(1) access.

Separate chaining

Separate chaining is a collision resolution method where each table slot holds a linked list of keys that hash to the same index. Other options are unrelated to collision resolution.

O(1)

A well-designed hash table with a good hash function and appropriate load factor achieves average constant time O(1) for insert, delete, and search operations.

The ratio of the number of stored elements to the table size

The load factor α is defined as the number of elements stored divided by the table size. It is a key indicator of how full the table is and affects performance.

Implementing a symbol table in a compiler

Hashing is widely used in symbol tables (e.g., in compilers), databases, and caches to provide fast key-based lookup. Sorting, tree traversal, and graph algorithms are not primary applications of hashing.

It probes for the next available slot

Open addressing resolves collisions by probing (e.g., linear, quadratic, or double hashing) to find another empty slot within the same array.

Number of keys divided by number of slots

Load factor α = n/m, where n is the number of keys stored and m is the number of slots. It indicates how full the table is.

It distributes keys uniformly across the table

A good hash function minimizes collisions by spreading keys uniformly over the available indices.

O(1)

With a good hash function and low load factor, hash table operations achieve constant average time complexity, O(1).

h(k) + 1

Linear probing checks consecutive slots: (h(k) + i) mod m for i = 0, 1, 2, ... until an empty slot is found.

It requires extra memory for pointers

Separate chaining uses linked lists, which require additional memory for node pointers, unlike open addressing which stores all elements in the array itself.

Separate chaining

Separate chaining is a different collision resolution technique that uses linked lists, not open addressing.

It reduces the number of collisions

A prime table size helps distribute keys more uniformly, especially when keys have patterns, reducing clustering and collisions.

Two different hash functions

Double hashing uses a second hash function to compute the step size, making the probe sequence more flexible and reducing clustering.

O(n)

In the worst case, all keys collide into one chain, making the search linear in the number of keys, O(n).