前回の記事の最後で「unsigned long long intのハッシュは（size_t = 32ビットの環境で）下位32ビットしか見てない」みたいな事を書きました。

これが本当にそうだとすると、この挙動に依存しているunordered_mapに、下位32ビットが同じ値のキーを送り続けるとアルゴリズムの教科書通りの最悪ケースになって悲惨なことになるのでは…！という事が容易に予想されます。

ということで、やってみました。

実験環境

• Windows 7 64bit
• MinGW 32 g++ 4.8.1

ソースコードはこちら。

#include <unordered_map>
#include <cstdio>
#include <chrono>
unsigned long getT()
{
    return std::chrono::system_clock::now().time_since_epoch() / std::chrono::milliseconds(1);
}
int main()
{
    {
        std::unordered_map<unsigned long long int, int> map;
        unsigned long t = getT();
        for(int j=0;j<100;++j)
        for(unsigned long long int i=0;i<0x1000;++i){
            map.insert(std::make_pair(i << 17, 10));
        }
        printf("Case 1 Time: %d\n", static_cast<int>(getT() - t));
    fflush(stdout);
    }
    {
        std::unordered_map<unsigned long long int, int> map;
        unsigned long t = getT();
        for(int j=0;j<100;++j)
        for(unsigned long long int i=0;i<0x1000;++i){
            map.insert(std::make_pair(i << 33, 10));
        }
        printf("Case 2 Time: %d\n", static_cast<int>(getT() - t));
    fflush(stdout);
    }
}

シフトする値だけ少し変更することで、他の要素の影響を出来る限り減らしました。

結果

g++ -o test -std=gnu++11 test.cpp
./test
Case 1 Time: 120
Case 2 Time: 67825

というわけで500倍くらい遅かったので、本当に線形探索してるっぽいです。本当にありがとうごいました。

64bit環境なら問題ありません

64bit環境のwandboxで実行すると、64bit環境ではsize_tも64ビットになってくれるので、

Start

Case 1 Time: 287
Case 2 Time: 279

0

Finish

というわけでほぼ同じ時間で終わります。

最近諸事情でアルゴリズムイントロダクションを読んでおります。

で、平均挿入・検索・削除時間がO(1)である謎のテクノロジー、ハッシュテーブルの章を読んだので、せっかくなのでSTLの実装を調べてみました。

なお、コンパイル時の条件によって色々実装が分岐するようですが、面倒臭いので適当に目についたコードを読んでいます。なので、組み合わせとして一緒に呼ばれないコードを読んでいる可能性がありますが、ご了承下さい。

とりあえず、挿入を足がかりに

std::unorderd_mapの実装は、いろいろたらい回しにされたあとbits/hashtable.hに記述されているらしいことが分かります。とりあえず挿入っぽい処理を調べてみると、こんな感じになります。

  template
    void
    _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 	       _H1, _H2, _Hash, _RehashPolicy, _Traits>::
    _M_insert_bucket_begin(size_type __bkt, __node_type* __node)
    {
      if (_M_buckets[__bkt])
	{
	  // Bucket is not empty, we just need to insert the new node
	  // after the bucket before begin.
	  __node->_M_nxt = _M_buckets[__bkt]->_M_nxt;
	  _M_buckets[__bkt]->_M_nxt = __node;
	}
      else
	{
	  // The bucket is empty, the new node is inserted at the
	  // beginning of the singly-linked list and the bucket will
	  // contain _M_before_begin pointer.
	  __node->_M_nxt = _M_before_begin._M_nxt;
	  _M_before_begin._M_nxt = __node;
	  if (__node->_M_nxt)
	    // We must update former begin bucket that is pointing to
	    // _M_before_begin.
	    _M_buckets[_M_bucket_index(__node->_M_next())] = __node;
	  _M_buckets[__bkt] = &_M_before_begin;
	}
    }

どうやら、衝突の解決には片方向リストを使った方法を使っているようです。アルゴリズムイントロダクションには「削除が必要な時は片方向リストを使った方法がいい」みたいなことが書いてあったような気がするのですが、そのとおりっぽいです。あと番兵は使ってないみたいですね。やっぱりメモリの節約が優先なのでしょうか。

バケットのインデックスは？

で、この__bktはどこから来てるのかを調べてみると、_M_bucket_indexという関数の値が実際には使われており…bits/hashtable_policy.hに次のようなコードがあります。（型の条件によって複数あるようですがこれが一番なんか読みやすそうなのでこれにしました）

      std::size_t
      _M_bucket_index(const __node_type* __p, std::size_t __n) const
	noexcept( noexcept(declval()(declval()))
		  && noexcept(declval()((__hash_code)0,
						    (std::size_t)0)) )
      { return _M_h2()(_M_h1()(_M_extract()(__p->_M_v())), __n); }

というわけで、h1に値を突っ込んでハッシュを得た後、さらにh2にそのハッシュとバケットの総数を入れてハッシュをバケット数以下にして、実際のバケットのインデックスを求めているみたいです。

__nはバケット数の最大値です。_Key&は例えばstd::unordered_map<string, int>ならstringの方です。_M_h1と_M_h2は実はbits/unorderd_map.hの最初の方にすでに書いてあって、

  template,
	   typename _Pred = std::equal_to<_Key>,
	   typename _Alloc = std::allocator<std::pair >,
	   typename _Tr = __umap_traits<__cache_default<_Key, _Hash>::value>>
    using __umap_hashtable = _Hashtable<_Key, std::pair,
                                        _Alloc, __detail::_Select1st,
				        _Pred, _Hash,
				        __detail::_Mod_range_hashing,
				        __detail::_Default_ranged_hash,
				        __detail::_Prime_rehash_policy, _Tr>;

h1の実体はstd::hash<_Key>(_key const& key)で、これは後で調べますが、とりあえず色々な型についてhash値を返してくれるSTLの公開の標準ライブラリです（皆様もお使いになれます！）

h2は__detail::_Mod_range_hashingで固定で、ユーザーが指定したりは出来ないようです。

h2はただのmod

_Mod_Range_hashingはbits/hashtable_policy.hに実体があり、

  // Many of class template _Hashtable's template parameters are policy
  // classes.  These are defaults for the policies.

  /// Default range hashing function: use division to fold a large number
  /// into the range [0, N).
  struct _Mod_range_hashing
  {
    typedef std::size_t first_argument_type;
    typedef std::size_t second_argument_type;
    typedef std::size_t result_type;

    result_type
    operator()(first_argument_type __num,
	       second_argument_type __den) const noexcept
    { return __num % __den; }
  };

というわけで、散々たらい回しにされた挙句ただのmodでした。万能ハッシュとか使ってるのかと思ったのですがそんなことはなく、h1の実体であるstd::hashに衝突の回避とかの仕事はほぼ丸投げして、バケット数とmodをとっているという感じになります。

std::hashの実体

std::hashの実体は色々なところに散らばっているのですが、std::stringの実装がやっぱり一番気になるのでそれを調べてみると、basic_string.hに実体があって、

  /// std::hash specialization for string.
  template<>
    struct hash
    : public __hash_base
    {
      size_t
      operator()(const string& __s) const noexcept
      { return std::_Hash_impl::hash(__s.data(), __s.length()); }
    };

  template<>
    struct __is_fast_hash> : std::false_type
    { };

となっております。ほかのstd::wstringとかutf16とかも全部同じ実装です。hashの先を見れば分かるのですが、この関数はvoid*を取る関数なので、文字列としての特性はとくに使わず、バイト列として解釈してhashを計算しているようです。

さて、_Hash_impl::hashはfunctional_hash.hの関数です。このseedの値の意味がよくわかりません…。

    static size_t
    hash(const void* __ptr, size_t __clength,
	 size_t __seed = static_cast(0xc70f6907UL))
    { return _Hash_bytes(__ptr, __clength, __seed); }

なんとこの先はlibsupc++という別ライブラリに投げれていて、

  inline std::size_t
  unaligned_load(const char* p)
  {
    std::size_t result;
    __builtin_memcpy(&result, p, sizeof(result));
    return result;
  }

}

namespace std
{
_GLIBCXX_BEGIN_NAMESPACE_VERSION

#if __SIZEOF_SIZE_T__ == 4

  // Implementation of Murmur hash for 32-bit size_t.
  size_t
  _Hash_bytes(const void* ptr, size_t len, size_t seed)
  {
    const size_t m = 0x5bd1e995;
    size_t hash = seed ^ len;
    const char* buf = static_cast(ptr);

    // Mix 4 bytes at a time into the hash.
    while(len >= 4)
      {
	size_t k = unaligned_load(buf);
	k *= m;
	k ^= k >> 24;
	k *= m;
	hash *= m;
	hash ^= k;
	buf += 4;
	len -= 4;
      }

    // Handle the last few bytes of the input array.
    switch(len)
      {
      case 3:
	hash ^= static_cast(buf[2]) << 16;
      case 2:
	hash ^= static_cast(buf[1]) << 8;
      case 1:
	hash ^= static_cast(buf[0]);
	hash *= m;
      };

    // Do a few final mixes of the hash.
    hash ^= hash >> 13;
    hash *= m;
    hash ^= hash >> 15;
    return hash;
  }

この関数もなんとなくバイト列中のたくさんのビットを反映させていることはなんとなく分かるのですが、謎のマジックワードもあるし、謎です。

やっぱり本と実装はすこし違いますね～とおもったのでした。おしまい。

他の型のハッシュは？

同じfunctional_hash.hにマクロがあって、

  // Explicit specializations for integer types.
#define _Cxx_hashtable_define_trivial_hash(_Tp) 	\
  template<>						\
    struct hash<_Tp> : public __hash_base  \
    {                                                   \
      size_t                                            \
      operator()(_Tp __val) const noexcept              \
      { return static_cast(__val); }            \
    };

  /// Explicit specialization for bool.
  _Cxx_hashtable_define_trivial_hash(bool)

  /// Explicit specialization for unsigned long long.
  _Cxx_hashtable_define_trivial_hash(unsigned long long)

という感じです。なんとstatic_castするだけ！型に収まってるならともかく、unsigned long longまでstatic_castしちゃうのは本当にそれでいいの？感があります。…ということは32bit環境下でunordered_mapに下32ビットが同じunsigned long longを送り続けると死ぬほど遅い可能性がある…？　→実際に実験したら遅かった

ちなみにこのコードのすぐ下にありますが、double/floatに関してはバイト列として文字列と同じハッシュ関数を使っています。うーん…(^_^;)