Hash Tables

What is a hash table?

A data structure that maps keys to values using a hash function to compute an index in an array, allowing for fast data retrieval.

What is the average-case time complexity for accessing elements in a hash table?

O(1) — constant time, assuming a good hash function and low load factor.

Name three common collision resolution techniques.

1. Linear probing\n2. Quadratic probing\n3. Separate chaining

What is linear probing?

A collision resolution technique where the algorithm searches sequentially for the next empty slot in the array.

What is clustering in the context of linear probing?

The formation of blocks of occupied slots, which increases the number of probes required during insertion and search.

How does quadratic probing reduce clustering?

It increases the interval between probes using a quadratic function: \\text{step} = i^2, where i is the probe number.

What is double hashing?

A method that uses a second hash function to determine the step size for probing, minimizing clustering and improving distribution.

Why should the hash table size be prime when using double hashing?

To ensure the entire table can be probed and to avoid infinite loops during insertion or search.

What is separate chaining?

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

What is a hash function?

A function that converts a key into an integer index used to store the value in a hash table.

What is the load factor in a hash table?

The ratio of the number of stored elements to the size of the table:\n\\text{Load Factor} = \\frac{\\text{Number of elements}}{\\text{Table size}}

What is the ideal load factor for hash table performance?

Between 0.5 and 0.75 for open addressing techniques.

What is rehashing?

The process of creating a new, larger hash table and reinserting all elements using a new hash function when the table becomes overloaded.

Why is deletion in open addressing difficult?

Removing an element may break the probing sequence for other elements, making them unreachable during search.

How is deletion handled in open addressing?

Elements are marked as deleted (using a special marker), but the slot is not cleared to preserve the probing sequence.

Why are hash tables not suitable for ordered data traversal?

Because hash tables do not store elements in a sorted order—trees are more suitable for that.

When are hash tables the best choice?

When fast search, insertion, and deletion are required, and the data size is relatively stable.

How is modular arithmetic used in hash functions?

It maps large integers into a fixed range by computing the remainder:\n\\text{Index} = \\text{key} \\mod \\text{table size}

What is primary clustering?

A phenomenon in linear probing where groups of occupied cells lead to longer probe sequences.

What is secondary clustering?

Clustering in quadratic probing where different keys follow the same probing sequence, causing virtual clusters.