## Universal Hash Function

### October 23, 2012

This exercise can be easy, impossible, or somewhere in between, depending on your computing environment. I had no trouble writing a universal hash function in Scheme, which has a limited number of types and predicates to recognize them. C gives you access to the internal bit-image of any object in the language, so it shouldn’t be hard to write a universal hash function there, either. But a straight-jacketed language like Java may make a universal hash function impossible. Here’s my version in Scheme:

```(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"))))```

The basic types are handled first, then the collection types list and vector just loop over their members, handling each recursively. You can see examples at http://programmingpraxis.codepad.org/uBMG1PWc.

Pages: 1 2

### 6 Responses to “Universal Hash Function”

1. burr said

>>> ht = {“Test”: “String”, 1: “Integer”}
>>> ht
‘Integer’
>>> ht[“Test”]
‘String’
>>>

2. Probably cheating in Python: use the `id()` function. From calling `help(id)`
in my Python environment:

id(…)
id(object) -> integer

Return the identity of an object. This is guaranteed to be unique among
simultaneously existing objects. (Hint: it’s the object’s memory address.)

3. Paul said

In Python it is trivial, as you can use hash(object), which gives a hash for many data types. Hash refuses to give a value for mutable objects like a list, which makes sense.

4. Using Shen (which I’m definitely intrigued by):

```(tc +)

(define praxis-hash
{A --> number --> number}
X N -> (hash X N))

(praxis-hash praxising 1729)
```