06 Hash Tables Free Online FlashCards

What is a hash table?

A hash table is a data structure that stores key–value pairs and supports efficient insertion, lookup, and deletion.

What properties should a useful hash function have?

A useful hash function is deterministic, fast, well distributed, and consistent with equality.

What is a collision in a hash table?

A collision occurs when two different keys map to the same table index.

How does separate chaining resolve collisions?

Separate chaining stores all entries with the same index in a collection associated with that slot, often a linked list.

How does open addressing resolve collisions?

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

Why does open addressing use tombstones?

A tombstone marks a deleted slot so probing continues through it instead of incorrectly ending a search.

Why must entries be rehashed after resizing?

Resizing requires recomputing indexes because changing the capacity changes the modulus used to place entries.

What must a hash function guarantee about equal keys?

Equal keys must produce the same hash value. Otherwise, a lookup may search a different location from the one used during insertion.

How does data-structure hashing differ from cryptographic hashing?

Data-structure hashing prioritizes speed and good distribution. Cryptographic hashing additionally aims to resist intentional attacks and make inputs difficult to recover or manipulate.

What is primary clustering in linear probing?

Primary clustering is the formation of long runs of consecutive occupied slots. In linear probing, these runs increase the probe lengths of later operations.

How does double hashing determine probe positions?

Double hashing uses a second hash function to determine the probe step: $p_i(k)=(h_1(k)+i\,h_2(k))\bmod m$.

When are hash-table operations expected to take $O(1)$ time?

Expected $O(1)$ operations require assumptions such as good distribution, controlled load factor, and an effective collision strategy. Worst-case search, insertion, or deletion can still take $O(n)$.