Dictionary

Dictionary ADT

  • The dictionary ADT models a searchable collection of keyelement items
  • The main operations of a dictionary are searching, inserting, and deleting items
  • Multiple items with the same key are allowed
  • Applications:􀂄 address book, credit card authorization, mapping host names
  • Dictionary ADT methods:
    • findElement(k): if the dictionary has an item with key k, returns its element, else, returns the special element NO_SUCH_KEY
    • insertItem(k, o): inserts item (k, o) into the dictionary
    • removeElement(k): if the dictionary has an item with key k, removes it from the dictionary and returns its element, else returns the special element NO_SUCH_KEY
    • size(), isEmpty()
    • keys(), elements()

Log File

  • A log file is a dictionary implemented by means of an unsorted sequence
    • We store the items of the dictionary in a sequence (based on a doubly-linked lists or a circular array), in arbitrary order
  • Performance:
    • insertItem takes O(1) time since we can insert the new item at the beginning or at the end of the sequence
    • findElement and removeElement take O(n) time since in the worst case (the item is not found) we traverse the entire sequence to look for an item with the given key
  • The log file is effective only for dictionaries of small size or for dictionaries on which insertions are the most common operations, while searches and removals are rarely performed (e.g., historical record of logins to a workstation)
  • Binary search performs operation findElement(k) on a dictionary implemented by means of an array-based sequence, sorted by key
    • similar to the high-low game
    • at each step, the number of candidate items is halved
    • terminates after a logarithmic number of steps

Implemented with Hash-Tables

See next chapter

Lookup Table

  • A lookup table is a dictionary implemented by means of a sorted sequence
    • We store the items of the dictionary in an array-based sequence, sorted by key
    • We use an external comparator for the keys
  • Performance:
    • findElement takes O(log n) time, using binary search
    • insertItem takes O(n) time since in the worst case we have to shift n/2 items to make room for the new item
    • removeElement take O(n) time since in the worst case we have to shift n/2 items to compact the items after the removal
  • The lookup table is effective only for dictionaries of small size or for dictionaries on which searches are the most common operations, while insertions and removals are rarely performed (e.g., credit card authorizations)

Implementing a Dictionary

Comparison of efficient dictionary implementations Implementing

Code

package examples;

import java.util.Iterator;

/**
 * Orderer Dictionary based on Locators which allows to store key - element pairs
 * @author ps
 *
 * @param <K> The type of the keys which has to extend a comparable type
 * @param <E> The type of the elements stored at this dictionary
 */
public interface OrderedDictionary<K extends Comparable<? super K>,E> {


    /**
     * @return the size (number of stored locators) of this dictionary object
     */
    public int size();

    /**
     * @param key
     * @return a Locator object with its key equal to 'key' or
     * null if there is no such locator in this dictionary (if there
     * are several equal keys all others can be retrieved with the
     * 'next' method )
     */
    public Locator<K,E> find(K key); // returns null if key not present

    /**
     * @param key
     * @return all Locator objects with its key equal to 'key' or
     * an arry of size 0 if there is no such locator in this dictionary
     */
    public Locator<K,E>[] findAll(K key);

    /**
     * @param key (not necessarily unique!)
     * @param o the object associated with 'key'
     * @return the Locator where the pair ('key','o') is stored
     */
    public Locator<K,E> insert(K key, E o);

    /**
     * @param loc the (valid) locator to be removed from this dictionary
     */
    public void remove(Locator<K,E> loc);

    /**
     * @param key
     * @return a locator with the largegst key smaller than 'key' is returned
     * (can be used to iterate over all locators)
     */
    public Locator<K,E> closestBefore(K key);
    /**
     * @param key
     * @return a locator with the smallest key larger than 'key' is returned
     * (can be used to iterate over all locators)
     */
    public Locator<K,E> closestAfter(K key);
    /**
     * @param loc
     * @return the next Locator in the order (can be used to iterate over all elements)
     */
    public Locator<K,E> next(Locator<K,E> loc);
    /**
     * @param loc
     * @return the previous Locator in the order (can be used to iterate over all elements)
     */
    public Locator<K,E> previous(Locator<K,E> loc);     
    /**
     * @return the locator with  minimal key (subsequent calls
     * of 'next' will find all of the locators)
     */
    public Locator<K,E> min();
    /**
     * @return  the Locator with minimal key (subsequent calls
     * of 'previous' will find all of the locators)
     */
    public Locator<K,E> max();

    /**
     * @return an Iterator on all locators of this
     * dictionary in sorted order;
     */
    public Iterator<Locator<K,E>> sortedLocators();


}