Matzにっきで取り上げられた MurmurHash を Java で書いてみた。 もともとのソースだと C の unsigned int でハッシュ値を計算していたので、Java では long で計算。 Java の int は signed だから桁を増やしたんだけど、 そのせいで 32 bit を超えた部分についてはマスクしてやる必要がでてしまった。 0xffffffffL でマスクするのはなんか不恰好だし遅いよなぁ…。 もうちょっとなんとかすべきかも。 一応、C で計算したのと同じハッシュ値が返る事は確認済み。 import java.io.UnsupportedEncodingException; import java.nio.ByteBuffer; import java.nio.ByteOrder; public class MurmurHash { /** * @par

FNVハッシュ関数は簡単に実装できるハッシュ関数です。 Twitterで見かけたので忘れないうちにメモ。 FNV-1 hash hash=offset_basis for each octet_of_data to be hashed hash=hash*FNV_prime hash=hash xor octet_of_data return hash octet_of_dataは変換元データから8bitずつ取り出した物を表します。変換元データがアルファベットだけから成る文字列なら、一文字ずつ取り出すのと同じです。 offset_basisとFNV_primeについては後述します。 FNV-1a hash XORを先にするだけです。変換元のデータが32bitよりも小さい場合はハッシュ値の分散度合いが良くなります。 hash=offset_basis for each octet_of_da