recitation 12: association lists & hash tables
----------------------------------------------------------
tradeoff: concrete structures that are very efficient but prone to misuse
vs.
abstract structures that nicely insulate the implementation
from its use but may suffer from efficiency issues
robust-ness, modularity, & ease of use will often triumph over speed
abstract data types (ADT)
* abstraction of implementation from use
* can write down types of the constructor/selectors & predicates
but don't know the guts It's not in the contract (unspecified).
----------------------------------------------------------
association list: (alist) List of 2 element lists (key value)
(define (find-assoc key alist)
(cond
((null? alist) #f)
((equal? key (caar alist)) (cadar alist))
(else (find-assoc key (cdr alist)))))
(define (add-assoc key val alist)
(cons (list key val) alist))
(define *phone-book*
(list (list 'alice 6175551212)
(list 'bob 6175555237)
(list 'carol 6175556824)))
* write code to get bob's number
* what happens if you look up dan's number?
* write code to add erin's number
* if there are 50,000 phone numbers in *phone-book*, how
long does it take to look up a person's number, on average?
* write code to add bob's new number
* what happens to his old number?
* write code to return the list of all the numbers ever stored
for a particular person, in chronological order
----------------------------------------------------------
mutation
* redefining at the top level is sort-of mutation, but we'll
learn REAL mutation on Tuesday & Wednesday
* convention: procedures that end in ! (pronounced "bang!")
are mutators
----------------------------------------------------------
vectors: (a.k.a. arrays, "efficient lists")
* vectors are fixed length
* retrieval in O(1) (it's O(n) for lists)
(make-vector k) k is length of vector, initialize entries to #f
(vector-ref vector k) returns the kth element of vector
(vector-set! vector k obj) sets the kth element of the vector to obj
(define *students* (make-vector 5))
*students* --> #(#f #f #f #f #f)
(vector-set! *students* 0 'bob)
(vector-set! *students* 3 'alice)
*students* --> #(bob #f #f alice #f)
(vector-ref *students* 3) -> alice
* can you re-implement make-vector & vector-ref using cons?
(ignoring efficiency)
----------------------------------------------------------
table: list of bindings/pairings of a key and a value
(make-empty-table) O(1)
(put! key value) O(1)
(get key) O(n)
hash tables: vector of bindings/pairings of a key and value
the key is mapped to an index by a hash function
hash functions: "uniformly" distributes the keys throughout the
range of legal index values (0 -> k-1). "chooses a bucket".
collisions: multiple keys often map to same index. Store an
association list at each index.
hash tables:
(make-empty-table) O(n) need to create & initialize the vector
(put! key value) O(1) if the hash function is easy to compute
(get key) O(1) for a "good" hash function, and a big
enough vector
* other than the efficiency of operations, all the functions have the
same type and we can use a table without knowing the implementation
----------------------------------------------------------
hash table application: caller id
* given *phone-book* (an association list with 50,000
name/number pairings) write code to lookup the name
matching a particular phone number
* name lookup should be O(1) time expected
* the caller id system should use O(n) memory (n = 50,000)
(define *phone-book*
(list (list 'alice 6175551212)
(list 'bob 6175555237)
(list 'carol 6175556824)))
(define *caller-id-length* 50000)
(define (make-caller-id-hash-table phone-book)
(if (null? phone-book)
(make-vector *caller-id-length*)
(let ((answer (make-caller-id-hash-table (cdr phone-book))))
(add-number (caar phone-book) (cadar phone-book) answer)
answer)))
(define (add-number name number caller-id)
(let ((index (phone-number-hash-function number)))
(vector-set! caller-id index (cons (list name number)
(vector-ref caller-id index)))))
(define (phone-number-hash-function number) (modulo number *caller-id-length*))
(define (lookup-name number caller-id)
(lookup-name-in-alist
number (vector-ref caller-id (phone-number-hash-function number))))
(define (lookup-name-in-alist number alist)
(if (null? alist)
(error "unknown caller")
(if (= (cadar alist) number) (caar alist)
(lookup-name-in-alist number (cdr alist)))))
(define *caller-id* (make-caller-id-hash-table *phone-book*))
(lookup-name 6175555237 *caller-id*) -> bob
----------------------------------------------------------
real world hash table application: ray tracing
(... if we have time)
----------------------------------------------------------