Top > プログラミング関連 > ファイルの重複ロードを防ぐ - ハッシュコンテナ:mapとhash_map

ハッシュコンテナ:mapとhash_map

2005/8/3 記述

S34さんのページの「STLportのハッシュ・コンテナ」で知ったのですが、std::mapより高速なhash_mapがあるそうです。標準C++で提供されるstd::mapは二分木で検索を行うので大変遅いのですが、STLportで提供されるhash_mapはハッシュテーブルを使った検索を行うのでかなり高速なのだそうです。

そこで、どれだけ高速なのか実際に試してみました。実験に使ったのはAthlonXP 2100+、メモリ512MB、OSはWindows2000sp4の自作機です。コードはVC6.0でリリースモードでコンパイルし、数値は10回の平均をとっています。いずれも要素はint,キーのみをintとstd::stringで切り替えています。

なお、検証コードは前述サイト内の「stx::basic_symbol<T>」にあったコードを流用させていただきました。

結果

要素200個、試行1000回の場合
コンテナの種類	キー	時間
std::map	int	14ms
std::map	std::string	131.2ms
hash_map	int	7ms
hash_map	std::string	35.1ms

要素2000個、試行1000回の場合
コンテナの種類	キー	時間
std::map	int	168.2ms
std::map	std::string	2072ms
hash_map	int	77.1ms
hash_map	std::string	550.8ms

なかなかいい結果が出てるとは思いませんか？hash_mapはハッシュ値が重複してもOKなように作ってあるので、私のCRC+std::mapを使ったコードよりも使い勝手が遙かにいいと思います。

戻る

泥巣 by Claybird <claybird.without.wing@gmail.com>