Hashing Concepts

Front

What is the goal of hashing?

Back

To perform inserts, deletes, and finds in constant average time.

Front

What are the main topics covered in hashing?

Back

Hash table, hash function, collisions.

Front

What are the two main methods of collision handling in hashing?

Back

Separate chaining and open addressing.

Front

What is the load factor in hashing?

Back

The load factor is a measure of how full the hash table is allowed to get before its capacity is automatically increased.

Front

What is the average time complexity for searching in a hash table?

Back

O(1) on average, but can degrade to O(n) in the worst case.

Front

What is a hash function?

Back

A function that maps keys into positions in a hash table.

Front

What is a collision in hashing?

Back

A collision occurs when two keys map to the same location in the hash table.

Front

What is linear probing in open addressing?

Back

A method where, upon collision, the algorithm checks the next available position in the table.

Front

What is quadratic probing?

Back

A method where the probe sequence is based on the square of the probe number, reducing clustering.

Front

What is double hashing?

Back

A technique that uses a second hash function to determine the next position to check after a collision.