UNB/ CS/ David Bremner/ teaching/ cs3613/ 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.

• The function `hash` creates an immutable hash table. Values can be retrieved with `hash-ref`
```    #lang racket

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

(module+ test
(require rackunit)
(check-equal? (hash-ref ht "apple") 'red))
```
• Immutable hash tables can be "updated" in the same way as lists, by returning a new, updated data structure. These updates are "constant time", which means they are pretty fast. In the following, hash-set is acting like `cons`, adding new data to `ht` and returning the result. Note that `ht` is not modified here, as the tests show.
```    (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"))))
```
• In the following example, a hash set is used to count the times a given element occurs in a list. Fill in update to the accumulator in the following code so that the tests pass.
```    (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))))
```
• We are using pairs, which are related to lists, but not exactly the same. `car` is like `first`, but works for both pairs and lists.

Explorer

Prerequisites
running
• Run the following program in DrRacket. You can navigate the data structure with the mouse, and evaluate expressions involving `this` (e.g. `(first this)`, `(hash-ref "apple" this)`) in the bottom REPL window.
```    #lang racket
(require explorer)

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