概要：C言語でシンプルなハッシュテーブルのデータ構造を実装する方法を解説します。線形探索と二分探索を簡単に紹介したあと、ハッシュテーブルを設計し実装します。本記事の目的は、ハッシュテーブルの内部は決して恐れるものではなく、一定の制約のもとであればゼロからでも十分簡単に作れることを示すことです。

最近、単語の出現回数を数えるシンプルなプログラムをさまざまな言語で比較する記事を書きました。その中で話題になったことの一つが、C言語の標準ライブラリにはハッシュテーブルというデータ構造が用意されていないという点でした。

これに気づいたときに取れる選択肢はいくつかあります。線形探索を使う、二分探索を使う、誰かが作ったハッシュテーブルの実装を持ってくる、自分でハッシュテーブルを書く、あるいはより高機能な言語に乗り換える、といった具合です。ここではまず線形探索と二分探索をざっと見てから、自分でハッシュテーブルを書く方法を学びます。これはC言語ではしばしば必要になることですが、他の言語を使っていてもカスタムのハッシュテーブルが必要になった場合に役立つこともあります。

線形探索

最もシンプルな選択肢は、線形探索を使って配列を先頭から順に走査することです。要素数が少なければ、これは決して悪い戦略ではありません。私が文字列を使って行った簡単な比較では、7件程度まではハッシュテーブルのルックアップよりも高速でした（ただし、よほど性能にシビアなプログラムでなければ、20〜30件程度までなら十分実用的でしょう）。線形探索なら、新しい要素を配列の末尾に追加するだけで済みます。この方式では、平均でnum_keys/2個の要素を比較することになります。

たとえば、次の配列（各要素は文字列のキーとそれに対応する整数値を持ちます）からキーbobを探す場合を考えてみましょう。

やり方は単純で、先頭（インデックス0のfoo）から順にキーを比較していきます。探しているキーと一致すればそこで終了です。一致しなければ次のスロットに進みます。bobを探す場合、5ステップ（インデックス0から4まで）かかります。

これをC言語で書くと次のようになります（配列の各要素が文字列キーと整数値を持つと仮定しています）。

typedef struct {
    char* key;
    int value;
} item;

item* linear_search(item* items, size_t size, const char* key) {
    for (size_t i=0; i<size; i++) {
        if (strcmp(items[i].key, key) == 0) {
            return &items[i];
        }
    }
    return NULL;
}

int main(void) {
    item items[] = {
        {"foo", 10}, {"bar", 42}, {"bazz", 36}, {"buzz", 7},
        {"bob", 11}, {"jane", 100}, {"x", 200}};
    size_t num_items = sizeof(items) / sizeof(item);

    item* found = linear_search(items, num_items, "bob");
    if (!found) {
        return 1;
    }
    printf("linear_search: value of 'bob' is %d\n", found->value);
    return 0;
}

二分探索

もう一つのシンプルなアプローチは、要素をキーでソートされた配列に入れておき、二分探索で比較回数を減らす方法です。これは紙の辞書で単語を引くときのやり方に近いものです。

C言語の標準ライブラリにはbsearch関数さえ用意されています。二分探索は、たとえ数百件の要素があってもそれなりに高速です（ハッシュテーブルほどではないにせよ）。平均でlog(num_keys)個の要素を比較するだけで済むからです。ただし、配列はソートされた状態を保つ必要があるため、要素を挿入する際には後続の要素をずらす必要があり、挿入には依然として平均でnum_keys/2回の操作がかかります。

再びbobを探す場合を考えます（今度はあらかじめソートされた配列です）。

二分探索では、まず真ん中（buzz）から始めます。そこにあるキーが探しているものより大きければ下半分で、小さければ上半分で同じ処理を繰り返します。今回の例ではインデックス3、1、2の順に3ステップで見つかります。5ステップだった線形探索に対して3ステップで済むわけで、要素数が増えるほど線形探索に対する優位性は（指数関数的に）大きくなります。

これをC言語で書くと次のようになります（bsearchを使う場合と使わない場合）。item構造体の定義は上と同じです。

int cmp(const void* a, const void* b) {
    item* item_a = (item*)a;
    item* item_b = (item*)b;
    return strcmp(item_a->key, item_b->key);
}

item* binary_search(item* items, size_t size, const char* key) {
    if (size + size < size) {
        return NULL; // size too big; avoid overflow
    }
    size_t low = 0;
    size_t high = size;
    while (low < high) {
        size_t mid = (low + high) / 2;
        int c = strcmp(items[mid].key, key);
        if (c == 0) {
            return &items[mid];
        }
        if (c < 0) {
            low = mid + 1; // eliminate low half of array
        } else {
            high = mid;    // eliminate high half of array
        }
    }
    // Entire array has been eliminated, key not found.
    return NULL;
}

int main(void) {
    item items[] = {
        {"bar", 42}, {"bazz", 36}, {"bob", 11}, {"buzz", 7},
        {"foo", 10}, {"jane", 100}, {"x", 200}};
    size_t num_items = sizeof(items) / sizeof(item);

    item key = {"bob", 0};
    item* found = bsearch(&key, items, num_items, sizeof(item), cmp);
    if (found == NULL) {
        return 1;
    }
    printf("bsearch: value of 'bob' is %d\n", found->value);

    found = binary_search(items, num_items, "bob");
    if (found == NULL) {
        return 1;
    }
    printf("binary_search: value of 'bob' is %d\n", found->value);
    return 0;
}

注：binary_searchでは、先頭の「サイズが半分を超えていないかのオーバーフロー検査」をなくし、size_tの範囲全体を扱えるようにした方がわずかに良いでしょう。その場合はmidの計算をlow + (high-low)/2に変更します。ただ、教育上の目的でここではこのままにしておきます。最初のオーバーフローチェックがあればバグはないと思いますが、size_tの半分の範囲しか許容していないのは理想的ではありません。とはいえ、64ビット環境で16エクサバイトもの配列を探索することはまずないでしょう！詳しくはNearly All Binary Searches and Mergesorts are Brokenという記事を参照してください。フィードバックをくれたSeth Arnold氏とOlaf Seibert氏に感謝します。

ハッシュテーブル

ハッシュテーブルは一見とっつきにくく感じられるかもしれません。種類も多く、さまざまな最適化が可能です。しかし、シンプルなハッシュ関数と「線形探索（linear probing）」と呼ばれる手法を組み合わせれば、十分実用的なハッシュテーブルを驚くほど簡単に作ることができます。

ハッシュテーブルの仕組みをご存じない方のために、簡単におさらいしておきましょう。ハッシュテーブルは、キー（多くの場合文字列）から対応する値（任意のデータ型）を高速に引き当てるためのコンテナ型データ構造です。内部的には、キーのハッシュ関数によってインデックス付けされた配列に過ぎません。

ハッシュ関数はキーを一見ランダムな数値に変換するもので、同じキーに対しては常に同じ数値を返さなければなりません。たとえば、これから使うハッシュ関数（64ビットのFNV-1a）で上記のキーをハッシュ化すると、次のようになります。

ハッシュを16で割った余りを示したのは、これから16要素の配列から始めるためです。ハッシュ値を配列の要素数に収める必要があり、modulo（剰余）演算で16で割った余りを取ることで、配列のインデックスを0から15の範囲に収めています。

ハッシュテーブルに値を挿入する際は、ハッシュ値を計算して16で割った余りを求め、それを配列のインデックスとして使います。サイズ16の配列であれば、barはインデックス10に、bazzは8に、bobは4に、といった具合に挿入されます。すべての要素をハッシュテーブルの配列に挿入してみましょう（xは後で扱うので一旦除外します）。

値を検索する際は、単にarray[hash(key) % 16]を取り出すだけです。配列サイズが2のべき乗であれば、array[hash(key) & 15]と書くこともできます。要素の順序がもはや意味を持たないことに注目してください。

しかし、2つのキーが（16で割った余りが）同じハッシュ値になったらどうなるでしょうか。ハッシュ関数や配列サイズによっては、これはそれほど珍しいことではありません。たとえば、上記の配列にxを追加しようとすると、そのハッシュを16で割った余りは7になります。しかし、インデックス7にはすでにfooが入っているため、衝突（collision）が発生します。

衝突の対処法にはいくつかあります。伝統的には、一定サイズのハッシュ配列を用意し、衝突が起きたら同じインデックスにハッシュされた値を連結リストで保持する方法がとられてきました。しかし、連結リストは要素を追加するたびに余分なメモリ確保が必要になり、しかもリストをたどる際にはメモリ上に散らばったポインタを追いかけることになるため、現代のCPUでは比較的低速です。

よりシンプルで高速な衝突の解決策が線形探索（linear probing）です。要素を挿入しようとしたスロットにすでに別の要素が入っていれば、単に次のスロットに移動します。次のスロットも埋まっていればさらに次へと進み、空きが見つかるまで続けます。配列の末尾に達したら先頭に折り返します（次のスロットに進む以外にもさまざまな探索方法がありますが、本記事の範囲を超えるので割愛します）。この手法は連結リストよりもはるかに高速です。CPUのキャッシュが次の要素をすでに取得している可能性が高いからです。

「衝突する」x（値200）を追加した後のハッシュテーブルの配列は次のようになります。まずインデックス7を試しますが、そこにはfooが入っているためインデックス8に進みます。しかし8にはbazzが入っているので、さらに9に進みます。9は空いているので、そこに挿入します。

ハッシュテーブルが詰まりすぎてきたら、より大きな配列を確保して要素を移し替える必要があります。要素数が配列サイズに達した場合は言うまでもなく必須ですが、通常はテーブルが半分から4分の3程度埋まった段階で拡張するのが望ましいでしょう。十分早い段階でリサイズしないと、衝突はどんどん頻発し、検索や挿入はどんどん遅くなります。ほぼ満杯になるまで待ってしまうと、実質的に線形探索に戻ったも同然です。

良いハッシュ関数を使えば、この種のハッシュテーブルでは、キーのハッシュ計算にかかる時間に加えて、1回のルックアップあたり平均1回の操作で済みます（とはいえ、キーは多くの場合比較的短い文字列です）。

これでおしまいです！ここから先はまだまだ奥が深く、今回触れたのは表面をなぞったに過ぎません。Big O記法の科学的な分析や、最適な配列サイズ、さまざまな探索手法などにはここでは立ち入りません。そういった詳細に興味があれば、Donald KnuthのTAOCPを読むことをおすすめします！

ハッシュテーブルの実装

この実装のコードはGitHubのbenhoyt/htリポジトリにあるht.hとht.cで確認できます。なお、すべてのコードは寛容なMITライセンスで公開されています。

Code Review Stack Exchangeで有益なフィードバックをいただき、いくつかの細かな問題を修正できました。中でも大きかったのは、ht_expandの中でstrdupを呼び出す方法に起因するメモリリークで、こちらで修正済みです。リークはValgrindを使って確認しましたが、もっと早く実行しておくべきでした。Seth Arnold氏からもこの記事の草稿に有益なフィードバックをいただきました。皆さん、ありがとうございます！

API設計

まずはどのようなAPIが欲しいかを考えてみましょう。ハッシュテーブルの作成と破棄、指定したキーに対応する値の取得、キーに対する値の設定、要素数の取得、そして要素の反復処理が必要です。最大効率のAPIを目指しているわけではなく、比較的シンプルに実装できるものを目指します。

何度か試行錯誤した結果、次のような関数と構造体に落ち着きました（ht.hを参照）。

// Hash table structure: create with ht_create, free with ht_destroy.
typedef struct ht ht;

// Create hash table and return pointer to it, or NULL if out of memory.
ht* ht_create(void);

// Free memory allocated for hash table, including allocated keys.
void ht_destroy(ht* table);

// Get item with given key (NUL-terminated) from hash table. Return
// value (which was set with ht_set), or NULL if key not found.
void* ht_get(ht* table, const char* key);

// Set item with given key (NUL-terminated) to value (which must not
// be NULL). If not already present in table, key is copied to newly
// allocated memory (keys are freed automatically when ht_destroy is
// called). Return address of copied key, or NULL if out of memory.
const char* ht_set(ht* table, const char* key, void* value);

// Return number of items in hash table.
size_t ht_length(ht* table);

// Hash table iterator: create with ht_iterator, iterate with ht_next.
typedef struct {
    const char* key;  // current key
    void* value;      // current value

    // Don't use these fields directly.
    ht* _table;       // reference to hash table being iterated
    size_t _index;    // current index into ht._entries
} hti;

// Return new hash table iterator (for use with ht_next).
hti ht_iterator(ht* table);

// Move iterator to next item in hash table, update iterator's key
// and value to current item, and return true. If there are no more
// items, return false. Don't call ht_set during iteration.
bool ht_next(hti* it);

このAPI設計について、いくつか補足しておきます。

• シンプルさを優先し、C言語標準のNUL終端文字列を使います。もっと効率的な文字列の扱い方もあることは承知していますが、Cの標準ライブラリに合わせる形にしています。
• ht_set関数は（初めて挿入する場合）キーを確保してコピーします。通常、呼び出し元にこの処理や、キーのメモリを保持し続けることを意識させたくないからです。なお、ht_setは複製されたキーへのポインタを返します。これは主に「メモリ不足」のエラー通知として使われ、失敗時にはNULLを返します。
• 一方、ht_setは値をコピーしません。値のポインタがハッシュテーブルの存続期間中有効であることを保証するのは呼び出し元の責任です。
• 値はNULLであってはなりません。これによりht_getのシグネチャが少しシンプルになります。NULLの値と、そもそも設定されていない値とを区別する必要がなくなるからです。
• ht_length関数は厳密には必須ではありません。テーブルを反復処理すれば要素数は分かります。しかし、それは少々面倒で（しかも遅い）ので、ht_lengthを用意しておくと便利です。
• 反復処理の実装方法はいくつか考えられます。明示的なイテレータ型を用意してwhileループで回す方式は、C言語ではシンプルで自然に感じられます（下の例を参照）。ht_iteratorが返すのはポインタではなく値そのもので、効率が良いうえ、呼び出し元が解放する必要がないようにしています。
• ハッシュテーブルから要素を削除するht_removeは用意していません。線形探索では「穴」が残るため、削除は少し厄介なのです。ただ、ハッシュテーブルを使う際に要素の削除が必要になることはそれほど多くないので、今回はあえて省き、読者の課題として残しておきます。

デモプログラム

以下は、APIのすべての関数を使ったシンプルなプログラム（demo.c）です。標準入力から空白区切りの単語を読み込み、ユニークな単語ごとの出現回数を数えて結果を出力します（ハッシュテーブルの反復順序は未定義なので、出力順は不定です）。最後にユニークな単語の総数を表示します。

// Example:
// $ echo 'foo bar the bar bar bar the' | ./demo
// foo 1
// bar 4
// the 2
// 3

void exit_nomem(void) {
    fprintf(stderr, "out of memory\n");
    exit(1);
}

int main(void) {
    ht* counts = ht_create();
    if (counts == NULL) {
        exit_nomem();
    }

    // Read next word from stdin (at most 100 chars long).
    char word[101];
    while (scanf("%100s", word) != EOF) {
        // Look up word.
        void* value = ht_get(counts, word);
        if (value != NULL) {
            // Already exists, increment int that value points to.
            int* pcount = (int*)value;
            (*pcount)++;
            continue;
        }

        // Word not found, allocate space for new int and set to 1.
        int* pcount = malloc(sizeof(int));
        if (pcount == NULL) {
            exit_nomem();
        }
        *pcount = 1;
        if (ht_set(counts, word, pcount) == NULL) {
            exit_nomem();
        }
    }

    // Print out words and frequencies, freeing values as we go.
    hti it = ht_iterator(counts);
    while (ht_next(&it)) {
        printf("%s %d\n", it.key, *(int*)it.value);
        free(it.value);
    }

    // Show the number of unique words.
    printf("%d\n", (int)ht_length(counts));

    ht_destroy(counts);
    return 0;
}

それでは、ハッシュテーブルの実装（ht.c）を見ていきましょう。

作成と破棄

新しいハッシュテーブルの確保は比較的単純です。配列の初期容量は16（capacityに格納）から始め、拡張するまでに最大8件まで保持できます。確保は2回行われ、1回はハッシュテーブル構造体自体、もう1回はエントリ配列のためです。エントリ配列にはcallocを使っている点に注目してください。これにより、開始時にすべてのキーがNULLであることが保証され、すべてのスロットが空であることを意味します。

ht_destroy関数はこのメモリを解放しますが、それだけでなく、途中で確保された複製されたキーのメモリも解放します（詳細は後述します）。

// Hash table entry (slot may be filled or empty).
typedef struct {
    const char* key;  // key is NULL if this slot is empty
    void* value;
} ht_entry;

// Hash table structure: create with ht_create, free with ht_destroy.
struct ht {
    ht_entry* entries;  // hash slots
    size_t capacity;    // size of _entries array
    size_t length;      // number of items in hash table
};

#define INITIAL_CAPACITY 16  // must not be zero

ht* ht_create(void) {
    // Allocate space for hash table struct.
    ht* table = malloc(sizeof(ht));
    if (table == NULL) {
        return NULL;
    }
    table->length = 0;
    table->capacity = INITIAL_CAPACITY;

    // Allocate (zero'd) space for entry buckets.
    table->entries = calloc(table->capacity, sizeof(ht_entry));
    if (table->entries == NULL) {
        free(table); // error, free table before we return!
        return NULL;
    }
    return table;
}

void ht_destroy(ht* table) {
    // First free allocated keys.
    for (size_t i = 0; i < table->capacity; i++) {
        free((void*)table->entries[i].key);
    }

    // Then free entries array and table itself.
    free(table->entries);
    free(table);
}

ハッシュ関数

次にハッシュ関数を定義します。これはFNV-1aハッシュアルゴリズムをC言語で素直に実装したものです。FNVはランダム化されたハッシュ関数でも暗号論的なハッシュ関数でもないため、攻撃者が衝突の多いキーを作り出して検索を極端に遅くする可能性があります。PythonがFNVの使用をやめたのもこのためです。ただ、今回の用途ではFNVはシンプルで高速なので十分です。

アルゴリズムとしては、FNV-1aはまずハッシュを「オフセット」定数で初期化し、文字列の各バイトについて、ハッシュとバイトのXORを取ってから大きな素数を掛ける、というだけのものです。オフセットと素数は博士号を持つ人々によって慎重に選ばれています。

ここでは64ビット版を使っています。まあ、今どきのコンピュータはほとんど64ビットですし、良さそうに思えたからです。私がそういった博士号を持っていないことはお分かりでしょう :-) 真面目な話、非常に大きなハッシュテーブルを扱う場合に備えて、32ビット版よりは良いだろうと考えました。

#define FNV_OFFSET 14695981039346656037UL
#define FNV_PRIME 1099511628211UL

// Return 64-bit FNV-1a hash for key (NUL-terminated). See description:
// https://en.wikipedia.org/wiki/Fowler–Noll–Vo_hash_function
static uint64_t hash_key(const char* key) {
    uint64_t hash = FNV_OFFSET;
    for (const char* p = key; *p; p++) {
        hash ^= (uint64_t)(unsigned char)(*p);
        hash *= FNV_PRIME;
    }
    return hash;
}

ここで詳細な分析は行いませんが、入力中のユニークな単語から作成されたハッシュテーブルの平均プローブ長を表示する小さな統計プログラムを用意しました。私たちが使っているFNV-1aハッシュアルゴリズムは、50万語の英単語リスト（平均プローブ長1.40）でも、word1、word2といった非常に似通った50万件のキーのリスト（平均プローブ長1.38）でも、良好に機能しているようです。

興味深いことに、FNV-1アルゴリズム（FNV-1aと同じですが、XORの前に掛け算を行うもの）を試したところ、英単語では依然として平均プローブ長1.43と良好でしたが、似通ったキーでは平均プローブ長が5.02と非常に悪化しました。したがって、私の簡単なテストではFNV-1aが明らかに優れていました。

取得

次にht_get関数を見てみましょう。まずハッシュ値を計算し、capacity（エントリ配列のサイズ）で割った余りを求めます。これはcapacity - 1とのAND演算で行っています。ANDが使えるのは、後述するように、シンプルさを優先して配列サイズを常に2のべき乗に保っているからです。

その後、空きスロットが見つかるまでループします。空きが見つかったということは、キーが見つからなかったということです。空でない各スロットでは、strcmpを使ってそのスロットのキーが探しているキーかどうかを確認します（衝突がなければ最初のスロットで見つかります）。違っていれば次のスロットに進みます。

void* ht_get(ht* table, const char* key) {
    // AND hash with capacity-1 to ensure it's within entries array.
    uint64_t hash = hash_key(key);
    size_t index = (size_t)(hash & (uint64_t)(table->capacity - 1));

    // Loop till we find an empty entry.
    while (table->entries[index].key != NULL) {
        if (strcmp(key, table->entries[index].key) == 0) {
            // Found key, return value.
            return table->entries[index].value;
        }
        // Key wasn't in this slot, move to next (linear probing).
        index++;
        if (index >= table->capacity) {
            // At end of entries array, wrap around.
            index = 0;
        }
    }
    return NULL;
}

設定

ht_set関数は少しだけ複雑です。要素が多すぎる場合にテーブルを拡張する必要があるからです。今回の実装では、テーブルが半分まで埋まったら容量を2倍にします。これはメモリをやや無駄にしますが、実装を非常にシンプルに保てます。

まずはht_set関数本体です。必要に応じてテーブルを拡張し、その後要素を挿入するだけです。

const char* ht_set(ht* table, const char* key, void* value) {
    assert(value != NULL);
    if (value == NULL) {
        return NULL;
    }

    // If length will exceed half of current capacity, expand it.
    if (table->length >= table->capacity / 2) {
        if (!ht_expand(table)) {
            return NULL;
        }
    }

    // Set entry and update length.
    return ht_set_entry(table->entries, table->capacity, key, value,
                        &table->length);
}

処理の核心はヘルパー関数ht_set_entryにあります（ループがht_getのものと非常によく似ていることに注目してください）。plength引数が非NULLであれば、ht_setから呼ばれたということなので、キーを確保してコピーし、要素数を更新します。

// Internal function to set an entry (without expanding table).
static const char* ht_set_entry(ht_entry* entries, size_t capacity,
        const char* key, void* value, size_t* plength) {
    // AND hash with capacity-1 to ensure it's within entries array.
    uint64_t hash = hash_key(key);
    size_t index = (size_t)(hash & (uint64_t)(capacity - 1));

    // Loop till we find an empty entry.
    while (entries[index].key != NULL) {
        if (strcmp(key, entries[index].key) == 0) {
            // Found key (it already exists), update value.
            entries[index].value = value;
            return entries[index].key;
        }
        // Key wasn't in this slot, move to next (linear probing).
        index++;
        if (index >= capacity) {
            // At end of entries array, wrap around.
            index = 0;
        }
    }

    // Didn't find key, allocate+copy if needed, then insert it.
    if (plength != NULL) {
        key = strdup(key);
        if (key == NULL) {
            return NULL;
        }
        (*plength)++;
    }
    entries[index].key = (char*)key;
    entries[index].value = value;
    return key;
}

ヘルパー関数ht_expandはどうなっているでしょうか。現在の容量の2倍の新しいエントリ配列を確保し、plengthにNULLを渡してht_set_entryを使ってエントリをコピーします。ハッシュ値自体は同じでも、容量が変わったため（インデックスはハッシュ値を容量で割った余りなので）インデックスは異なるものになります。

// Expand hash table to twice its current size. Return true on success,
// false if out of memory.
static bool ht_expand(ht* table) {
    // Allocate new entries array.
    size_t new_capacity = table->capacity * 2;
    if (new_capacity < table->capacity) {
        return false;  // overflow (capacity would be too big)
    }
    ht_entry* new_entries = calloc(new_capacity, sizeof(ht_entry));
    if (new_entries == NULL) {
        return false;
    }

    // Iterate entries, move all non-empty ones to new table's entries.
    for (size_t i = 0; i < table->capacity; i++) {
        ht_entry entry = table->entries[i];
        if (entry.key != NULL) {
            ht_set_entry(new_entries, new_capacity, entry.key,
                         entry.value, NULL);
        }
    }

    // Free old entries array and update this table's details.
    free(table->entries);
    table->entries = new_entries;
    table->capacity = new_capacity;
    return true;
}

要素数と反復処理

ht_length関数は取るに足らないものです。要素数はその都度_lengthで更新しているので、それを返すだけです。

size_t ht_length(ht* table) {
    return table->length;
}

最後のピースが反復処理です。イテレータを作成するにはユーザーがht_iteratorを呼び出し、次の要素に進むにはht_nextがtrueを返す間ループで呼び出します。それぞれの定義は次のとおりです。

hti ht_iterator(ht* table) {
    hti it;
    it._table = table;
    it._index = 0;
    return it;
}

bool ht_next(hti* it) {
    // Loop till we've hit end of entries array.
    ht* table = it->_table;
    while (it->_index < table->capacity) {
        size_t i = it->_index;
        it->_index++;
        if (table->entries[i].key != NULL) {
            // Found next non-empty item, update iterator key and value.
            ht_entry entry = table->entries[i];
            it->key = entry.key;
            it->value = entry.value;
            return true;
        }
    }
    return false;
}

考察

以上です。ht.cの実装は、空行やコメントを含めてもわずか約200行です。

注意：これはあくまで学習用のものであり、ライブラリではありません。ぜひいろいろと試してみて、まだ見つかっていないバグがあれば教えてください！十分なテストやエッジケースの確認などをせずにそのまま使うことはおすすめしません。ここで扱っているのは安全ではないC言語だということを忘れないでください。私自身、これを書いている最中に、エントリ配列の確保にcallocではなくmallocを使っていたことに気づきました。これではキーがNULLに初期化されない可能性があったのです。

前述のとおり、実装はシンプルさを優先し、性能についてはそれほど気にしていませんでした。しかし、Goのmap実装と簡単かつ非科学的な性能比較をしたところ、なかなか健闘しています。50万語の英単語では、このC版は検索が約50%遅い一方、挿入は約40%高速でした。

Goの話ついでに言うと、Goのような言語ではカスタムのハッシュテーブルを書くのはさらに簡単です。メモリ確保の失敗への対処や、確保したメモリの解放を気にする必要がないからです。最近、私はGoで同様のハッシュテーブルを実装したcounterパッケージを書きました。

C版でできることは明らかにまだまだたくさんあります。さまざまなテストを行って安全性や信頼性に注力することもできますし、性能に注力してメモリ確保の回数を減らしたり、複製されたキー用に「bump allocator」を使ったり、短いキーを各要素の構造体内に直接格納したりといったことも可能です。メモリ使用量を改善し、毎回サイズを2倍にしないように_ht_expandを調整することもできますし、要素の削除のような機能を追加することもできます。

これを書き終えた後、Bob Nystrom氏の優れたCrafting Interpretersという書籍にハッシュテーブルに関する章があることを思い出しました。彼も似たような設計上の選択をしていますが、その章は本記事よりもはるかに掘り下げた内容です。書き始める前に思い出していたら、おそらくこの記事は書いていなかったでしょう！

いずれにせよ、この記事が何かの役に立ったり、興味を持っていただけたりしていれば幸いです。バグを見つけたり、フィードバックがあればぜひ教えてください。Hacker News、programming Reddit、Lobstersでのディスカッションもご覧いただけます。