文字列/バイト列用のハッシュ関数ライブラリ
A Hash Function for Hash Table Lookupに載っているハッシュ関数(Jenkins Hash)をCommon Lispで実装した。
github: jenkins-hash(0.0.2)
作成の主な動機は以下の二つ:
おそらくSBCL以外の処理系でも動くと思うけど、動作は未確認。
使用例
以下、使用例。
;;;; SBCL-1.0.51-64bit ;;; 【文字列】 ;; 文字列からハッシュ値を算出 (jenkins-hash:hash-string "ハッシュ関数") --> 3188986421 ; 一つのキーに対して二つのハッシュ値(32bit)を返す 2167986557 ;; パラメータ(seed1,seed2)を替えて別のハッシュ値を算出 (jenkins-hash:hash-string "ハッシュ関数" :seed1 13 :seed2 44444) --> 2402597428 3323692532 ;; 範囲指定 (jenkins-hash:hash-string "ハッシュ関数" :start 2 :end 4) --> 58741211 888923469 ;;; 【バイト列】 ;; バイト列からハッシュ値を算出 (jenkins-hash:hash-octets (sb-ext:string-to-octets "ハッシュ関数")) --> 1523938354 936250363 ;; sxhash関数だと配列を与えた場合、全て同じハッシュ値になってしまう (sxhash (sb-ext:string-to-octets "ハッシュ関数")) --> 518591303 (sxhash (sb-ext:string-to-octets "別の値")) --> 518591303 ;;; 【複数のハッシュ値】 ;; nth-hash関数を使って、任意個のハッシュ値を安価に生成可能 ;; ※ 内部的にはDoubleHashingを用いて生成している => 可算一つと乗算一つで算出可能 ;; 一つのキーに対する10個の異なるハッシュ値を取得する (defun hash10 (key) (multiple-value-bind (h1 h2) (jenkins-hash:hash-string key) ;; 最初の二つはそのまま使って、残りはnth-hash関数で生成する `(,h1 ,h2 . ,(loop FOR i FROM 2 BELOW 10 COLLECT (jenkins-hash:nth-hash i h1 h2))))) (hash10 "ハッシュ関数") --> (3188986421 2167986557 3229992239 1103011500 3270998057 1144017318 3312003875 1185023136 3353009693 1226028954)
