implementing dictionaries
simple representation: association list
- (define (lookup d k) (cadr (assq k d)))
- orders of growth (in n, length of assoc list):
time to lookup: n
time to insert new entry: 1
- if list is sorted?
worst case is no better
but on average, only search half the list
better representations
- can learn about these in algorithms course
- tree: entries are sorted by key, and arranged on a tree
time is order (log n) to lookup
- hash table
entries are stored in lists of buckets
each list is associated with an array element
hash function applied to key gives array index, designed to spread entries evenly so that lists are short
time is order (1) to lookup