Loading [Contrib]/a11y/accessibility-menu.js
$\newcommand{\O}{\mathrm{O}}$ My Algorithm : kopricky アルゴリズムライブラリ

kopricky アルゴリズムライブラリ

Hash Function

コードについての説明

ハッシュ関数のリスト.
pair_hash, vector_hash は boost ライブラリを参考にハッシュ値を combine して実装した.
あとの $4$ つは murmur hash と呼ばれるハッシュ関数で こちら で著者が公開しているコードを基に実装した.
なお murmur hash は基本 public domain(ノンライセンス) だが, ビジネス目的で用いる場合は MIT license であるとの文言があるので注意.

コード

  1. // pair に対する std::hash を用いたハッシュ関数
  2. struct pair_hash {
  3.     template <class C1, class C2>
  4.     unsigned int operator() (const pair<C1, C2>& p) const {
  5.         unsigned int lhs = hash<C1>()(p.first), rhs = hash<C2>()(p.second);
  6.         return lhs^(rhs+0x9e3779b9+(lhs<<6)+(lhs>>2));
  7.     }
  8. };
  9.  
  10. // vector に対する std::hash を用いたハッシュ関数
  11. struct vector_hash {
  12.     template <class C>
  13.     unsigned int operator()(const vector<C>& p) const {
  14.         unsigned int h = p.size();
  15.         for(const C& k : p){
  16.             h ^= hash<C>()(k)+0x9e3779b9+(h<<6)+(h>>2);
  17.         }
  18.         return h;
  19.     }
  20. };
  21.  
  22. // int に対する murmur hash
  23. struct murmur_hash_int32 {
  24.     unsigned int operator()(int p) const {
  25.         const unsigned int m = 0x5bd1e995; p *= m;
  26.         unsigned int h = (p^(p>>24))*m;
  27.         return h = (h^(h>>13))*m, (h^(h>>15));
  28.     }
  29. };
  30.  
  31. // long long に対する murmur hash
  32. struct murmur_hash_int64 {
  33.     unsigned long long operator()(long long p) const {
  34.         const unsigned long long m = 0xc6a4a7935bd1e995; p *= m;
  35.         unsigned long long h = (p^(p>>47))*m;
  36.         return h = (h^(h>>47))*m, (h^(h>>47));
  37.     }
  38. };
  39.  
  40. // vector<int> に対する murmur hash
  41. struct murmur_hash32 {
  42.     unsigned int operator()(const vector<int>& p) const {
  43.         const unsigned int m = 0x5bd1e995;
  44.         unsigned int h = p.size();
  45.         for(unsigned int k : p){
  46.             k *= m, h = (h*m)^((k^(k>>24))*m);
  47.         }
  48.         h = (h^(h>>13))*m;
  49.         return (h^(h>>15));
  50.     }
  51. };
  52.  
  53. // vector<long long> に対する murmur hash
  54. struct murmur_hash64 {
  55.     unsigned long long operator()(const vector<long long>& p) const {
  56.         const unsigned long long m = 0xc6a4a7935bd1e995;
  57.         unsigned long long h = p.size();
  58.         for(unsigned long long k : p){
  59.             k *= m, h = (h*m)^((k^(k>>47))*m);
  60.         }
  61.         h = (h^(h>>47))*m;
  62.         return (h^(h>>47));
  63.     }
  64. };