Show where a simple hash function sends each key, and which keys collide.
What to build
A picture of a hash table with chaining: every bucket and the keys in it.
Requirements
- Use the hash function
key % m. - Print one line for each bucket, from 0 to
m - 1: the bucket number, a colon, and its keys in the order they arrived. - Print
-for a bucket with no keys.
Input
The first line has m and n. The second line has the n keys, which are all different.
Output
m lines, such as 0: 10 5 or 1: -.
Constraints
1 ≤ m ≤ 20, 1 ≤ n ≤ 100, and each key is from 0 to 10000.
Example
Input:
5 4
10 17 24 5
Output:
0: 10 5
1: -
2: 17
3: -
4: 24
Why it works
The remainder after dividing by m is always from 0 to m - 1, so every key gets a valid bucket. Keys that leave the same remainder share a bucket, and that is a collision.
Examples
Example 1 · Input
5 4 10 17 24 5
Expected output
0: 10 5 1: - 2: 17 3: - 4: 24
Example 2 · Input
3 3 3 6 9
Expected output
0: 3 6 9 1: - 2: -
Hints
Hint 1
The bucket of a key is key % m.
Hint 2
For each bucket in turn, go through the keys in the order they came and print the ones that belong to it.
Solution
Show one correct solution (try it yourself first)
#include <stdio.h>
int main(void) {
int m, n, keys[100];
scanf("%d %d", &m, &n);
for (int i = 0; i < n; i++) scanf("%d", &keys[i]);
for (int b = 0; b < m; b++) {
int any = 0;
printf("%d:", b);
for (int i = 0; i < n; i++) {
if (keys[i] % m == b) {
printf(" %d", keys[i]);
any = 1;
}
}
if (!any) printf(" -");
printf("\n");
}
return 0;
}