はじめに
C言語の標準ライブラリには、連想配列は存在しない。
一般的な連想配列の実装にはハッシュテーブルや平衡二分探索木があるが、それぞれ以下の欠点がある。
- ハッシュテーブル
- 格納するデータが少ない場合でも、ハッシュ関数が返しうるデータの種類数を長さとする配列が必要になる
- 格納された要素の走査がしにくい
- 平衡二分探索木
- 実装が面倒・複雑で、エンバグしやすい
そこで、本記事では、要素の走査がしやすく、かつ簡単に実装できる連想配列を提案する。
こんなときに便利！
- 連想配列に格納された要素を走査して処理を行いたいとき
- 格納する要素数に合ったメモリ消費量で要素を管理したいとき
アルゴリズム
二分木を用意する。
非負整数のキーを受け取る。
ニ分木の根からスタートし、以下の法則で木を降りていく。
その際、無いノードは作成する。
- 現在のキーが
0である場合、現在居るノードに要素を格納する - そうでない場合、現在のキーを2で割った値を新しいキーとして、子に移動する
- 現在のキーを2で割った余りが
0の場合は、左の子に移動する - 現在のキーを2で割った余りが
1の場合は、右の子に移動する
- 現在のキーを2で割った余りが
木のノードとそこに要素を格納するキーの関係は、以下のようになる。
このアルゴリズムではキーを非負整数としているが、キーが負の整数の場合は符号を反転して別の木に格納することで、一般の整数に拡張できる。
実装例
/* 連想配列の実装に用いる */
#include <stdlib.h>
/* デモ用 (連想配列の実装には用いない) */
#include <stdio.h>
#include <string.h>
/* 木のノードを表す構造体 */
struct map_node {
/* 連想配列に格納するデータ (今回は整数) */
int value;
/* ノードの子へのポインタ */
struct map_node* next[2];
};
/*
木の根を表すポインタへのポインタ node と、要素を取得するキー key を受け取る。
キーに対応するデータへのポインタを返す。
*/
int* map_get(struct map_node** node, unsigned int key) {
/* ノードが無い場合は、作成する */
if (*node == NULL) {
/* ノードを作成し、データを 0、子へのポインタを NULL で初期化する */
*node = calloc(1, sizeof(**node));
/* 作成に失敗した場合、終了する */
if (*node == NULL) exit(1);
}
/* キーが 0 なら、このノードに格納されているデータを返す */
if (key == 0) {
return &(*node)->value;
}
/* 子に移動する */
return map_get(&(*node)->next[key & 1], key >> 1);
}
/*
以下の形式のクエリを受け付ける。
set x y : キー x に値 y を格納する
get x : キー x に対応する値を出力する
exit : 終了する
*/
int main(void) {
struct map_node* map = NULL;
char query[8];
while (scanf("%7s", query) == 1) {
if (strcmp(query, "set") == 0) {
unsigned int key;
int value;
if (scanf("%u%d", &key, &value) != 2) return 1;
*map_get(&map, key) = value;
} else if (strcmp(query, "get") == 0) {
unsigned int key;
if (scanf("%u", &key) != 1) return 1;
printf("%d\n", *map_get(&map, key));
} else if (strcmp(query, "exit") == 0) {
break;
}
}
return 0;
}
効率
キーに対応するノードを特定するためにたどるノードの数は、キーのビット数程度である。
よって、キーの最大値を $N$ として、$O(\log N)$ でキーに対応するノードを特定できる。
キーに対応するデータのポインタを取得し、それを用いて読み書きを行う方式なので、データの取得も設定も探索コストは同じである。
一方、キーとノードの関係の図を見るとわかる通り、このアルゴリズムではキーに対応しないノードが発生する。
そのため、全てのノードにデータを格納する平衡二分探索木よりはメモリ効率が悪いと考えられる。
格納されている要素の走査
このアルゴリズムでは要素をニ分木に格納するため、DFSなどにより木のノードを走査することで、要素を走査できる。
ただし、走査の順番は素直な昇順・降順などにはならない。
また、キーに対応しないノードや、まだ対応するキーを用いたアクセスがされていないノードもあるため、別途 valid フラグを用意したり、使わない (無効な) 値で初期化したりするなど、有効な値が格納されたノードとそうでないノードを見分けられるようにしておかなければならない。
使用例
ネタバレ注意！
以下にこのアルゴリズムを使用した提出へのリンクを示す。