ハッシュテーブル考

　このごろ、ハッシュテーブルの実装について考えていました。
　それはひとつに「Common Lispでいつも使っているハッシュテーブルってどうなっているの？」という疑問があり、もうひとつには「オレオレLispを実装するときホスト言語によってはハッシュテーブルがないことがあり、自分で実装する必要がある」という思いがありました。

　そこでハッシュテーブルってどのように実装されているのだろうということをちょっと調べてみた、というわけです。

そもそもハッシュテーブルとは

　じつはここまでで言っていた「ハッシュテーブル」と、データ構造の本に載っている「ハッシュテーブル」は異なります。

　前者の「ハッシュテーブル」は、キーとそれに対応する値を格納するための、最近の言語ではデフォルトで提供されているデータ構造です。こんなやつ:

>>> dic = {}
>>> dic
{}
>>> dic['test'] = 42
>>> dic
{'test': 42}

「連想配列」(Perl)、「ハッシュマップ（あるいはマップ）」(Java、JVM系言語)、「ディクショナリ」(Python)、などと呼ばれるものです。以降この記事ではPythonに倣ってディクショナリと呼ぶことにします。

　後者の「ハッシュテーブル」は、格納可能な値の数が大きいが実際に格納される値の数はそれほど大きくない、というようなデータを効率的に格納するためのデータ構造です。データ構造とアルゴリズム、というような書籍や大学の講義で、見たことがある人もいると思います。以降この記事ではハッシュテーブルと呼ぶことにします。

　前者のハッシュテーブルの実装に際して後者のハッシュテーブルを用いるため、どちらもハッシュテーブルと呼ばれるのですかね。

　なので、冒頭で考えていた内容はこういうことになります:

ディクショナリってどうやって実装するんだろう？

　まずは、その実装に必要な概念であるハッシュテーブルのことを思い出すことにします。

ハッシュテーブル

　ハッシュテーブルは、格納可能な値の数が大きいが、実際に格納される値はそれほど多くないようなデータを格納するのに適したデータ構造です。格納対象の値をハッシュ値という整数値に変換し、事前に用意した配列のハッシュ値の位置に値を格納する、ということをします。これにより値の取り出しの計算量がO(1)と非常に効率がよいです。

　このハッシュテーブルでは、ハッシュ値を計算するための関数「ハッシュ関数」をどのように選ぶかが、効率を左右します。異なる値のハッシュ値が同一になってしまった場合、重複をうまく処理する必要があるため、なるべくダブらず値の格納位置が配列内に均等にバラけるようなハッシュ関数を選ぶ必要があるのです。

　単純な例として、整数を格納するハッシュテーブルを考えます。ハッシュ関数はテーブル長の剰余を取る関数を選びました。

#define TABLE_SIZE 256;

static int table[TABLE_SIZE];

int hash(int v) {
  return v % TABLE_SIZE;
}

　このテーブルに値を格納するときは、こうします:

int main(void) {
  int value = 42;
  int hash_code = hash(value);
  table[hash_code] = value;

  return 0;
}

　値の取得は、こうです+

int main(void) {
  int value = 42;
  int hash_code = hash(value);
  printf("%d\n", table[hash_code]);

  return 0:
}

　ちなみにこの方法ではハッシュ値が同じ別の値があったときに、別の値で元の値が上書きされてしまいます（ハッシュ値が衝突する、といいます）。その対策は二つ（配列の要素をリストにする、すぐ隣に格納する）ありますがここでは詳しく書きません。こちらの本を参照してください。

みんなのデータ構造（紙書籍+電子書籍）www.lambdanote.com

ディクショナリだ！

　上のハッシュテーブルの例はキーと値が同じなのでつまらない例でした。これを使ってディクショナリを実装するにはどうしたらよいでしょう。ハッシュ値の衝突時、同一ハッシュ値の異なる値を探索するため、値にはキーそのものが入っていなければなりません。いっぽうでディクショナリでは下記のように、キーに対して異なる値を格納するのが目的でした:

>>> dic = {}
>>> dic
{}
>>> dic['test'] = 42
>>> dic
{'test': 42}

　どうすればよいのかわからなかったので（ここで数日悩んでしまったので）、Pythonのディクショナリの実装を覗き見てみました。

　値にハッシュ値とキー値を一緒に入れてしまいましょう、が答えでした。

　したがって、最近開発を始めたばかりのC言語によるLisp実装のシンボル-値テーブルは、調査の結果このようになりました:

int hash(const char* name);

typedef struct {
  int hash;
  WlSymbol* symbol;
} WlSymTableEntry;

typedef struct {
  WlSymTableKey** key_table;
  WlObject** values;
  int item_count;
  int not_null_count;
  int d;  // hash_table.length = 2^d
} WlSymTable;

https://github.com/t-sin/wl/blob/066e12919810d7c7aa31ce713d52690ec021a86b/wlsym.h より

余談

ところでPythonのディクショナリの実装、上でいうWlSymTableEntryにそのまま値を持つcombinedな形と、上のWlObject** valuesのように別で値を持つsplitedな形と二種あるようです。このドキュメントを見るとキャッシュヒット率が関係していそうな感じなのですが、英語力が低すぎてよくわからない…。

https://github.com/python/cpython/blob/master/Objects/dictnotes.txt

octahedron

LemとSKKとCommon Lispでたたかうプログラマのブログ

ハッシュテーブル考

そもそもハッシュテーブルとは

ハッシュテーブル

ディクショナリだ！

余談