株式会社エス・スリー・フォー » STLport のハッシュ・コンテナ

STLport のハッシュ・コンテナ

標準C++ライブラリが提供するコンテナは、vector, list, deque, set, multiset, map, multimap の7種です。これらコンテナから特定の要素を検索するとき、その時間計算量は vector, list, deque では O(N), set, multiset, map, multimap では O(logN) となります。

これ以上に高速な検索が可能なコンテナとしてハッシュ表(hashtable)を利用すれば、適切なハッシュ関数を与えることによって検索に要する時間計算量をコンテナ内の要素数に関わらず O(1) に近づけることができますが、残念ながら標準C++ライブラリにはハッシュ表で実装されたコンテナ(ハッシュ・コンテナ)を提供していません。

SGI(Silicon Graphics社)のSTL実装をベースに様々な処理系に対応させたSTLport(http://www.stlport.org)には、標準C++からは逸脱するものの、ハッシュ・コンテナ hash_set, hash_multiset, hash_map, hash_multimap が実装されています。

ハッシュ・コンテナ hash_set および hash_map は以下のように宣言されています(hash_multiset, hash_multimap は割愛)。

hash_set (stlport/stl/_hash_set.h より抜粋)

template <class Key, class HashFcn =hash<Key>, class EqualKey =equal_to<Key>,
          class Alloc =allocator<Key> >
class hash_set {
public:
  typedef ... key_type;
  typedef ... value_type;
  typedef ... hasher;
  typedef ... key_equal;

  typedef ... size_type;
  typedef ... difference_type;
  typedef ... pointer;
  typedef ... const_pointer;
  typedef ... reference;
  typedef ... const_reference;

  typedef ...            const_iterator;
  typedef const_iterator iterator;

  typedef ... allocator_type;

  hasher hash_funct() const;
  key_equal key_eq() const;
  allocator_type get_allocator() const;

  hash_set();
  explicit hash_set(size_type);
  hash_set(size_type, const hasher&);
  hash_set(size_type, const hasher&, const key_equal&, const allocator_type& =allocator_type());

  template <class InputIterator>
  hash_set(InputIterator, InputIterator);

  template <class InputIterator>
  hash_set(InputIterator, InputIterator, size_type );

  template <class InputIterator>
  hash_set(InputIterator, InputIterator, size_type, const hasher&);

  template <class InputIterator>
  hash_set(InputIterator, InputIterator, size_type, const hasher&, const key_equal&);

  template <class InputIterator>
  hash_set(InputIterator, InputIterator, size_type, const hasher&, const key_equal&, const allocator_type&);

  size_type size() const;
  size_type max_size() const;
  bool empty() const;
  void swap(hash_set&);

  iterator begin() const;
  iterator end() const;

  pair<iterator, bool> insert(const value_type&);

  template <class InputIterator>
  void insert(InputIterator, InputIterator); 

  pair<iterator, bool> insert_noresize(const value_type&);

  template <class KT>
  iterator find(const KT&) const;

  size_type count(const key_type&) const;
  pair<iterator, iterator> equal_range(const key_type&) const;

  size_type erase(const key_type&);
  void erase(iterator);
  void erase(iterator, iterator);
  void clear();

  void resize(size_type);
  size_type bucket_count() const;
  size_type max_bucket_count() const;
  size_type elems_in_bucket(size_type) const;

};

hash_map (stlport/stl/_hash_map.h より抜粋)

template <class Key, class Data, class HashFcn =hash<Key>, class EqualKey =equal_to<_Key>,
          class Alloc =allocator< pair<const Key,Data> > >
class hash_map {
public:
  typedef ... key_type;
  typedef ... data_type;
  typedef ... mapped_type;
  typedef ... value_type;
  typedef ... hasher;
  typedef ... key_equal;
  
  typedef ... size_type;
  typedef ... difference_type;
  typedef ... pointer;
  typedef ... const_pointer;
  typedef ... reference;
  typedef ... const_reference;

  typedef ... iterator;
  typedef ... const_iterator;

  typedef ... allocator_type;

  hasher hash_funct() const;
  key_equal key_eq() const;
  allocator_type get_allocator() const;

  hash_map();
  explicit hash_map(size_type);
  hash_map(size_type, const hasher&);
  hash_map(size_type, const hasher&, const key_equal&, const allocator_type& =allocator_type());

  template <class InputIterator>
  hash_map(InputIterator, InputIterator);

  template <class InputIterator>
  hash_map(InputIterator, InputIterator, size_type);

  template <class InputIterator>
  hash_map(InputIterator, InputIterator, size_type, const hasher&);

  template <class InputIterator>
  hash_map(InputIterator, InputIterator, size_type, const hasher&, const key_equal&)

  template <class InputIterator>
  hash_map(InputIterator, InputIterator, size_type, const hasher&, const key_equal&, 
            const allocator_type& =allocator_type());

  size_type size() const;
  size_type max_size() const;
  bool empty() const;
  void swap(hash_map&);
  iterator begin();
  iterator end();
  const_iterator begin() const;
  const_iterator end() const;

  pair<iterator,bool> insert(const value_type&);

  template <class InputIterator>
  void insert(InputIterator, InputIterator);

  pair<iterator,bool> insert_noresize(const value_type&)

  iterator find(const key_type&);
  const_iterator find(const key_type&) cons;

  Data& operator[](const key_type&);

  size_type count(const key_type& __key) const;
  
  pair<iterator, iterator> equal_range(const key_type&);

  pair<const_iterator, const_iterator> equal_range(const key_type&) const;

  size_type erase(const key_type&);
  void erase(iterator);
  void erase(iterator, iterator);
  void clear();

  void resize(size_type);
  size_type bucket_count() const;
  size_type max_bucket_count() const;
  size_type elems_in_bucket(size_type) const;

};

ハッシュ関数

template 引数に要素の型:Key、ハッシュ関数:HashFcn、等値判定関数:EqualKey、そしてアロケータ:Allocを与えます。

ハッシュ関数:HashFcn はKeyを引数とし、引数より求められたハッシュ値を size_t で返す関数オブジェクトを与えることになります。

STLport はよく使われるいくつかの型:

char*
const char*
crope
wrope
char
singned char
undigned char
short
unsigned short
int
unsigned int
long
unsigned long
string
wstring

についてはデフォルトのハッシュ関数オブジェクト:hash<T>が定義されているので利用者が定義する必要はありませんが、それ以外の型をハッシュ・コンテナの要素とする場合には利用者が定義しなければなりません。

また、等値判定関数:EqualKey のデフォルトは std::equal_to<Key> ですから、HashFcnと同様、operator== が定義されていない型については利用者が定義を与えることになります。

example

struct person {
  std::string name;
  int         age;
};

struct person_hash {
  std::hash<string> hs;
  std::hash<int>    hi;
  size_t operator()(const person& x) const {
    return static_cast<size_t>(hs(x.name) & hi(x.age));
  }
};

struct person_equal {
  bool operator()(const person& x, const person& y) const {
    return x.name == y.name && x.age == y.age;
  }
};

std::hash_set<person, person_hash, person_equal> person_set;
...

bucket

STLportが提供するハッシュ・コンテナの内部では、各要素はbucketに格納されます。ハッシュ・コンテナ内にはそのbucketが複数個あり、その数は bucket_count() で得られます。ある要素が挿入されるとき、まずハッシュ関数でハッシュ値が求められます。そしてそのハッシュ値をbucket数で割った余りを求め、その値が'何番目のbucketに要素を格納するか'を決定します。

個々のbucketは単方向リストで実装されているので複数の要素が格納されます。言い換えれば同じハッシュ値を持つ要素は同じbucketに納められます。

したがって、要素から得られるハッシュ値に十分なバラツキがない場合、いくつかのbucketに要素が集中することになります(各bucketに格納された要素数は elems_in_bucket() で得られます)。bucket内から特定の要素を検索する際、単方向リストからの検索すなわち線形検索が行なわれますから、結果的に検索速度が劣化します。

このbucket数は要素の増加に応じて自動的に大きくなります。bucket数の伸張の際、格納された全要素について適切なbucketに再配置する作業が伴い、この処理にかなりの処理時間を消費します。ですからより高速な動作が必要であるならあらかじめ十分大きなbucket数を設定しておけばよいでしょう。bucket数はコンストラクタあるいは resize() で設定することができます。実際のbucket数は引数で与えた設定値より小さくない素数となるようです。なお要素の挿入時にbucket数を伸張しない insert_noresize() が定義されています。

1,000,000個の要素をひとつづつhash_setに挿入したときのbucket数の変化を調べてみました。テスト・コードと実行結果を以下に示します。

bucket_count.cpp

#include <iostream>
#include <iomanip>
#include <hash_set>

int main() {
  std::hash_set<int> hs;
  std::hash_set<int>::size_type buckets = hs.bucket_count();

  std::cout << std::setw(7) << hs.size() << '\t' 
            << std::setw(7) << buckets << std::endl;
  const int N = 100000;
  for ( int i = 1; i <= N; ++i ) {
    hs.insert(i);
    if ( buckets != hs.bucket_count() ) {
      buckets = hs.bucket_count();
      std::cout << std::setw(7) << hs.size() << '\t' 
                << std::setw(7) << buckets << std::endl;
    }
  }
  return 0;
}

実行結果

      0     193
    194     389
    390     769
    770    1543
   1544    3079
   3080    6151
   6152   12289
  12290   24593
  24594   49157
  49158   98317
  98318  196613

iterator

前述のとおり、ハッシュ・コンテナ内の各要素は単方向リストに格納されています。したがってハッシュ・コンテナのメンバ関数が返すiteratorはいずれも単方向のiteratorであり、次の要素への移動(operator++)はできますが前の要素へは移動(operator–)できません。

また、要素の値がハッシュ値を決めるので、コンテナ内の要素の値を変更してはいけません。そのためにたとえばhash_setのメンバ関数が返すiteratorは、それを介して要素の変更ができないよう const_iterator と等価です。

επιστημη 2006-04-05

ハッシュは本当に速いのか?

標準C++ライブラリが提供する連想コンテナ
set/map(multiset/multimap)は通常二分木(binary-tree)で実装されています。要素の大小関係に基づいて木の枝を管理し、挿入/削除/検索に必要な時間計算量を対数時間に抑えるよう作られた優れものです。

では対数時間より高速なコンテナはないのでしょうか。ハッシュ表によるコンテナがひとつの解です。ハッシュ表のサイズとハッシュ関数を適切に選べば、時間計算量を定数時間に近づけることができます。

残念ながら標準C++規格にはハッシュ・コンテナは取り入れられませんでした。幸いなことに標準にはならなかったものの、ハッシュ・コンテナはいくつかの実装がなされています。

その中で代表的なハッシュ・コンテナの実装について、実際にそのパフォーマンス計測を試みました。

計測したハッシュ・コンテナは以下の3種です:

Dinkum Standard Library 2.33 (Dinkumware)
Visual C++にOEM提供されているSTLの製品版です。
STLport 4.5.1 (STLport)
SGI版をベースに、各種OS/コンパイラで使えるよう修正が加えられています。
SourcePro/Core (Rogue Wave)
C++ BuilderにOEM供給されているSTLの製品版です。

Windows2000,Visual C++6.0の環境下で、以下のコードをマルチスレッド/DLLでコンパイルし、計測を行いました。

#include <windows.h> // GetTickCount
#include <iostream>  // cout
#include <set>       // set

#if   defined(BENCH_DINKUM)
#include <hash_set>

typedef std::hash_set<int> hashset_type;

#elif defined(BENCH_STLPORT)
#include <hash_set>

typedef std::hash_set<int> hashset_type;

#elif defined(BENCH_SOURCEPRO)
#include <rw/stdex/hashset.h>
struct inthash {
  unsigned long operator()(int x) const { return x; }
};

typedef rw_hashset<int,inthash,std::equal_to<int>,std::allocator<int> > hashset_type;

#endif

template<class C>
void bench(const char* msg, C& c, size_t N) {
  std::cout << msg << '(' << N <&lt ')';
  int i;
  long tick = GetTickCount();
  for ( i = 0; i < N; ++i )
    c.insert(i);
  for ( i = 0; i < N; ++i )
    c.erase(i);
  tick = GetTickCount() - tick;
  std::cout << tick << "[ms], " << (double)tick/(double)N << "[ms/element]" << std::endl;
}

int main() {
  for ( size_t n = 1000; n < 40000; n += n ) {
    hashset_type hs;
    bench("hash table", hs, n);
    std::set<int> s;
    bench("bin.  tree", s, n);
  }
  return 0;
}

関数benchはintを要素の型とするコンテナに[0,N)の範囲のN個の要素を挿入/削除し、それに要する時間および要素1個あたりの時間を出力します。

mainでは要素数 1000, 2000, 4000, … 32000の場合についてハッシュ・コンテナと二分木コンテナとをbenchに与え、それぞれを比較しています。

Dinkum

実行結果

ash table(1000)10[ms], 0.01[ms/element]
bin.  tree(1000)10[ms], 0.01[ms/element]
hash table(2000)30[ms], 0.015[ms/element]
bin.  tree(2000)10[ms], 0.005[ms/element]
hash table(4000)100[ms], 0.025[ms/element]
bin.  tree(4000)20[ms], 0.005[ms/element]
hash table(8000)371[ms], 0.046375[ms/element]
bin.  tree(8000)50[ms], 0.00625[ms/element]
hash table(16000)1422[ms], 0.088875[ms/element]
bin.  tree(16000)120[ms], 0.0075[ms/element]
hash table(32000)5658[ms], 0.176813[ms/element]
bin.  tree(32000)241[ms], 0.00753125[ms/element]

正直'がっかり'しました。全然速くありません。要素数に比例して処理時間を食っています。

STLport

実行結果

hash table(1000)0[ms], 0[ms/element]
bin.  tree(1000)10[ms], 0.01[ms/element]
hash table(2000)0[ms], 0[ms/element]
bin.  tree(2000)0[ms], 0[ms/element]
hash table(4000)0[ms], 0[ms/element]
bin.  tree(4000)20[ms], 0.005[ms/element]
hash table(8000)20[ms], 0.0025[ms/element]
bin.  tree(8000)30[ms], 0.00375[ms/element]
hash table(16000)20[ms], 0.00125[ms/element]
bin.  tree(16000)80[ms], 0.005[ms/element]
hash table(32000)50[ms], 0.0015625[ms/element]
bin.  tree(32000)171[ms], 0.00534375[ms/element]

これはお見事。二分木に比べ、ほぼ5倍のスピードを叩き出しています。

SourcePro/Core

実行結果

hash table(1000)11[ms], 0.011[ms/element]
bin.  tree(1000)10[ms], 0.01[ms/element]
hash table(2000)10[ms], 0.005[ms/element]
bin.  tree(2000)10[ms], 0.005[ms/element]
hash table(4000)20[ms], 0.005[ms/element]
bin.  tree(4000)20[ms], 0.005[ms/element]
hash table(8000)60[ms], 0.0075[ms/element]
bin.  tree(8000)40[ms], 0.005[ms/element]
hash table(16000)160[ms], 0.01[ms/element]
bin.  tree(16000)90[ms], 0.005625[ms/element]
hash table(32000)411[ms], 0.0128437[ms/element]
bin.  tree(32000)190[ms], 0.0059375[ms/element]

Dinkum程ではないにしろ、二分木より遅いという結果となりました。

ハッシュは本当に速いのか?

なぜこのような結果になってしまったのでしょうか。

ハッシュ・コンテナは二分木に比べて複雑です。ハッシュ値を求め、その値に対応するスロットに要素を挿入します。必要に応じて全要素の再配置を行わなければならないこともあるでしょう。それに比べたら要素の比較を繰り返す二分木の方が速いという結果もうなずけます。比較に大きな時間を要する要素ではスピードが逆転するかもしれません。やってみましょう。要素を長さ8のstringに変更します:

#include <windows.h>  // GetTickCount
#include<iostream>  // cout
#include <set>       // set
#include <vector>    // vector
#include <string>    // string

#if   defined(BENCH_DINKUM)
#include 

class str_hash {
public:
  enum {bucket_size = 4,
        min_buckets = 8};
  size_t operator()(const std::string& x) const {
    size_t result = 0;
    for ( int i = 0; i < x.size(); ++i )
      result = result * 5 + x[i];
    return result;
  }
  bool operator()(const std::string& x, const std::string& y) const
   { return x < y; }
};

typedef std::hash_set<std::string, str_hash> hashset_type;

#elif defined(BENCH_STLPORT)
#include <hash_set>

typedef std::hash_set<std::string> hashset_type;

#elif defined(BENCH_SOURCEPRO)
#include <rw/stdex/hashset.h>
struct strhash {
  unsigned long operator()(const std::string& x) const { 
    unsigned long result = 0;
    for ( int i = 0; i < x.size(); ++i )
      result = result * 5 + x[i];
    return result;
  }
};

typedef rw_hashset<std::string,strhash,std::equal_to<std::string>,
                   std::allocator<std::string> > hashset_type;

#endif

template
void bench(const char* msg, C& c, size_t N) {
  std::cout <＆lt; msg <＆lt; '(' <＆lt; N >＆gt; ')';
  int i;
  std::vector<std::string> data;
  for ( i = 0; i < N; ++i ) {
    char str_val[6];
    sprintf(str_val,"%08d",i);
    data.push_back(str_val);
  }
  long tick = GetTickCount();
  for ( i = 0; i < N; ++i )
    c.insert(data[i]);
  for ( i = 0; i < N; ++i )
    c.erase(data[i]);
  tick = GetTickCount() - tick;
  std::cout << tick << "[ms], " << (double)tick/(double)N << "[ms/element]" << std::endl;
}

int main() {
  for ( size_t n = 1000; n < 40000; n += n ) {
    hashset_type hs;
    bench("hash table", hs, n);
    std::set<std::string> s;
    bench("bin.  tree", s, n);
  }
  return 0;
}

さて、結果は…

Dinkum

hash table(1000)10[ms], 0.01[ms/element]
bin.  tree(1000)10[ms], 0.01[ms/element]
hash table(2000)40[ms], 0.02[ms/element]
bin.  tree(2000)20[ms], 0.01[ms/element]
hash table(4000)161[ms], 0.04025[ms/element]
bin.  tree(4000)50[ms], 0.0125[ms/element]
hash table(8000)370[ms], 0.04625[ms/element]
bin.  tree(8000)111[ms], 0.013875[ms/element]
hash table(16000)1902[ms], 0.118875[ms/element]
bin.  tree(16000)230[ms], 0.014375[ms/element]
hash table(32000)2714[ms], 0.0848125[ms/element]
bin.  tree(32000)490[ms], 0.0153125[ms/element]

STLport

hash table(1000)0[ms], 0[ms/element]
bin.  tree(1000)10[ms], 0.01[ms/element]
hash table(2000)0[ms], 0[ms/element]
bin.  tree(2000)20[ms], 0.01[ms/element]
hash table(4000)10[ms], 0.0025[ms/element]
bin.  tree(4000)50[ms], 0.0125[ms/element]
hash table(8000)31[ms], 0.003875[ms/element]
bin.  tree(8000)100[ms], 0.0125[ms/element]
hash table(16000)80[ms], 0.005[ms/element]
bin.  tree(16000)220[ms], 0.01375[ms/element]
hash table(32000)171[ms], 0.00534375[ms/element]
bin.  tree(32000)481[ms], 0.0150312[ms/element]

SourcePro/Core

hash table(1000)10[ms], 0.01[ms/element]
bin.  tree(1000)10[ms], 0.01[ms/element]
hash table(2000)20[ms], 0.01[ms/element]
bin.  tree(2000)30[ms], 0.015[ms/element]
hash table(4000)50[ms], 0.0125[ms/element]
bin.  tree(4000)60[ms], 0.015[ms/element]
hash table(8000)100[ms], 0.0125[ms/element]
bin.  tree(8000)130[ms], 0.01625[ms/element]
hash table(16000)240[ms], 0.015[ms/element]
bin.  tree(16000)271[ms], 0.0169375[ms/element]
hash table(32000)621[ms], 0.0194063[ms/element]
bin.  tree(32000)571[ms], 0.0178437[ms/element]

ごらんの通り、比較に要する時間が長い要素の場合、二分木の処理速度が大きく劣化することがわかるでしょう。ハッシュ関数もintの場合と比べればハッシュ関数および等値判断が複雑になったので、その分遅くなってはいますが、二分木ほどの速度劣化は見られません。

しかしそれでもなお、速いはずのハッシュが二分木にはかないません。ハッシュは速いという常識をくつがえす結果となりました。

επιστημη 2006-03-30