C++:map、hash_map、unordered_map
面接でよく聞かれる質問の一つは、mapとhashです.mapの違いと、いつmapを使うか、いつhashを使うかmap.またC++11のunordered_mapなので、ここでは3つも紹介します.使い方は紹介しないで、主に違いを紹介します.
1.三者の違い
map下層は赤黒樹で実現され,空間複雑度はO(n)であり,ノードの増加に伴って増加するが,検索時間複雑度はO(log(n))に固定されている.赤黒樹はもともと二叉探索樹であるため,begin()からend()まで遍歴して得られるkey値が秩序化されていることもmapの特徴である.
hash_mapはSGI実装、unordered_mapはC++11規格に追加されました.これらはhashテーブルで実現され,開鎖法を用いて衝突問題を解決する.しかしhashテーブルを用いるため,その特性は実際に必要とされる空間よりも基本的に大きい空間を用いることを決定した.保存されたデータは秩序化されていないので、mapのように遍歴して秩序化された結果を得ることはできません.検索時間の複雑さはO(1)に達することができ,基本的にmapより速い.unordered_mapでは,チェーンテーブルノードはbucket(バケツ)と呼ばれるデータ構造を用いる.
多くの場合hash tableで実現されるmapは赤黒樹で実現されるmapよりも検索が速いが、絶対的ではない.衝突が多すぎるとmapよりも時間がかかる可能性があるからだ.したがって、前者については基本的にrehashの操作があり、rehashの処理が異なるため、hash_mapとunordered_mapの性能にはいくつかの違いがあります.これは後述します.
2.使用するシーン
使用シーンは基本的にそれぞれの特性で決まる.
mapは、一般的に、データ量が1000未満、またはメモリの使用要件が高い場合に使用されます.hash tableは申請する空間が大きいため、赤黒樹は1つのノードを追加して1つのノードを申請する空間である.
データ量が多く頻繁に検索する必要がある場合はhash tableで実現したmapを使用できます.このときメモリはもはや主な問題ではなく,検索時間であるが,この場合hash tableの検索速度は定数であり,赤黒樹はO(log(n))であり,後者1024個のデータが最悪の場合には10回比較し,頻繁に検索する場合にはこの時間の消費が大きい.
まとめると、検索速度、データ量、メモリ使用の3つのトレードオフポイントです.
3. hash_mapとunordered_mapの性能の違い
hash_mapとunordered_mapの下部はすべてhash tableで実現されているので、わざわざ次の2つの違いを検索しましたが、関連する紹介は見つかりませんでしたが、基本的には両方ともhash table実装およびunordered_map性能比hash_mapはずっと良くてunordered_mapはすでに標準になっておりhash_の使用は推奨されていませんmap.
なぜunordered_map性能比hash_mapは良くて、簡単に両者の実現の部分のソースコードをすり抜けて、両者のrehashの処理が異なることを発見します.
unordered_の場合map、主なソースコードは「/usr/include/c+/4.8.2/tr 1/」ディレクトリの下にあります.unordered_を使用していますmap.hファイルは、実際の下地で使用するhash tableがhashtableである.hファイルにあります.hashtableを表示します.shのinsert関数の実装では、挿入するたびに次のコードが呼び出されることがわかります.
すなわちunordered_mapは挿入前に呼び出されます_M_rehash_policy._M_need_rehashは、rehashが必要かどうかを判断し、必要であれば呼び出します.M_rehash操作を行います._M_rehash_policyは同じディレクトリのhashtable_policy.hで実現された、M_need_rehashコードは次のとおりです.
_M_max_load_factorはhash table全体の負荷因子であり、デフォルトは1,M_growth_factorはbucket数の増加因子であり、デフォルトは2であり、_prime_リストは素数リストです.上記のコードから、insertのたびに、最後に必要なデータサイズが予め設定された最大値を超えているか否かを判断する.M_next_resizeは、必要なbucket数が現在のbucket数より大きいか否かを判断し、そうであればrehash操作が必要となる.
rehashの場合はまず現在のbucket数に負荷因子を乗じて新しいbucket数を得,_min_bkts比較で最大のbucket数を__に更新min_bktsで.次に、__からprime_リスト中選択比_min_bktsの大きい最小素数(素数のhashの方が効果的)、更新_M_max_load_factor後に素数を返します.
からM_need_rehashで返された結果、rehashが必要になった場合に呼び出されます.M_rehashは、返された素数をこの関数に渡します.
この関数は、再申請_です.n個のメンバーのbucket配列を,古いbucket配列のノードを新しいbucket配列に再hashすることは,比較的容易に理解できる.
じゃあ、hash_mapではどのようにrehashを実現しているのでしょうか.ここで私が見たソースコードは主に「/usr/local/include/boost/asio/detail/」ディレクトリの下のhash_map.hpp.Insert関数の内容は次のとおりです.
挿入時に現在のノードサイズがbucket数より大きいと判断すると、rehashの操作が行われ、rehash関数の内容は次のようになります.
ここでmapのrehashは簡単で乱暴で、unordered_のようにbucketの数を更新するだけでいいです.mapはそのように数量の最適化を行う.
またboostのunorderedも見ましたmapの実装、「/usr/local/include/boost/unordered」ディレクトリの下のunordered_map.hpp、コードの中のrehash操作も上のunordered_のようですmapのように新しいbucket数は素数に変換されますが、新しい要素を挿入するときにrehashが必要かどうかは判断されず、手動でrehash操作が必要に見えるようです.
上の対比でunordered_が見えますmapはrehashの操作でhash_よりmapはたくさん必要です.これはunorderedです.map効率はhash_mapの原因の一つでしょう.何か言い間違いがあったら、皆さんも指摘してほしいです.
次のリンクを参照してください.
map/unordered_map原理と使用整理
STLのmap、unordered_map、hash_map
1.三者の違い
map下層は赤黒樹で実現され,空間複雑度はO(n)であり,ノードの増加に伴って増加するが,検索時間複雑度はO(log(n))に固定されている.赤黒樹はもともと二叉探索樹であるため,begin()からend()まで遍歴して得られるkey値が秩序化されていることもmapの特徴である.
hash_mapはSGI実装、unordered_mapはC++11規格に追加されました.これらはhashテーブルで実現され,開鎖法を用いて衝突問題を解決する.しかしhashテーブルを用いるため,その特性は実際に必要とされる空間よりも基本的に大きい空間を用いることを決定した.保存されたデータは秩序化されていないので、mapのように遍歴して秩序化された結果を得ることはできません.検索時間の複雑さはO(1)に達することができ,基本的にmapより速い.unordered_mapでは,チェーンテーブルノードはbucket(バケツ)と呼ばれるデータ構造を用いる.
多くの場合hash tableで実現されるmapは赤黒樹で実現されるmapよりも検索が速いが、絶対的ではない.衝突が多すぎるとmapよりも時間がかかる可能性があるからだ.したがって、前者については基本的にrehashの操作があり、rehashの処理が異なるため、hash_mapとunordered_mapの性能にはいくつかの違いがあります.これは後述します.
2.使用するシーン
使用シーンは基本的にそれぞれの特性で決まる.
mapは、一般的に、データ量が1000未満、またはメモリの使用要件が高い場合に使用されます.hash tableは申請する空間が大きいため、赤黒樹は1つのノードを追加して1つのノードを申請する空間である.
データ量が多く頻繁に検索する必要がある場合はhash tableで実現したmapを使用できます.このときメモリはもはや主な問題ではなく,検索時間であるが,この場合hash tableの検索速度は定数であり,赤黒樹はO(log(n))であり,後者1024個のデータが最悪の場合には10回比較し,頻繁に検索する場合にはこの時間の消費が大きい.
まとめると、検索速度、データ量、メモリ使用の3つのトレードオフポイントです.
3. hash_mapとunordered_mapの性能の違い
hash_mapとunordered_mapの下部はすべてhash tableで実現されているので、わざわざ次の2つの違いを検索しましたが、関連する紹介は見つかりませんでしたが、基本的には両方ともhash table実装およびunordered_map性能比hash_mapはずっと良くてunordered_mapはすでに標準になっておりhash_の使用は推奨されていませんmap.
なぜunordered_map性能比hash_mapは良くて、簡単に両者の実現の部分のソースコードをすり抜けて、両者のrehashの処理が異なることを発見します.
unordered_の場合map、主なソースコードは「/usr/include/c+/4.8.2/tr 1/」ディレクトリの下にあります.unordered_を使用していますmap.hファイルは、実際の下地で使用するhash tableがhashtableである.hファイルにあります.hashtableを表示します.shのinsert関数の実装では、挿入するたびに次のコードが呼び出されることがわかります.
size_type __n_elt = __detail::__distance_fw(__first, __last);
std::pair __do_rehash
= _M_rehash_policy._M_need_rehash(_M_bucket_count,
_M_element_count, __n_elt);
if (__do_rehash.first)
_M_rehash(__do_rehash.second); すなわちunordered_mapは挿入前に呼び出されます_M_rehash_policy._M_need_rehashは、rehashが必要かどうかを判断し、必要であれば呼び出します.M_rehash操作を行います._M_rehash_policyは同じディレクトリのhashtable_policy.hで実現された、M_need_rehashコードは次のとおりです.
// __n_bkt is current bucket count, __n_elt is current element count,
// and __n_ins is number of elements to be inserted. Do we need to
// increase bucket count? If so, return make_pair(true, n), where n
// is the new bucket count. If not, return make_pair(false, 0).
inline std::pair
_Prime_rehash_policy::
_M_need_rehash(std::size_t __n_bkt, std::size_t __n_elt,
std::size_t __n_ins) const
{
if (__n_elt + __n_ins > _M_next_resize)
{
float __min_bkts = ((float(__n_ins) + float(__n_elt))
/ _M_max_load_factor);
if (__min_bkts > __n_bkt)
{
__min_bkts = std::max(__min_bkts, _M_growth_factor * __n_bkt);
const unsigned long* __p =
std::lower_bound(__prime_list, __prime_list + _S_n_primes,
__min_bkts);
_M_next_resize = static_cast<:size_t>
(__builtin_ceil(*__p * _M_max_load_factor));
return std::make_pair(true, *__p);
}
else
{
_M_next_resize = static_cast<:size_t>
(__builtin_ceil(__n_bkt * _M_max_load_factor));
return std::make_pair(false, 0);
}
}
else
return std::make_pair(false, 0);
} _M_max_load_factorはhash table全体の負荷因子であり、デフォルトは1,M_growth_factorはbucket数の増加因子であり、デフォルトは2であり、_prime_リストは素数リストです.上記のコードから、insertのたびに、最後に必要なデータサイズが予め設定された最大値を超えているか否かを判断する.M_next_resizeは、必要なbucket数が現在のbucket数より大きいか否かを判断し、そうであればrehash操作が必要となる.
rehashの場合はまず現在のbucket数に負荷因子を乗じて新しいbucket数を得,_min_bkts比較で最大のbucket数を__に更新min_bktsで.次に、__からprime_リスト中選択比_min_bktsの大きい最小素数(素数のhashの方が効果的)、更新_M_max_load_factor後に素数を返します.
からM_need_rehashで返された結果、rehashが必要になった場合に呼び出されます.M_rehashは、返された素数をこの関数に渡します.
template
void
_Hashtable<_key _value="" _allocator="" _extractkey="" _equal="" _h1="" _h2="" _hash="" _rehashpolicy="" __chc="" __cit="" __uk="">::
_M_rehash(size_type __n)
{
_Node** __new_array = _M_allocate_buckets(__n);
__try
{
for (size_type __i = 0; __i < _M_bucket_count; ++__i)
while (_Node* __p = _M_buckets[__i])
{
std::size_t __new_index = this->_M_bucket_index(__p, __n);
_M_buckets[__i] = __p->_M_next;
__p->_M_next = __new_array[__new_index];
__new_array[__new_index] = __p;
}
_M_deallocate_buckets(_M_buckets, _M_bucket_count);
_M_bucket_count = __n;
_M_buckets = __new_array;
}
__catch(...)
{
...
}
} この関数は、再申請_です.n個のメンバーのbucket配列を,古いbucket配列のノードを新しいbucket配列に再hashすることは,比較的容易に理解できる.
じゃあ、hash_mapではどのようにrehashを実現しているのでしょうか.ここで私が見たソースコードは主に「/usr/local/include/boost/asio/detail/」ディレクトリの下のhash_map.hpp.Insert関数の内容は次のとおりです.
// Insert a new entry into the map.
std::pair insert(const value_type& v)
{
if (size_ + 1 >= num_buckets_)
rehash(hash_size(size_ + 1));
size_t bucket = calculate_hash_value(v.first) % num_buckets_;
iterator it = buckets_[bucket].first;
...
}
挿入時に現在のノードサイズがbucket数より大きいと判断すると、rehashの操作が行われ、rehash関数の内容は次のようになります.
// Re-initialise the hash from the values already contained in the list.
void rehash(std::size_t num_buckets)
{
if (num_buckets == num_buckets_)
return;
num_buckets_ = num_buckets;
BOOST_ASIO_ASSERT(num_buckets_ != 0);
iterator end_iter = values_.end();
// Update number of buckets and initialise all buckets to empty.
bucket_type* tmp = new bucket_type[num_buckets_];
delete[] buckets_;
buckets_ = tmp;
for (std::size_t i = 0; i < num_buckets_; ++i)
buckets_[i].first = buckets_[i].last = end_iter;
...
}ここでmapのrehashは簡単で乱暴で、unordered_のようにbucketの数を更新するだけでいいです.mapはそのように数量の最適化を行う.
またboostのunorderedも見ましたmapの実装、「/usr/local/include/boost/unordered」ディレクトリの下のunordered_map.hpp、コードの中のrehash操作も上のunordered_のようですmapのように新しいbucket数は素数に変換されますが、新しい要素を挿入するときにrehashが必要かどうかは判断されず、手動でrehash操作が必要に見えるようです.
上の対比でunordered_が見えますmapはrehashの操作でhash_よりmapはたくさん必要です.これはunorderedです.map効率はhash_mapの原因の一つでしょう.何か言い間違いがあったら、皆さんも指摘してほしいです.
次のリンクを参照してください.
map/unordered_map原理と使用整理
STLのmap、unordered_map、hash_map