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 と等価です。