7 Hash Tables Free Online FlashCards

What is a hash table?

A hash table is a data structure that stores key–value pairs using an array, a hash function, and a collision-resolution strategy.

How does hash-table lookup work?

It computes the key’s hash value, maps it to a bucket or slot, examines entries there, and uses key equality to confirm the match.

What must a hash function guarantee about equal keys?

Equal keys must produce equal hash values, but unequal keys may produce the same hash value or bucket index.

What is a hash-table collision?

A collision occurs when two different keys are assigned to the same bucket or slot.

How does separate chaining resolve collisions?

Separate chaining stores all entries mapping to one bucket in a collection, such as a linked list or dynamically managed sequence.

How does open addressing resolve collisions?

Open addressing stores every entry directly in the table array and searches a probe sequence of alternative slots after a collision.

What is linear probing?

Linear probing checks consecutive positions using $index_i = (h(k) + i) \bmod m$.

Why are tombstones used in open addressing?

A tombstone marks a deleted entry while telling searches to continue probing, preventing a search from stopping too early.

Why must entries be rehashed after resizing?

It allocates a larger array and rehashes every entry because changing the bucket count changes the result of $hash(key) \bmod m$.

How does geometric growth affect insertion complexity?

A resize costs $O(n)$ when it occurs, but geometric growth spreads these costs across insertions, giving amortized $O(1)$ insertion.

What are hash-table operation bounds?

With good distribution and controlled load factor, search, insertion, and deletion are expected $O(1)$, but each can be $O(n)$ in the worst case.

When is a hash table a strong data-structure choice?

A hash table is preferable for fast average-case membership tests, key–value associations, and frequent unsorted insertion or deletion.