hash functions
Here are some common hash functions in C I found online
here and
here. I have done the menial task of translating them to Common Lisp.
code
1
2
3
4
5
6
7
8
9
10
11
12
13
|
;;; Hash Function by Dan Bernstein
(defun hash-DJB (str)
(declare (type simple-string str)
(type (unsigned-byte 32) hash)
(optimize speed (debug 0)))
(let ((hash 5381))
(loop for x across str
do (setf hash (ldb (byte 32 0)
(+ (ldb (byte 32 0)
(+ (ldb (byte 32 0)
(ash hash 5)) hash))
(char-int x))))
finally (return hash))))
|
1
2
3
4
5
6
7
8
9
10
|
;;; Hash Function by Dan Bernstein
(defun hash-DJB2 (str)
(declare (type simple-string str)
(type (unsigned-byte 32) hash)
(optimize speed (debug 0)))
(let ((hash 5381))
(loop for x across str
do (setf hash (ldb (byte 32 0)
(logxor (char-int x) (* hash 33))))
finally (return hash))))
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
;;; Hash Function from GAWK, a variation from the verwion from SDBM
(defun hash-SDBM (str)
(declare (type simple-string str)
(type (unsigned-byte 32) hash)
(optimize speed (debug 0)))
(let ((hash 0))
(loop for x across str
do (setf hash (ldb (byte 32 0)
(+ (char-int x)
(ldb (byte 32 0) (ash hash 6))
(ldb (byte 32 0) (ash hash 16))
(- hash))))
finally (return hash))))
|
1
2
3
4
5
6
7
8
9
10
11
12
|
;;; An algorithm proposed by Donald E. Knuth in The Art Of Computer Programming Volume 3
(defun hash-DEK (str)
(declare (type simple-string str)
(type (unsigned-byte 32) hash)
(optimize speed (debug 0)))
(let ((hash (length str)))
(loop for x across str
do (setf hash (ldb (byte 32 0)
(logxor (char-int x)
(logxor (ldb (byte 32 0) (ash hash 5))
(ash hash -27)))))
finally (return hash))))
|