如何为无序映射 C++14 包含更好的位混合器

Question

如何合并以下位混合代码以最大限度地减少 unordered_map 中的哈希冲突？目的是帮助无序映射的内部散列方案执行位混合器策略以最小化散列冲突。作为菜鸟，即使阅读了文档，我也无法弄清楚如何去做。

UInt64 MurmurHash3Mixer( UInt64 key )
  {
  key ^= (key >> 33);
  key *= 0xff51afd7ed558ccd;
  key ^= (key >> 33);
  key *= 0xc4ceb9fe1a85ec53;
  key ^= (key >> 33);

  return key;
  }

发布的代码引用自 site。

以下是完整代码（测试代码），只是为了让 'MurmurHash3Mixer' 包含在 'std::unordered_map' 哈希方案中。

#include <iostream>
#include <unordered_map>

uint64_t MurmurHash3Mixer( uint64_t key ) { 
    key ^= (key >> 33);
    key *= 0xff51afd7ed558ccd;
    key ^= (key >> 33);
    key *= 0xc4ceb9fe1a85ec53;
    key ^= (key >> 33);

    return key;
}


int main() {

    uint64_t tx = 10L;
    std::unordered_map<uint64_t, uint64_t> ht; 
    ht.insert(std::make_pair<uint64_t, uint64_t>(tx, 20));
    std::cout << ht[tx] << std::endl;

    return 0;
}

Answer 1

您需要设置一个接受 const Key & 和 returns a size_t 的函数对象。然后在创建无序映射时将其作为模板传递

struct myhash
{
   size_t operator() (const UInt64 &key)
   {
      return (size_t) MurmurHash3Mixer(key):
   }
}

std::unordered_map<uint64_t, uint64_t, myhash> ht;

Answer 2

只是为有同样问题的人添加更正的代码。

#include <iostream>
#include <unordered_map>

uint64_t MurmurHash3Mixer( uint64_t key ) {
    key ^= (key >> 33);
    key *= 0xff51afd7ed558ccd;
    key ^= (key >> 33);
    key *= 0xc4ceb9fe1a85ec53;
    key ^= (key >> 33);

    return key;
}

struct myhash {
   std::size_t operator() (const uint64_t &key) const {
      return (size_t) MurmurHash3Mixer(key);
    }
};


int main() {

    uint64_t tx = 10L;
    std::unordered_map<uint64_t, uint64_t, myhash> ht;
    ht.insert(std::make_pair<uint64_t, uint64_t>(tx, 20));
    std::cout << ht[tx] << std::endl;

    return 0;
}

如何为无序映射 C++14 包含更好的位混合器

How to include better bit mixer for unordered map C++14

c++

unordered-map

hashtable

c++11

c++14