Dictionaries and Maps

This data structure is probably the most useful data structure you will.  Typical programmers use tables every day programming.  We will discuss this topics for several weeks.

Container for entry = {key, value}, like the priority queue.  But unlike the priority queue that has one important entry: the minimal key, dictionaries and maps attempt to achieve "equal" and "fast" access for all entires.

Real Life Examples
The English dictionary is good example of a dictionary, and mathematical functions are good examples of maps.  For more examples of maps, think of tables.

Interfaces

public interface Map {
    public int size();
    public boolean isEmpty();
    /* returns the corresponding value */
    pubic Object get(Object key);
    /* adds the key and value to the map, returns the value */
    public Object put(Object key, Object value);
    /* removes the key and value from the map, returns value */
    public Object remove(Object key);
    public Iterator keys();
    public Iterator values();
}

/** Interface for a key-value pair entry **/
public interface Entry {
  public Object key();
  public Object value();
}

public interface Dictionary{
    public int size();
    public boolean isEmpty();
    /* returns a entry with key */
    pubic Entry find(Object key);
    /* returns an iterator of all the entries matching key */
    public Iterator findAll(Object key);
    /* adds the key and value to the map, returns the value */
    public Object put(Object key, Object value);
    /* removes the key and value from the map, returns value */
    public Object remove(Object key);
    public Iterator keys();
    public Iterator values();
}

Difference between Dictionaries and Maps

Maps have unique keys while dictionaries can have duplicate keys.  I like to say that "Dictionaries are like dictionaries and maps are like functions."

Implementation

How would you use a sequence or List to implement a dictionary or a map

Unsorted List

If we do not expect to access the dictionary after creation then we want creation of the dictionary to be fast.  If we do have to search the dictionary in the future we still can, although the search will be slow.  Examples are audit trails for transactions, process creation/execution/death, and the name sake: logs.

Log files are unordered sequences perhaps implemented with link list. Then at any time insertion is O(1) while finding a matching key takes O(n).

Sorted Vector

Look-up tables are ordered dictionaries.  Typical examples are dictionaries and spell checkers.  We prefer to implement them with a vector instead of a sequence so that we have faster look-ups,  but naturally the insertion is slow.  insertItem(k, e) could be as bad O(n) where n is the number of items in the dictionary.  Why?

Binary Search

The ordered keys in the vector allows us to make a binary search pattern.   First check the middle key of the dictionary if the middle key is greater then the target key we check the left part of the dictionary, otherwise we check the right side of the dictionary.    The algorithm is recursive so we can continue until we find the key or the region we are searching vanishes.

Algorithm: BinarySearch(S, k, low, high)
    input: Ordered vector S, key k, and int low and high
    output: element of S with key k

if low >= high then return NO_SUCH_KEY  // termination for not found
else
    mid = (low + high)/2
    if k = key(mid) then return element(mid)   //  terminate for found
     // following elses are the recursive cases.
    elseif k < key(mid) then return BinarySearch(S, k, low, mid-1)
    else return BinarySearch(S, k, mid+1, high)

Cost

Worst case: The search is made in O(lg n) time, where n is the number of items in the Look-up Table.   So findItem takes no more then O(lg n).

Comparison of Log file and Look-up Table: