C++11のconstexprでコンパイル時に文字列のMurMur3ハッシュを計算する

文字列の比較は、その文字数によって計算時間が変化する。
例えば、以下の様な長い文字列の比較では、整数の比較に比べると時間がかかる。

example1.cpp

#include <string.h>
#include <iostream>

int main() {
    std::cout << strcmp("abcdefghijklmnopqrstuvwxyz", "abcdefghijklmnopqrstuvwxyz");
}

特に、何度も同じ文字列を比較する様な場合は、比較に要する計算時間を短縮するべきである。
そこで、文字列の比較では、文字列から所定の計算方法によって一意に得られた整数を比較する事がある。
この計算方法をハッシュ関数、得られた整数をハッシュ値という。殆どの場合、ハッシュ値から元の文字列を得る事は出来ない。

一般的に利用されているハッシュ関数にMurMur3というアルゴリズムがある。MurMur3は異なる文字列から同じハッシュ値が算出される事（シノニム）が少なく、計算時間も短いという特徴がある。なおMurMurはムァームァーと発音する。

注意すべき点として、ハッシュ値同士の比較は完全ではない。シノニムが発生すると異なる文字列を同じ文字列であると誤解してしまうからである。しかし、プログラムの実行中に変化しない文字列であれば、シノニムが判明した時点で別の文字列に変更する事でシノニムを回避する事ができる。例えば、そう、コンパイル時に判明している文字列ならね。

というわけで、C++11のユーザー文字列リテラルとconstexprを利用してコンパイル時に文字列からMurMur3ハッシュ値を算出するコードを書いた。C++14のconstexprであれば簡単に記述できるにも拘らず、敢えてC++11で記述したのである。理由は推して知るべし。

exmaple.cpp

#include <iostream>

namespace murmur3
{

constexpr uint32_t seed = 0;

constexpr uint32_t to_uint32(char const* key, size_t i = sizeof(uint32_t), uint32_t u32 = 0) { return i ? to_uint32(key, i - 1, (u32 << 8) | key[i - 1]) : u32; }

constexpr uint32_t murmur3a_5(uint32_t h) { return (h * 5) + 0xe6546b64; }
constexpr uint32_t murmur3a_4(uint32_t h) { return murmur3a_5((h << 13) | (h >> 19)); }
constexpr uint32_t murmur3a_3(uint32_t k, uint32_t h) { return murmur3a_4(h ^ k); }
constexpr uint32_t murmur3a_2(uint32_t k, uint32_t h) { return murmur3a_3(k * 0x1b873593, h); }
constexpr uint32_t murmur3a_1(uint32_t k, uint32_t h) { return murmur3a_2((k << 15) | (k >> 17), h); }
constexpr uint32_t murmur3a_0(uint32_t k, uint32_t h) { return murmur3a_1(k * 0xcc9e2d51, h); }
constexpr uint32_t murmur3a(char const* key, size_t i, uint32_t h = seed) { return i ? murmur3a(key + sizeof(uint32_t), i - 1, murmur3a_0(to_uint32(key), h)) : h; }

constexpr uint32_t murmur3b_3(uint32_t k, uint32_t h) { return h ^ k; }
constexpr uint32_t murmur3b_2(uint32_t k, uint32_t h) { return murmur3b_3(k * 0x1b873593, h); }
constexpr uint32_t murmur3b_1(uint32_t k, uint32_t h) { return murmur3b_2((k << 15) | (k >> 17), h); }
constexpr uint32_t murmur3b_0(uint32_t k, uint32_t h) { return murmur3b_1(k * 0xcc9e2d51, h); }
constexpr uint32_t murmur3b(char const* key, size_t i, uint32_t h) { return i ? murmur3b_0(to_uint32(key, i), h) : h; }

constexpr uint32_t murmur3c_4(uint32_t h) { return h ^ (h >> 16); }
constexpr uint32_t murmur3c_3(uint32_t h) { return murmur3c_4(h * 0xc2b2ae35); }
constexpr uint32_t murmur3c_2(uint32_t h) { return murmur3c_3(h ^ (h >> 13)); }
constexpr uint32_t murmur3c_1(uint32_t h) { return murmur3c_2(h * 0x85ebca6b); }
constexpr uint32_t murmur3c_0(uint32_t h) { return murmur3c_1(h ^ (h >> 16)); }
constexpr uint32_t murmur3c(uint32_t h, size_t len) { return murmur3c_0(h ^ len); }

constexpr uint32_t operator "" _murmur3(char const* str, size_t len) { return murmur3c(murmur3b(str + ((len >> 2) * sizeof(uint32_t)), len & 3, murmur3a(str, len >> 2)), len); }

}

int main() {
    using namespace murmur3;
    constexpr auto hash = "qwertyuio"_murmur3;
    std::cout << hash; // 64226981
}

以上