Programming Praxis

To allow us to focus on the cuckoo algorithm, we restrict ourselves to only string-valued keys. Here is our hash function:

(define (string-hash str x)
  (let loop ((cs (string->list str)) (h 0))
    (if (null? cs) h
      (loop (cdr cs) (+ (* h x)
        (char->integer (car cs)))))))

This is the same as the string-hash function in the Standard Prelude, except that it uses a variable multiplier x instead of a constant multiplier 31. To make a family of hash functions we will store the two multipliers in global variables x1 and x2, initialize them to 31 and 37, and increase them to the next-larger prime number when necessary:

(define (reset-multipliers)
  (set! x1 (next-prime x2))
  (set! x2 (next-prime x1)))

Lookup is simple: calculate the first hash, and return the requested item if it is found, otherwise calculate the second hash, and return the requested item if it is found, otherwise return failure. We store the key/value pairs as cons pairs and return the null list for failure:

(define (lookup table key)
  (let ((h (modulo (string-hash key x1) table-size)))
    (if (and (pair? (vector-ref table h))
             (string=? (car (vector-ref table h)) key))
        (vector-ref table h)
        (let ((h (modulo (string-hash key x2) table-size)))
          (if (and (pair? (vector-ref table h))
                   (string=? (car (vector-ref table h)) key))
              (vector-ref table h)
              '())))))

Insertion works as described above, except that if both possible nests are occupied, we always throw out the contents of the first nest; doing so makes it somewhat more likely that only one hash function will need to be calculated during lookup. Instead of checking for cycles, as suggested above, we simply stop and rehash if we have made more than max-probes steps:

(define (insert table key value)
  (define (hash key x) (modulo (string-hash key x) table-size))
 (if (pair? (lookup table key))
      (let ((h1 (hash key x1)) (h2 (hash key x2)))
        (if (= (car (vector-ref table h1)) key)
            (begin (vector-set! table h1 (cons key value)) table)
            (begin (vector-set! table h2 (cons key value)) table)))
      (let loop ((key key) (value value) (count max-probes))
        (let ((h1 (hash key x1)) (h2 (hash key x2)))
          (cond ((null? (vector-ref table h1))
                 (vector-set! table h1 (cons key value)) table)
                ((null? (vector-ref table h2))
                  (vector-set! table h2 (cons key value)) table)
                ((zero? count)
                  (set! table (rehash table))
                  (insert table key value))
                (else (let ((t (vector-ref table h1)))
                        (vector-set! table h1 (cons key value))
                        (loop (car t) (cdr t) (- count 1)))))))))

Rehashing is simply a matter of re-inserting all the key/value pairs in one table in a newly-allocated table using a new pair of hash functions:

(define (rehash table)
  (reset-multipliers)
  (let loop ((new-table (make-vector table-size '())) (i 0))
    (if (= i table-size) new-table
      (let ((t (vector-ref table i)))
        (if (pair? t)
            (loop (insert new-table (car t) (cdr t)) (+ i 1))
            (loop new-table (+ i 1)))))))

Deletion is simple; just lookup the requested item, then replace it with the null list:

(define (delete table key)
  (let ((h (modulo (string-hash key x1) table-size)))
    (if (and (pair? (vector-ref table h))
             (string=? (car (vector-ref table h)) key))
        (vector-set! table h '())
        (let ((h (modulo (string-hash key x2) table-size)))
          (if (and (pair? (vector-ref table h))
                   (string=? (car (vector-ref table h)) key))
              (vector-set! table h '())))))
  table)

Now that we know how the functions work, we can write the make-hash function that creates a new hash table; it’s often better to work this way, so that you know the steady-state working of the code before you do the initialization. The sole argument is max-size, which is the maximum number of key/value pairs permitted in the table; the size of the underlying array is the smallest prime number more than twice the requested maximum size, so the array never gets too full. We make the table size and multipliers prime to reduce the number of collisions. X1 and x2 are initialized to 31 and 37, max-probes is initialized based on the size of the table, and empty items are initialized to the null list:

(define x1 #f)
(define x2 #f)
(define table-size #f)
(define max-probes #f)

(define (make-hash max-size)
  (set! x1 31) (set! x2 37)
  (set! table-size (next-prime (* 2 max-size)))
  (set! max-probes (max (* (ilog 2 max-size) 2) 20))
  (make-vector table-size '()))

We collect the contents of the hash table in a list by indexing through the table taking all non-null items:

(define (enlist table)
  (let loop ((i 0) (xs '()))
    (if (= i table-size) xs
      (let ((t (vector-ref table i)))
        (loop (+ i 1) (if (pair? t) (cons t xs) xs))))))

We test cuckoo hashing using a phonetic alphabet:

(define words '("alpha" "bravo" "charlie" "delta" "echo"
  "foxtrot" "golf" "hotel" "india" "juliet" "kilo" "lima"
  "mike" "november" "oscar" "papa" "quebec" "romeo" "sierra"
  "tango" "uniform" "victor" "whiskey" "xray" "yankee" "zulu"))

(define (cuckoo-test)
  (let ((t (make-hash 25)))
    (assert (lookup t "praxis") '())
    (let loop ((words words) (val 1))
      (when (pair? words)
        (set! t (insert t (car words) val))
        (loop (cdr words) (+ val 1))))
    (assert (lookup t "praxis") '())
    (assert (cdr (lookup t "papa")) 16)
    (set! t (delete t "papa"))
    (assert (lookup t "papa") '())))

With a max-size of 25, we rehashed the table once when inserting “lima” and twice when inserting “whiskey;” that’s what happens when the table gets full. With max-size of 30, no rehashes are required.

We used ilog and assert from the Standard Prelude and prime? from a previous exercise, and wrote a simple next-prime function that appears in the collected code at http://programmingpraxis.codepad.org/LIYEw8xo.

Pages: 1 2