Chapter 11 - Maps
|
Document last modified: |
Overview
Dynamic set (Chapter 10)
Sets that can change over time
Basic Operations
insert
delete
membership (search)
Dictionary - a dynamic set that supports the above operations
Elements - typically an object with fields that can be examined and manipulated
key - identifying field
satellite data - carried with key field but not used in set implementation
key satellite data 1492 "fourteen ninety two"
Total ordering - each set element satisfies for any a and b: a<b, a>b or a = b.
Many applications require a dynamic set that supports only the dictionary operations INSERT, SEARCH, and DELETE.
Example: a symbol table in a compiler.
Operations on dynamic set
SEARCH( S, k ) - search set S for key k returning a pointer to element or NIL
INSERT( S, x ) - inserts object x into set S at appropriate point, maintaining set properties such as ordered keys.
DELETE( S, x ) - deletes object x from set S, maintaining set properties such as ordered keys.
MINIMUM( S ) - returns pointer to element in S with minimum key.
MAXIMUM( S ) - returns pointer to element in S with maximum key.
SUCCESSOR( S, x ) - from totally ordered set S, returns pointer to successor of x, the next larger key or NIL if x.key is maximum.
PREDECESSOR( S, x ) - from totally ordered set S, returns pointer to predecessor of x, the next smaller key or NIL if x.key is minimum.
Hash table
A hash table is effective for implementing a dictionary.
The expected time to search for an element in a hash table is O(1), under some reasonable assumptions.
Worst-case search time is Q(n), however.
A hash table is a generalization of an ordinary array.
With an ordinary array, we store the element whose key is k in position k of the array.
Given a key k, we find the element whose key is k by just looking in the kth position of the array. This is called direct addressing.
Direct addressing is applicable when we can afford to allocate an array with one position for every possible key.
We use a hash table when we do not want to (or cannot) allocate an array with one position per possible key.
Use a hash table when the number of keys actually stored is small relative to the number of possible keys.
A hash table is an array, but it typically uses a size proportional to the number of keys to be stored (rather than the number of possible keys).
Given a key k, don’t just use k as the index into the array.
Instead, compute a function of k, and use that value to index into the array. We call this function a hash function.
Issues that we’ll explore in hash tables:
How to compute hash functions. We’ll look at the multiplication and division methods.
What to do when the hash function maps multiple keys to the same table entry. We’ll look at chaining and open addressing.
Mapping
What data structures books and algorithms commonly refer to as a dictionary is really a mathematical mapping defined by the function:
f: key ® satellite data
Functions can be viewed as a set of ordered pairs: {(k1, d1), ..., (ki, di), ... (kn, dn)}where "i, j if ki = kj, then i = j
The keys ki Î U, where U is the universe of all keys.
Mathematically, the keys form the domain, and the satellite form the range of the function.
If the function f maps all k Î U to some satellite data, then it's known as a total mapping.
If the function f maps k Î K, where K Ì U, then it's known as a partial mapping.
Mapping Operations
Insert new mapping (ki, di) into the mapping function
Lookup satellite data given a key k
Test to see if a key is defined in the mapping function
Remove an existing (ki, di) from the mapping function
Determine the number of mappings in the mapping function
Abstraction and Implementations
The mathematical function forms the abstraction upon which the dictionary is built
Databases are built on this abstraction.
What are some possible implementations:
direct addressing table
hash table
linear search (aka, association list)
binary tree