はてなブックマーク

概要 メルカリのハッシュ関数の完全性の別証明 multiplicative hash（実数値計算）の実装と計算機実験 multiplicative hash（整数値計算）の実装と計算機実験 multiplicative hash でインデックスが衝突する, 完全でない例（命題3の証明） multiplicative hash とメルカリのハッシュ関数の違い 注 本文では, 参考文献を [著者名 西暦下2桁] と記す. その詳細は文末の参考文献に示す. 本文中に示す命題の証明は, 付録にまとめて示す. はじめに メルカリのブログに, Knuth multiplicative hash が最小完全ハッシュ関数であることの証明 [metal_unk 17] というエントリがあり, Knuth の multiplicative hash が最小完全である証明を示しています. 実用的なハッシュ関数は