More than 3 years have passed since last update.

libcxx std::hash 実装のメモ

Posted at 2020-10-21

C++11 は unordered_map や unordered_set で便利になりましたが, その背景には std::hash の導入があります.

しかし std::hash の実装自体はややこしいものです.
ここでは libcxx(libc++)の実装を見てみます.

string

__string という名前のヘッダファイルの __do_string_hash に実装があります.

アルゴリズムとしては 32bit (size_t が 32bit の場合) では murmur2, 64bit では cityhash を使っています.
この実装は <utility> にあります.

CityHash の情報はこちら

イマドキに hash を一から実装するのであれば SipHash https://131002.net/siphash/ が良さそうな気もしますがどうかしらん?