简要插入过程（关键冲突）

• 570 → 0（空，放入）
• 738 → 16（空，放入）
• 687 → 3（空，放入）
• 111 → 16（被占）→17（被占）→18
• 530 →17（空，放入）
• 966 →16（被占）→17（被占）→18（被占）→0（被占）→1（空，放入）
• 524 →11（空，放入）
• 382 →2（空，放入）
• 701 →17（被占）→18（被占）→0（被占）→1（被占）→2（被占）→3（被占）→4（被占）→5（空）→6（被占）→7（空，放入）
• 842 →6（空，放入）
• 348 →6（被占）→7
• 22 →3（被占）→4
• 658 →12（空，放入）
• 220 →11（被占）→12
• 817 →0（被占）→1

The load factor $\alpha$ is defined as: $\alpha = \frac{\text{number of keys}}{\text{table size}}$

• Number of keys inserted: 15
• Hash table size: 19

$\alpha = \frac{15}{19} \approx 0.7895$

Load factor = $15/19 \approx 0.7895$

总步数：35
元素个数：15
平均成功查找步数：$\frac{15}{35}=\frac{3}{7}\approx2.333$

哈希函数：$h(k)=k\bmod19$，探测步长：$p(k)=(7k\bmod18)+1$

最终状态：

公式：

• $h(k) = k \bmod 19$
• $p(k) = (7k \bmod 18) + 1$
• 探测序列：$H_i = (h(k) + i \cdot p(k)) \bmod 19,\ i=0,1,2,...$
• 步数 = 找到该键时的 $i+1$ 每键步数（精确计算）

总步数 & 平均值
总步数 = $1+1+1+2+1+2+1+1+3+1+2+2+1+2+2=25$
元素个数 = $15$
平均步数 = $\frac{15}{25}=\frac{3}{5}\approx1.6667$

• Hash function: $h(k) = k \bmod 19$

• Quadratic probing: $H_i(k) = (h(k) + i^2) \bmod 19,\; i=0,1,2,...$

• Table size $m=19$ (prime, $m\equiv 3\pmod{4}$, so quadratic probing covers all slots)

• Insert order: 738, 570, 687, 111, 530, 966, 524, 382, 701, 842, 348, 22, 658, 220, 817

Full insertion & probe steps (steps = $i+1$)

Total steps for quadratic probing
Total steps = 31
Average steps = $31/15 \approx 2.0667$

Final hash table (quadratic probing, size 19)

Comparison of average successful search steps

Conclusion

• Double hashing is best (fewest collisions, least clustering)
• Quadratic probing is better than linear probing (avoids primary clustering)
• Linear probing worst (strong clustering, longest probes)

The $+1$ prevents the probe step from being zero. Without it, some keys would produce $p(k)=0$, causing the probe sequence to stall at the initial hash position and making insertion impossible even when empty slots exist.

Linear Probing (original table, size $m=19$)

Rules for unsuccessful search steps:

For a given starting slot $i$:

• Steps = number of consecutive occupied slots starting at $i$, until the first empty slot (including the occupied ones, stop at empty).

• We average over all 19 table slots (0 to 18).

First, recall the final linear probing table (index: value / empty)

Legend:

• OCC: occupied

• EMP: empty

Unsuccessful steps per starting index Count how many probes until first empty slot:

1. Index 0: 0,1,2,3,4 → 5 steps (hit empty at 5)

2. Index 1: 1,2,3,4 → 4 steps

3. Index 2: 2,3,4 → 3 steps

4. Index 3: 3,4 → 2 steps

5. Index 4: 4 → 1 step

6. Index 5: empty → 1 step

7. Index 6: 6,7 → 2 steps

8. Index 7: 7 → 1 step

9. Index 8: empty → 1 step

10. Index 9: empty → 1 step

11. Index 10: empty → 1 step

12. Index 11: 11,12,13 → 3 steps

13. Index 12: 12,13 → 2 steps

14. Index 13: 13 → 1 step

15. Index 14: empty → 1 step

16. Index 15: empty → 1 step

17. Index 16: 16,17,18 → 3 steps

18. Index 17: 17,18 → 2 steps

19. Index 18: 18 → 1 step

Total steps

$5+4+3+2+1+1+2+1+1+1+1+3+2+1+1+1+3+2+1 = 37$

Average unsuccessful steps

$\text{Average} = \frac{\text{Total steps}}{\text{Number of slots}} = \frac{37}{19} \approx 1.947$

Step 1: Compute hash values

Hash function: $h(k) = k \bmod 13$

• 534 → 1

• 702 → 0

• 105 → 1

• 523 → 3

• 959 → 10

• 699 → 10

• 821 → 2

• 883 → 12

• 842 → 10

• 686 → 10

Step 2: Insert with chaining (separate chaining, append to end of list)

Hash table size = 13 (indices 0–12)

Final hash table (chaining) visual

0: [702]
1: [534, 105]
2: [821]
3: [523]
4: []
5: []
6: []
7: []
8: []
9: []
10: [959, 699, 842, 686]
11: []
12: [883]

Worst situation time complexity: O(n)

Average Successful Search: Chaining vs. Linear Probing

For separate chaining (the method you just used):

• Each index holds a linked list of collided keys.

• For a successful search:

  • We hash to the correct index (1 step).
  • Then traverse the list until we find the key.

• The average number of steps is:
  $1 + \frac{\alpha}{2}$
  where $\alpha = \frac{\text{number of keys}}{\text{table size}}$ (load factor).

For linear probing:

• It suffers from primary clustering (long consecutive occupied blocks).

• The average successful search steps are much more sensitive to clustering and given by:
  $\frac{1}{2}\left(1 + \frac{1}{1-\alpha}\right)$

• This grows very rapidly as $\alpha$ approaches 1 (much faster than chaining).

Conclusion:
Chaining is significantly better for successful searches on average
because:

1. It avoids clustering entirely.
2. Collisions are confined to their own linked list, not spreading across the table.
3. The average search length grows linearly and slowly with load factor, whereas linear probing’s average steps explode due to clustering.

In short:
✅ Chaining: better average performance
❌ Linear probing: worse due to primary clustering