Hashing Practice Questions

Calculate the hash value for each key using $h(k)=k \bmod 9$:
$h(5)=5$, $h(28)=1$, $h(19)=1$, $h(15)=6$, $h(26)=8$, $h(33)=6$, $h(12)=3$, $h(17)=8$, $h(10)=1$.
Group keys by their hash index: index $1 = \{28, 19, 10\}$, index $3 = \{12\}$, index $5 = \{5\}$, index $6 = \{15, 33\}$, and index $8 = \{26, 17\}$.
Determine the length of each chain: $L_1=3$, $L_3=1$, $L_5=1$, $L_6=2$, and $L_8=2$.
The longest chain is located at index $1$ with a length of $3$.
[CORRECT_OPTION: 3]

To find the slot where key 24 is stored, we need to insert all keys (63, 50, 25, 79, 67, 24) one by one into the hash table of size $m=11$ using the given double hashing scheme. The hash function for the $i$-th probe is $H(k, i) = [h_1(k) + i \cdot h_2(k)] \mod m$.

1. Key 63:
   $h_1(63) = 63 \mod 11 = 8$
   $h_2(63) = 1 + (63 \mod 7) = 1 + 0 = 1$
   $H(63, 0) = [8 + 0 \cdot 1] \mod 11 = 8$. Slot 8 is occupied by 63.

2. Key 50:
   $h_1(50) = 50 \mod 11 = 6$
   $h_2(50) = 1 + (50 \mod 7) = 1 + 1 = 2$
   $H(50, 0) = [6 + 0 \cdot 2] \mod 11 = 6$. Slot 6 is occupied by 50.

3. Key 25:
   $h_1(25) = 25 \mod 11 = 3$
   $h_2(25) = 1 + (25 \mod 7) = 1 + 4 = 5$
   $H(25, 0) = [3 + 0 \cdot 5] \mod 11 = 3$. Slot 3 is occupied by 25.

4. Key 79:
   $h_1(79) = 79 \mod 11 = 2$
   $h_2(79) = 1 + (79 \mod 7) = 1 + 2 = 3$
   $H(79, 0) = [2 + 0 \cdot 3] \mod 11 = 2$. Slot 2 is occupied by 79.

5. Key 67:
   $h_1(67) = 67 \mod 11 = 1$
   $h_2(67) = 1 + (67 \mod 7) = 1 + 4 = 5$
   $H(67, 0) = [1 + 0 \cdot 5] \mod 11 = 1$. Slot 1 is occupied by 67.

6. Key 24:
   $h_1(24) = 24 \mod 11 = 2$
   $h_2(24) = 1 + (24 \mod 7) = 1 + 3 = 4$

   • Probe $i=0$: $H(24, 0) = [2 + 0 \cdot 4] \mod 11 = 2$. Slot 2 is occupied by 79.
   • Probe $i=1$: $H(24, 1) = [2 + 1 \cdot 4] \mod 11 = 6 \mod 11 = 6$. Slot 6 is occupied by 50.
   • Probe $i=2$: $H(24, 2) = [2 + 2 \cdot 4] \mod 11 = [2 + 8] \mod 11 = 10 \mod 11 = 10$. Slot 10 is free. Slot 10 is occupied by 24.

Thus, key 24 gets stored in slot 10.

[CORRECT_OPTION: None]

The problem describes an adversary who tries to maximize collisions in a hash table where $k > m$.
Division and multiplication methods are deterministic and an adversary can choose keys that map to the same slot, causing many collisions.
Universal hashing is a technique where the hash function is chosen randomly from a family of hash functions.
This randomness makes it difficult for an adversary to predict which keys will collide, thus minimizing the worst-case number of collisions.
Therefore, universal hashing is the best strategy against a malicious adversary.

We have $n$ keys and $m$ hash table slots.
The hashing scheme uses $h_1$ for odd keys and $h_2$ for even keys.
Assuming a simple uniform hash function means that each key is equally likely to hash into any of the $m$ slots.
Approximately half of the $n$ keys will be odd, and half will be even.
So, the number of odd keys is approximately $n/2$.
The number of even keys is approximately $n/2$.
For the $n/2$ odd keys, they are hashed using $h_1$ into $m$ slots.
For the $n/2$ even keys, they are hashed using $h_2$ into $m$ slots.
The expected number of keys in a slot from the odd keys is $\frac{n/2}{m} = \frac{n}{2m}$.
The expected number of keys in a slot from the even keys is $\frac{n/2}{m} = \frac{n}{2m}$.
The total expected number of keys in a slot is the sum of these two expectations:
Expected keys per slot = $\frac{n}{2m} + \frac{n}{2m} = \frac{2n}{2m} = \frac{n}{m}$.
The expected number of keys per slot is $n/m$.

The dynamic hashing approach uses the 2 least significant bits (LSBs) of a key to index into a hash table of size 4. Collisions are resolved by organizing keys into a binary tree, first splitting by the 3rd LSB, then by the 4th LSB if further collisions occur. A split happens only when a collision occurs.

Let's trace the insertions for option (c): 10, 9, 6, 7, 5, 13.

1. 10 (1010): 2 LSBs are '10'. Insert into slot '10'.
2. 9 (1001): 2 LSBs are '01'. Insert into slot '01'.
3. 6 (0110): 2 LSBs are '10'. Collision in slot '10' (with 10). Split slot '10' by 3rd LSB.
   • 10 (1010): 3rd LSB is '0'.
   • 6 (0110): 3rd LSB is '1'.
   • Slot '10' now has a tree: root (split by 3rd LSB), left child (0) has 10, right child (1) has 6.
4. 7 (0111): 2 LSBs are '11'. Insert into slot '11'.
5. 5 (0101): 2 LSBs are '01'. Collision in slot '01' (with 9). Split slot '01' by 3rd LSB.
   • 9 (1001): 3rd LSB is '0'.
   • 5 (0101): 3rd LSB is '0'.
   • Collision again for 9 and 5 in the '0' subtree. Split by 4th LSB.
     • 9 (1001): 4th LSB is '1'.
     • 5 (0101): 4th LSB is '0'.
   • Slot '01' now has a tree: root (split by 3rd LSB), left child (0) has a subtree (split by 4th LSB), with left (0) having 5 and right (1) having 9.
6. 13 (1101): 2 LSBs are '01'. Collision in slot '01'. 3rd LSB is '1'. Insert into the right child of the 3rd LSB split.
   • Slot '01' tree: root (split by 3rd LSB), left child (0) has subtree (5, 9), right child (1) has 13.

The resulting hash table state matches the given diagram: slot '00' is empty, slot '01' has a tree with root 0 and left child 1 (representing 3rd LSB split), slot '10' has a tree with root 0 and left child 1, and slot '11' is empty.

The problem describes a double hashing scheme and asks for the address returned by probe 1 for a given key.
The double hashing formula is given by $(h_1(k) + i \cdot h_2(k)) \pmod{table\_size}$, where $i$ is the probe value.

1. Calculate the primary hash function $h_1(k)$ for $k=90$ and $table\_size=23$:
   $h_1(90) = 90 \pmod{23} = 21$.

2. Calculate the secondary hash function $h_2(k)$ for $k=90$:
   $h_2(90) = 1 + (90 \pmod{19}) = 1 + 14 = 15$.

3. For probe 1, the value of $i$ is $1$. Substitute these values into the double hashing formula:
   Address $= (h_1(90) + 1 \cdot h_2(90)) \pmod{23}$
   Address $= (21 + 1 \cdot 15) \pmod{23}$
   Address $= (21 + 15) \pmod{23}$
   Address $= 36 \pmod{23}$

4. Finally, calculate the modulo to find the address:
   Address $= 13$.

The address returned by probe 1 for key value k=90 is 13.

In linear hashing, the total capacity of the file is determined by the number of buckets $N$ multiplied by the blocking factor $bfr$, which represents the maximum number of records per bucket. This is expressed as $Capacity = N \times bfr$. The loading factor $i$ is defined as the ratio of the actual number of records $r$ to this total capacity, given by $i = \frac{r}{N \times bfr}$. Rearranging this equation to solve for the number of records yields $r = i \times bfr \times N$. Therefore, the total number of records is the product of the loading factor, the blocking factor, and the number of buckets.

In a hash table using linear probing, an unsuccessful search for a key proceeds from its initial hash index until an empty slot is encountered. The number of comparisons corresponds to the number of probes made until reaching that empty slot. The occupied indices form contiguous clusters: $[8, 9, 0, 1]$ (wrapping around the table size of $10$), $[3, 4]$, and $[6]$.

For the cluster $[8, 9, 0, 1]$, a search hashing to index $8$ will probe slots $8, 9, 0, 1,$ and finally $2$ (the first empty slot), resulting in $5$ comparisons. Other hash values result in shorter probe sequences, such as $3$ probes for indices $3$ or $9$, and $2$ probes for indices $1, 4,$ or $6$. Therefore, the maximum number of comparisons needed for an unsuccessful search is $5$.

The hash function is defined as $f(key) = key \pmod 7$. We insert keys sequentially into the table:

1. $37 \pmod 7 = 2$: Store at index 2.
2. $38 \pmod 7 = 3$: Store at index 3.
3. $72 \pmod 7 = 2$: Collision at index 2, probe $2+1=3$ (collision), probe $3+1=4$. Store at index 4.
4. $48 \pmod 7 = 6$: Store at index 6.
5. $98 \pmod 7 = 0$: Store at index 0.
6. $11 \pmod 7 = 4$: Collision at index 4, probe $4+1=5$. Store at index 5.

The load factor, $\alpha$, of a hash table is a measure of how full the table is. It is defined as the ratio of the number of elements stored in the table to the number of available slots.
Given the number of elements is 2000 and the number of slots is 25, the load factor is calculated as:
$\alpha = \frac{\text{Number of elements}}{\text{Number of slots}} = \frac{2000}{25} = 80$

For a hash function to distribute keys uniformly over 10 buckets, the last digit of the result should be uniformly distributed across {0, 1, ..., 9}.
Let's analyze the last digits produced by h(i) = i^3 mod 10 for inputs 0 through 9. The sequence of last digits is {0, 1, 8, 7, 4, 5, 6, 3, 2, 9}. Each digit from 0 to 9 appears exactly once, indicating a perfect uniform distribution.
In contrast, h(i) = i^2 mod 10 produces last digits {0, 1, 4, 9, 6, 5, 6, 9, 4, 1}, which is non-uniform as some digits are repeated and others (2, 3, 7, 8) are missing.

To determine the maximum number of comparisons needed to search for an item that is not present, we must identify the longest contiguous sequence (cluster) of occupied slots, as a search for a non-existent key must probe until it hits an empty slot.

1. In a hash table with linear probing, the search sequence wraps around from the last index (9) to the first index (0).
2. Looking at the table, we identify the following occupied clusters:
   • Indices $\{3, 4\}$: Empty at 5. Max comparisons = $3$ ($3 \to 4 \to 5$).
   • Index $\{6\}$: Empty at 7. Max comparisons = $2$ ($6 \to 7$).
   • Indices $\{8, 9, 0, 1\}$: Since 8 is occupied, 9 is occupied, and the table wraps to 0 which is occupied, then 1 is occupied, the sequence is $8 \to 9 \to 0 \to 1$.
3. The next available empty slot after the cluster $\{8, 9, 0, 1\}$ is at index 2.
4. A search hashing to index 8 will result in the sequence $8, 9, 0, 1, 2$.
5. Counting these probes: $1 (index\ 8) + 1 (index\ 9) + 1 (index\ 0) + 1 (index\ 1) + 1 (index\ 2) = 5$ comparisons.

The hash function is $f(key) = key \pmod{13}$.

1. Insert 661: $661 \pmod{13} = 11$. Place in index $11$.
2. Insert 182: $182 \pmod{13} = 0$. Place in index $0$.
3. Insert 24: $24 \pmod{13} = 11$, which is occupied. Probe $(11 + 1) \pmod{13} = 12$. Place in index $12$.
4. Insert 103: $103 \pmod{13} = 12$, which is occupied. Probe $(12 + 1) \pmod{13} = 0$, which is occupied. Probe $(0 + 1) \pmod{13} = 1$. Place in index $1$.

Let $N$ be the total number of slots, so $N=100$.
Let $K$ be the number of initial slots that must remain unfilled, so $K=3$.
For the first insertion, the probability that it falls into any of the remaining $N-K=97$ slots (i.e., not one of the first 3 slots) is $97/100$.
Since collisions are resolved by chaining, subsequent insertions can fall into the same slot as a previous insertion. For the second insertion, the probability that it also falls into one of the $97$ unfilled slots (excluding the first 3) is $97/100$.
Similarly, for the third insertion, the probability that it falls into one of the $97$ unfilled slots (excluding the first 3) is $97/100$.
Since each insertion is an independent event, the total probability is the product of these individual probabilities.

$P = \left(\frac{97}{100}\right) \times \left(\frac{97}{100}\right) \times \left(\frac{97}{100}\right) = \frac{97 \times 97 \times 97}{100^3}$

We need to insert the given keys into a hash table with 9 slots using the hash function $h(k) = k \pmod 9$ and resolve collisions by chaining.

1. Calculate $h(k)$ for each key:
   $h(5) = 5 \pmod 9 = 5$
   $h(28) = 28 \pmod 9 = 1$
   $h(19) = 19 \pmod 9 = 1$
   $h(15) = 15 \pmod 9 = 6$
   $h(20) = 20 \pmod 9 = 2$
   $h(33) = 33 \pmod 9 = 6$
   $h(12) = 12 \pmod 9 = 3$
   $h(17) = 17 \pmod 9 = 8$
   $h(10) = 10 \pmod 9 = 1$

2. Construct the hash table:
   Slot 0: (empty)
   Slot 1: [28] -> [19] -> [10] (chain length 3)
   Slot 2: [20] (chain length 1)
   Slot 3: [12] (chain length 1)
   Slot 4: (empty)
   Slot 5: [5] (chain length 1)
   Slot 6: [15] -> [33] (chain length 2)
   Slot 7: (empty)
   Slot 8: [17] (chain length 1)

3. Determine chain lengths:
   Chain lengths for non-empty slots are 3, 1, 1, 1, 2, 1. For empty slots (0, 4, 7), the chain length is 0.

4. Identify maximum, minimum, and average chain lengths:
   Maximum chain length: 3
   Minimum chain length: 0
   Average chain length: $(3+1+1+0+1+2+0+1+0) / 9 = 9/9 = 1$.

The hash function is h(k) = k mod 10 with linear probing for collision resolution. We need to check which insertion sequence produces the given hash table.

Let's trace the insertion order for option C: 46, 34, 42, 23, 52, 33.

Initial table (empty):
[ , , , , , , , , , ]

1. Insert 46:

   • h(46) = 46 mod 10 = 6. Index 6 is empty.
   • Table: [ , , , , , , 46, , , ]

2. Insert 34:

   • h(34) = 34 mod 10 = 4. Index 4 is empty.
   • Table: [ , , , , 34, , 46, , , ]

3. Insert 42:

   • h(42) = 42 mod 10 = 2. Index 2 is empty.
   • Table: [ , , 42, , 34, , 46, , , ]

4. Insert 23:

   • h(23) = 23 mod 10 = 3. Index 3 is empty.
   • Table: [ , , 42, 23, 34, , 46, , , ]

5. Insert 52:

   • h(52) = 52 mod 10 = 2. Index 2 is occupied (by 42).
   • Linear probing: try index 3. Occupied (by 23).
   • Try index 4. Occupied (by 34).
   • Try index 5. Empty. Place 52 here.
   • Table: [ , , 42, 23, 34, 52, 46, , , ]

6. Insert 33:

   • h(33) = 33 mod 10 = 3. Index 3 is occupied (by 23).
   • Linear probing: try index 4. Occupied (by 34).
   • Try index 5. Occupied (by 52).
   • Try index 6. Occupied (by 46).
   • Try index 7. Empty. Place 33 here.
   • Table: [ , , 42, 23, 34, 52, 46, 33, , ]

This final table state matches the one given in the question. Therefore, this is a possible insertion order.

To determine the number of valid insertion sequences, we first identify the dependency constraints for each key based on the hash function $h(k) = k \mod 10$ and linear probing:

1. Independent Keys: $42$ ($h=2$), $23$ ($h=3$), $34$ ($h=4$), and $46$ ($h=6$) are hash-independent and can be inserted in any relative order as long as they appear before their dependent keys.
2. Dependent Keys:
   • $52$ ($h=2$) collides with $42, 23, 34$ and is placed at index $5$. Thus, $42, 23, 34$ must be inserted before $52$.
   • $33$ ($h=3$) collides with $23, 34, 52, 46$ and is placed at index $7$. Thus, $23, 34, 52, 46$ must be inserted before $33$.

Let the keys be $A=42, B=23, C=34, D=52, E=46, F=33$. The constraints are:

• $A, B, C < D$
• $B, C, D, E < F$

Since $F$ must be inserted after $B, C, D, E$, and $D$ must be inserted after $A, B, C$, $F$ must be the last element (position 6). For the remaining $5$ keys $\{A, B, C, D, E\}$, we must satisfy the condition that $D$ appears after $A, B, C$. In any random permutation of these $5$ keys, $D$ will appear after $A, B, C$ in exactly $\frac{1}{4}$ of the cases (because in the set $\{A, B, C, D\}$, $D$ is the last of the four in $\frac{3!}{4!} = \frac{1}{4}$ of permutations).

Total permutations = $5! = 120$.
Valid sequences = $120 \times \frac{1}{4} = 30$.

We simulate insertions with $h(k) = k \pmod{10}$ and linear probing:

1. Insert 12: $h(12) = 2$. Table[2] = 12.
2. Insert 18: $h(18) = 8$. Table[8] = 18.
3. Insert 13: $h(13) = 3$. Table[3] = 13.
4. Insert 2: $h(2) = 2$. Collides with 12. Probe: Table[3] (collides with 13). Probe: Table[4]. Table[4] = 2.
5. Insert 3: $h(3) = 3$. Collides with 13. Probe: Table[4] (collides with 2). Probe: Table[5]. Table[5] = 3.
6. Insert 23: $h(23) = 3$. Collides with 13. Probe: Table[4] (collides with 2). Probe: Table[5] (collides with 3). Probe: Table[6]. Table[6] = 23.
7. Insert 5: $h(5) = 5$. Collides with 3. Probe: Table[6] (collides with 23). Probe: Table[7]. Table[7] = 5.
8. Insert 15: $h(15) = 5$. Collides with 3. Probe: Table[6] (collides with 23). Probe: Table[7] (collides with 5). Probe: Table[8] (collides with 18). Probe: Table[9]. Table[9] = 15.

The final table state matches Option C.

Given the hash function $h(k) = k \pmod{11}$, we insert keys into the table using linear probing:

1. $43 \rightarrow 10$, $36 \rightarrow 3$, $92 \rightarrow 4$, $87 \rightarrow (10, 0)$, $11 \rightarrow (0, 1)$.
2. $4 \rightarrow (4, 5)$, $71 \rightarrow 6$, $13 \rightarrow 2$.
3. For the last key 14: $h(14) = 14 \pmod{11} = 3$.
4. Since indices $3, 4, 5,$ and $6$ are already occupied by $36, 92, 4,$ and $71$ respectively, linear probing continues until it finds the first empty bin.
5. The next available index is 7.