2026-10-27
probe_order.c
#include <stdio.h>
void show(const int* keys, int n, int size) {
int table[8] = {0};
for (int i = 0; i < n; i++) {
int h = keys[i] % size;
while (table[h] != 0)
h = (h + 1) % size;
table[h] = keys[i];
}
for (int h = 0; h < size; h++)
if (table[h] != 0)
printf("%d", table[h]);
printf("\n");
}
int main(void) {
int keys[] = {6, 9, 2};
show(keys, 3, 4);
show(keys, 3, 8);
}
これは何を出力するでしょうか?
Answer
962 と 926 の2行です。
キーを置く枠は keys[i] % size で決まり、そこが埋まっていれば次の枠へ進みます。走査は枠の番号の順なので、出力は入れた順ではなく、各キーが落ちた枠の順に並びます。
大きさ4の表では、6 が枠2、9 が枠1に入ります。2 も枠2を指しますが、6 が使っているので枠3へずれます。枠1から3の順に読むので 962 です。
大きさ8の表では、6 が枠6、9 が枠1、2 が枠2で、ぶつかるキーはありません。枠の順に読むと 926 になります。キーも入れる順も同じなのに、表の大きさが変わると走査の順も変わります。表が埋まってきて大きな表へ移し替えるときにも、同じことが起きます。