[ create a new paste ] login | about

Project: programmingpraxis
Link: http://programmingpraxis.codepad.org/uBMG1PWc    [ raw code | output | fork ]

programmingpraxis - Scheme, pasted on Oct 22:
; universal hash function

(define (hash x)
  (define (mod n) (modulo n 4294967296))
  (cond ((boolean? x) (if x 1 0))
        ((symbol? x) (hash (symbol->string x)))
        ((char? x) (char->integer x))
        ((integer? x) (mod x))
        ((real? x)
          (let* ((r (inexact->exact x))
                 (n (numerator r))
                 (d (denominator r)))
            (mod (+ n (* 37 d)))))
        ((rational? x) (mod (+ (numerator x) (* 37 (denominator x)))))
        ((complex? x)
          (mod (+ (hash (real-part x))
                  (* 37 (hash (imag-part x))))))
        ((null? x) 4294967295)
        ((pair? x)
          (let loop ((x x) (s 0))
            (if (null? x) s
              (loop (cdr x) (mod (+ (* 31 s) (hash (car x))))))))
        ((vector? x)
          (let loop ((i (- (vector-length x) 1)) (s 0))
            (if (negative? i) s
                (loop (- i 1) (mod (+ (* 31 s) (hash (vector-ref x i))))))))
        ((string? x)
          (let loop ((i (- (string-length x) 1)) (s 0))
            (if (negative? i) s
              (loop (- i 1) (mod (+ (* 31 s) (hash (string-ref x i))))))))
        ((procedure? x) (error 'hash "can't hash procedure"))
        ((port? x) (error 'hash "can't hash port"))
        (else (error 'hash "don't know how to hash object"))))

(display (hash #t)) (newline)
(display (hash 'cat)) (newline)
(display (hash #\c)) (newline)
(display (hash 42)) (newline)
(display (hash 3.3)) (newline)
(display (hash 22/7)) (newline)
(display (hash 1.2+3.4i)) (newline)
(display (hash '())) (newline)
(display (hash (list #t 'cat #\c 42 3.3 22/7 1.2+3.4i "cat"))) (newline)
(display (hash (vector #t 'cat #\c 42 3.3 22/7 1.2+3.4i "cat"))) (newline)
(display (hash "cat")) (newline)


Output:
1
2
3
4
5
6
7
8
9
10
11
1
114582
99
42
858993459
281
2576980370
4294967295
3763378086
634861146
114582


Create a new paste based on this one


Comments: