hash vs trie

• ref:http://www.kt.rim.or.jp/~kbk/zakkicho/08/zakkicho0804b.html#D20080411-4

hash table vs trie というネタは数年前に、工藤さんがやられてます。

• ref:http://web.archive.org/web/20060623192948/http://chasen.org/~taku/blog/archives/2003/10/cdb_vs_darts_1.html

cdb が hash database、darts が trie。
まぁ、このへんは実装とキー集合の特性に依存するのでなんとも。一般的には大差ないんじゃないですかね。まぁ、ルックアップだけじゃなくて要素追加のコストとかも考えないといけないだろうし。