Flashcards on Hash Tables: Concepts, Operations, and Performance
Hash Tables: Concepts, Operations & Performance Explained
Tap to flip · Swipe to navigate
Open Addressing Probing Techniques
9 cards
Card 1
Question: What is the form of the probe function used in linear probing (given an auxiliary hash h0) and how is the probe sequence generated for a key k?
Answer: h(k,i) = (h0(k) + i) mod m for i = 0,1,...,m-1. Start at T[h0(k)], then T[h0(k)+1], ... up to T[m-1], wrap to T[0], continuing until T[h0(k)-1]. The i
Card 2
Question: What primary performance problem does linear probing suffer from and why does it occur?
Answer: Primary clustering: long runs of occupied slots form and tend to grow, increasing average search time. Clusters form because an empty slot preceded by
Card 3
Question: How does quadratic probing define its probe function (using h0, c1, c2) and how do probe offsets behave?
Answer: h(k,i) = (h0(k) + c1*i + c2*i^2) mod m. Offsets from the initial position depend quadratically on the probe number i (i and i^2 terms).
Card 4
Question: What clustering phenomenon can still occur with quadratic probing and why?
Answer: Secondary clustering: if two keys share the same initial probe position h0(k), they follow identical probe sequences, since h(k1,0)=h(k2,0) implies h(
Card 5
Question: What is double hashing's probe function and how does it differ from linear and quadratic probing regarding dependence on the key?
Answer: h(k,i) = (h1(k) + i * h2(k)) mod m. Unlike linear/quadratic probing, the probe sequence depends on the key via both the initial position h1(k) and the
Card 6
Question: Why must h2(k) be relatively prime to the table size m in double hashing?
Answer: So the probe sequence visits every slot (the entire table) before repeating; if h2(k) and m share a common factor, the sequence cycles over only a sub
Card 7
Question: Give one convenient way to ensure h2(k) is relatively prime to m in double hashing.
Answer: Choose m as a power of two and design h2(k) to always return an odd number (which is relatively prime to a power of two). Another option (mentioned) i
Card 8
Question: How many distinct probe sequences does double hashing provide compared to linear/quadratic probing when m is prime or a power of two?
Answer: Double hashing can provide Θ(m^2) distinct probe sequences (each distinct pair (h1(k),h2(k)) gives a different sequence), whereas linear/quadratic pro
Card 9
Question: In the example given, what were the sample choices for h1 and h2 and how was key 14 inserted into a table of size 13?
Answer: Example choices: h1(k)=k mod 13 and h2(k)=1+(k mod 11). For key 14: h1=1 and h2=1+(14 mod 11)=4. Probing examined slots 1 and 5 (1+4), then inserted i