C++で直接アドレス指定テーブルを実装する方法｜O(1)の挿入・検索・削除

この記事では、C++を使って直接アドレス指定テーブル（Direct Addressing Table）を実装する方法を解説します。直接アドレス指定テーブルは、各要素が普遍集合 S = {0, 1, ..., n−1} のいずれかのキーを持ち、n がそれほど大きくなく、すべてのキーが一意である場合に有効なデータ構造です。キーをそのまま配列の添字として扱うため、挿入・検索・削除をすべて O(1) の時間で行えるのが最大の特徴です。

基本となる操作と擬似コード

直接アドレス指定テーブルでは、次の3つの基本操作を定義します。

Begin
    insert():
      テーブル変数 word と key を引数として受け取る。
      T[ x.key ] = x （x はキーの値）
    delete():
      テーブル変数 word と key を引数として受け取る。
      T[ x.key ] = tab(0, "")  // 空スロットで上書き
    search():
      T[key] を返す
End

C++での実装例

以下は、メニュー形式で挿入・削除・検索を試せる完全なサンプルプログラムです。テーブルのサイズは 65536 とし、空のスロットは tab(0, "") で表しています。

#include<iostream>
#include<cstdlib>
#include<string>
#include<cstdio>
using namespace std;

struct tab {  // テーブルの変数宣言
    string word;
    int key;
    tab()
    {}
    tab(int k, string w) // 変数を初期化するコンストラクタ
    {
        word = w;
        key = k;
    }
};

void INSERT(tab T[], tab x) {
    T[ x.key ] = x;
}

void DELETE(tab T[], tab x) {
    T[ x.key ] = tab(0, "");
}

tab SEARCH(tab T[], int key) {
    return T[ key ];
}

int main() {
    int i, k, c;
    string str;
    tab T[65536]; // テーブルのサイズを初期化
    tab x;
    for(i = 0; i < 65536; i++)
        T[i] = tab(0,"");

    while (1) {
        cout<<"1.キーに要素を挿入する"<<endl;
        cout<<"2.テーブルから要素を削除する"<<endl;
        cout<<"3.テーブルから要素を検索する"<<endl;
        cout<<"4.終了"<<endl;
        cout<<"選択してください: ";
        cin>>c;
        switch(c) {
            case 1: {
                string str1 = "";
                cout<<"キー値を入力してください: ";
                cin>>k;
                cout<<"挿入する文字列を入力してください: ";
                cin.ignore();
                getline(cin, str);
                INSERT(T, tab(k, str));
                break;
            }
            case 2:
                cout<<"削除する要素のキーを入力してください: ";
                cin>>k;
                x = SEARCH(T, k);
                DELETE(T, x);
                break;
            case 3:
                cout<<"検索する要素のキーを入力してください: ";
                cin>>k;
                x = SEARCH(T, k);
                if (x.key == 0) {
                    cout<<"そのキーには要素が挿入されていません"<<endl;
                    continue;
                }
                cout<<"キー "<<k<<" の要素 -> ";
                cout<<"\""<<x.word<<"\""<<endl;
                break;
            case 4:
                exit(1);
            default:
                cout<<"無効な選択です"<<endl;
        }
    }
    return 0;
}

実行結果

1.キーに要素を挿入する
2.テーブルから要素を削除する
3.テーブルから要素を検索する
4.終了
選択してください: 1
キー値を入力してください: 1
挿入する文字列を入力してください: hi
1.キーに要素を挿入する
2.テーブルから要素を削除する
3.テーブルから要素を検索する
4.終了
選択してください: 1
キー値を入力してください: 2
挿入する文字列を入力してください: tutorials
1.キーに要素を挿入する
2.テーブルから要素を削除する
3.テーブルから要素を検索する
4.終了
選択してください: 1
キー値を入力してください: 3
挿入する文字列を入力してください: point
1.キーに要素を挿入する
2.テーブルから要素を削除する
3.テーブルから要素を検索する
4.終了
選択してください: 3
検索する要素のキーを入力してください: 1
キー 1 の要素 -> "hi"
1.キーに要素を挿入する
2.テーブルから要素を削除する
3.テーブルから要素を検索する
4.終了
選択してください: 3
検索する要素のキーを入力してください: 4
そのキーには要素が挿入されていません
1.キーに要素を挿入する
2.テーブルから要素を削除する
3.テーブルから要素を検索する
4.終了
選択してください: 2
削除する要素のキーを入力してください: 1
1.キーに要素を挿入する
2.テーブルから要素を削除する
3.テーブルから要素を検索する
4.終了
選択してください: 3
検索する要素のキーを入力してください: 1
そのキーには要素が挿入されていません
1.キーに要素を挿入する
2.テーブルから要素を削除する
3.テーブルから要素を検索する
4.終了
選択してください: 4

計算量と留意点

• 時間計算量： 挿入・検索・削除はいずれも配列への直接アクセスのみで行われるため、最悪でも O(1) です。
• 空間計算量： キーの取り得る範囲全体（この例では 65536 個）分の領域をあらかじめ確保する必要があるため、O(U) のメモリを消費します。
• 適用条件： キーが非負の整数で、範囲が比較的小さい場合に適しています。キーの範囲が広い場合や疎な場合は、ハッシュテーブルの方がメモリ効率に優れています。
• 空スロットの扱い： サンプルコードでは key == 0 を「要素が存在しない」ことの目印として利用しています。