C/C++のデータ構造

C・C++のハッシュテーブル（hash table）

このレッスンでは、Cで自作したハッシュテーブルとC++のstd::unordered_mapで、各単語が何回出てくるかを数えます。

はじめに

ハッシュテーブル（hash table）は、ハッシュ関数（hash function）で各キーを格納場所（バケット、bucket）のインデックスに変えることで、検索、追加、削除をとても速く行います。異なる2つのキーが同じバケットに入ることを衝突（collision）と呼び、チェイン法（chaining）やオープンアドレス法（open addressing）などで対処する必要があります。

大切なポイント

操作を書く前に、データ構造で常に成り立つべき条件（不変条件、invariant）を決めましょう。
空のとき、満杯のとき、メモリ確保に失敗したときもきちんと処理しましょう。
各操作の計算量とメモリ管理を、あわせて評価しましょう。

動きで理解する

キーを入力して保存または検索します。キーはハッシュでバケット番号に変換されるので、プログラムは正しいバケットへ直接進みます。

CとC++のコード例

実行 →

main.c

#include <stdio.h>
#include <string.h>

typedef struct Item {
    const char *key;
    int count;
    struct Item *next;
} Item;

unsigned hash(const char *text) {
    unsigned value = 5381;
    while (*text) {
        value = value * 33u ^ (unsigned char)*text++;
    }
    return value % 5;
}

int main(void) {
    const char *words[] = {"c", "cpp", "c"};
    Item items[2] = {{"c", 0, NULL}, {"cpp", 0, NULL}};
    Item *buckets[5] = {0};

    for (int index = 0; index < 2; ++index) {
        unsigned bucket = hash(items[index].key);
        items[index].next = buckets[bucket];
        buckets[bucket] = &items[index];
    }
    for (int index = 0; index < 3; ++index) {
        Item *item = buckets[hash(words[index])];
        for (; item; item = item->next) {
            if (strcmp(item->key, words[index]) == 0) {
                ++item->count;
                break;
            }
        }
    }
    printf("c=%d cpp=%d\n", items[0].count, items[1].count);
}

実行結果

c=2 cpp=1

C++

実行 →

main.cpp

#include <iostream>
#include <string>
#include <unordered_map>

int main() {
    std::unordered_map<std::string, int> counts;
    for (const std::string word : {"c", "cpp", "c"}) {
        ++counts[word];
    }
    std::cout << "c=" << counts["c"]
              << " cpp=" << counts["cpp"] << '\n';
}

実行結果

c=2 cpp=1

CとC++の比較

Cのhash関数は文字列の文字から値を計算し、5で割った余りで5つのバケットのどれかを選びます。各バケットは連結リストなので、衝突した単語は同じバケットの中につながります。Cの例はバケットの仕組みに集中するため、いくつかの決まった単語だけを使っています。C++のstd::unordered_mapはノードを自分で管理し、必要に応じて大きくなり、どんな文字列でもキーにできます。

データ（struct）と操作は分かれていて、メモリは手作業で確保・解放します。

C++

クラスとコンテナが、データの正しさを守り、リソースを自分で管理します。

発展問題

両方のバージョンを実行し、コードを書き換えて、それぞれの言語がもたらす安全性の違いを観察しましょう。

空の状態と、容量の上限に達したときのテストを追加しましょう。
メモリを解放する処理を書き、メモリリークがないか確認しましょう。
標準ライブラリの対応するコンテナと計算量を比べましょう。

チャレンジで練習する

このレッスンの内容を使って実際の問題を解きましょう。各チャレンジはブラウザで動き、すぐにテストされ、AI のレビューも受けられます。

すべてのチャレンジ