Namaran

Code daily. Without assist.

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 になります。キーも入れる順も同じなのに、表の大きさが変わると走査の順も変わります。表が埋まってきて大きな表へ移し替えるときにも、同じことが起きます。