>>26
オープンアドレス法?
チェイン法?
(って話からするとチェインか?)
ハッシュテーブルのサイズは?

2000万近くあるなら BST のほうがいいかもよ。
もしくはチェインの下に BST を吊すとか。