>>32
BST はバイナリサーチツリー、2分探索木ってやつ。

ハッシュテーブルのサイズが1万ってことは
それにリスト垂らしてて 2000万 とかなら
一つのテーブルに 2000 もの長さのリストがあって
それを線形探索してるのか? 平均1000ぐらいの比較?

BST なら 2000万 の要素でも 24,5回の比較で探索できますよね。
チェインに1000個の要素の BST なら 10回ぐらい。

BST の実装法は探せばいっぱいでてくるはず。