UNB/ CS/ David Bremner/ teaching/ cs4613/ tutorials/ hash

Hash tables

Prerequisites
tests, recursion, tail-recursion

Although we've mainly focussed on lists, racket supports many other data structures. One very useful data structure is the hash table These support fast key based retrieval (and updating) of information.

    #lang racket

    (define ht (hash "apple" 'red "banana" 'yellow))

    (module+ test
      (require rackunit)
      (check-equal? (hash-ref ht "apple") 'red))
    (define ht2 (hash-set ht "coconut" 'brown))

    (module+ test
      (check-equal? (hash-ref ht2 "coconut") 'brown)
      (check-exn exn:fail? (lambda () (hash-ref ht "coconut"))))
    (define (census . lst)
      (define (helper lst acc-hash)
        (cond
          [(empty? lst) (hash->list acc-hash)]
          [else
           (let* ([key (first lst)]
                  [current (hash-ref acc-hash key 0)])
             (helper (rest lst)                         ))]))
      (helper lst (hash)))

    (module+ test
      (check-equal?
       (sort (census 1 2 3 1 2) #:key car <) '((1 . 2) (2 . 2) (3 . 1)))
      (check-equal?
       (sort (census "aardvark" "dingo" "buffalo" "buffalo" "bear") #:key car string<?)
       '(("aardvark" . 1) ("bear" . 1) ("buffalo" . 2) ("dingo" . 1))))

Explorer

Prerequisites
running
    #lang racket
    (require explorer)

    (define a-list
      (list 1 (list 'foo "hello")
            (hash 'apple "red" 'sky "blue" 'violets "purple")))
    (explore a-list)