Store keys in a hash table that has no chains, moving along to the next free slot after a collision.
What to build
A hash table with open addressing and linear probing.
Requirements
- A key starts at slot
key % m. If that slot is taken, try the next one, wrapping round to slot 0 after the last. - Count one probe for every slot looked at, including the free slot where the key is stored.
- Print the table on one line, with
-for an empty slot, and the total number of probes on the next line.
Input
The first line has m and n. The second line has the n keys, which are all different.
Output
Two lines: the m slots, then the number of probes.
Constraints
1 ≤ n ≤ m ≤ 100, and each key is from 0 to 10000.
Example
Input:
7 4
10 17 24 5
Output:
- - - 10 17 24 5
8
Why it works
Keys that collide are stored next to each other, so a run of full slots grows and later keys must walk past it. The probe count shows how that cost rises as the table fills.
Examples
Example 1 · Input
7 4 10 17 24 5
Expected output
- - - 10 17 24 5 8
Example 2 · Input
3 3 2 5 8
Expected output
5 8 2 6
Hints
Hint 1
Keep a second array that says which slots are in use.
Hint 2
Start at key % m. While the slot is taken, move to (slot + 1) % m.
Hint 3
Count the first slot you look at as well as every slot after it.
Solution
Show one correct solution (try it yourself first)
#include <stdio.h>
int main(void) {
int m, n, table[100], used[100] = {0};
scanf("%d %d", &m, &n);
int probes = 0;
for (int i = 0; i < n; i++) {
int key;
scanf("%d", &key);
int slot = key % m;
probes++;
while (used[slot]) {
slot = (slot + 1) % m;
probes++;
}
table[slot] = key;
used[slot] = 1;
}
for (int s = 0; s < m; s++) {
if (s > 0) printf(" ");
if (used[s]) printf("%d", table[s]);
else printf("-");
}
printf("\n%d\n", probes);
return 0;
}