読者です 読者をやめる 読者になる 読者になる

文字列/バイト列用のハッシュ関数ライブラリ

common lisp library

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)

*1:sxhash関数を配列に適用すると常に同じ値が返ってきてしまう。sbcl-1.0.51-64bit