11.4. The Dictionary ADT¶
11.4.1. The Dictionary ADT¶
The most common objective of computer programs is to store and retrieve data. Much of this book is about efficient ways to organize collections of data records so that they can be stored and retrieved quickly. In this section we describe a simple interface for such a collection, called a dictionary. The dictionary ADT provides operations for storing records, finding records, and removing records from the collection. This ADT gives us a standard basis for comparing various data structures. Loosly speaking, we can say that any data structure that supports insert, search, and deletion is a “dictionary”.
Dictionaries depend on the concepts of a search key and comparable objects. To implement the dictionary’s search function, we will require that keys be totally ordered. Ordering fields that are naturally multi-dimensional, such as a point in two or three dimensions, present special opportunities if we wish to take advantage of their multidimensional nature. This problem is addressed by spatial data structures.
Here is code to define a simple abstract dictionary class.
/** The Dictionary abstract class. */
public interface Dictionary {
/** Reinitialize dictionary */
public void clear();
/** Insert a record
@param key The key for the record being inserted.
@param elem The record being inserted. */
public void insert(Comparable key, Object elem);
/** Remove and return a record.
@param key The key of the record to be removed.
@return A maching record. If multiple records match
"k", remove an arbitrary one. Return null if no record
with key "k" exists. */
public Object remove(Comparable key);
/** Remove and return an arbitrary record from dictionary.
@return the record removed, or null if none exists. */
public Object removeAny();
/** @return A record matching "k" (null if none exists).
If multiple records match, return an arbitrary one.
@param key The key of the record to find */
public Object find(Comparable key);
/** @return The number of records in the dictionary. */
public int size();
}
/** The Dictionary abstract class. */
public interface Dictionary<K, E> {
/** Reinitialize dictionary */
public void clear();
/** Insert a record
@param k The key for the record being inserted.
@param e The record being inserted. */
public void insert(K key, E elem);
/** Remove and return a record.
@param k The key of the record to be removed.
@return A maching record. If multiple records match
"k", remove an arbitrary one. Return null if no record
with key "k" exists. */
public E remove(K key);
/** Remove and return an arbitrary record from dictionary.
@return the record removed, or null if none exists. */
public E removeAny();
/** @return A record matching "k" (null if none exists).
If multiple records match, return an arbitrary one.
@param k The key of the record to find */
public E find(K key);
/** @return The number of records in the dictionary. */
public int size();
}
The methods insert
and find
are the heart of the class.
Method insert
takes a record and inserts it into the dictionary.
Method find
takes a key value and returns some record from
the dictionary whose key matches the one provided.
If there are multiple records in the dictionary with that key value,
there is no requirement as to which one is returned.
Method clear
simply re-initializes the dictionary.
The remove
method is similar to find
, except that it
also deletes the record returned from the dictionary.
Once again, if there are multiple records in the dictionary that match
the desired key, there is no requirement as to which one actually is
removed and returned.
Method size
returns the number of elements in the
dictionary.
The remaining Method is removeAny
.
This is similar to remove
, except that it does not take a key
value.
Instead, it removes an arbitrary record from the dictionary, if one
exists.
The purpose of this method is to allow a user the ability to iterate
over all elements in the dictionary (of course, the dictionary will
become empty in the process).
Without the removeAny
method, dictionary users could not get
at a record of the dictionary that they didn’t already know the key
value for.
With the removeAny
method, the user can process all records
in the dictionary as shown in the following code fragment.
while (dict.size() > 0) {
Object it = dict.removeAny();
doSomething(it);
}
There are other approaches that might seem more natural for iterating
though a dictionary, such as using a “first” and a “next” function.
But not all data structures that we want to use to implement a
dictionary are able to do “first” efficiently.
For example, a hash table implementation cannot efficiently locate the
record in the table with the smallest key value.
By using RemoveAny
, we have a mechanism that provides generic
access.
Given a database storing records of a particular type, we might want to search for records in multiple ways. For example, we might want to store payroll records in one dictionary that allows us to search by ID, and also store those same records in a second dictionary that allows us to search by name.
Here is an implementation for a payroll record.
/** A simple payroll entry with ID, name, address fields */
public class Payroll {
private Integer ID;
private String name;
private String address;
/** Constructor */
Payroll(int inID, String inname, String inaddr) {
ID = inID;
name = inname;
address = inaddr;
}
/** Data member access functions */
public Integer getID() { return ID; }
public String getname() { return name; }
public String getaddr() { return address; }
}
Class Payroll
has multiple fields, each of which might be
used as a search key.
Simply by varying the type for the key, and using the appropriate
field in each record as the key value,
we can define a dictionary whose search key is the ID field,
another whose search key is the name field, and a third whose search
key is the address field.
Here is an example where Payroll
objects are stored in two separate dictionaries, one using the
ID field as the key and the other using the name field as the key.
// IDdict organizes Payroll records by ID
Dictionary IDdict = new UALDictionary();
// namedict organizes Payroll records by name
Dictionary namedict = new UALDictionary();
Payroll foo1 = new Payroll(5, "Joe", "Anytown");
Payroll foo2 = new Payroll(10, "John", "Mytown");
IDdict.insert(foo1.getID(), foo1);
IDdict.insert(foo2.getID(), foo2);
namedict.insert(foo1.getname(), foo1);
namedict.insert(foo2.getname(), foo2);
Payroll findfoo1 = (Payroll)IDdict.find(5);
Payroll findfoo2 = (Payroll)namedict.find("John");
One problem with the example as it is written is that the dictionary relies on the programmer to be reasonable about being consistent with the keys. These dictionaries are intended to have homogeneous elements. But nothing stops the programmer from inserting an integer key into the names dictionary, or searching with an integer search key. This problem can be handled by using C++ templates or Java generics.
The fundamental operation for a dictionary is finding a record that matches a given key. This raises the issue of how to extract the key from a record. We will usually assume that dictionary implementations store a key-value pair so as to be able to extract the key associated with a record for this particular dictionary.
The insert
method of the dictionary class supports the
key-value pair implementation because it takes two parameters,
a record and its associated key for that dictionary.
Now that we have defined the dictionary ADT and settled on the design approach of storing key-value pairs for our dictionary entries, we are ready to consider ways to implement it. Two possibilities would be to use an array-based or linked list. Here is an implementation for the dictionary using an (unsorted) array-based list.
// Dictionary implemented by unsorted array-based list.
public class UALDictionary implements Dictionary {
private static final int defaultSize = 10; // Default size
private AList list; // To store dictionary
// Constructors
UALDictionary() { this(defaultSize); }
UALDictionary(int sz) { list = new AList(sz); }
// Reinitialize
public void clear() { list.clear(); }
// Insert an element: append to list
public void insert(Comparable k, Object e) {
KVPair temp = new KVPair(k, e);
list.append(temp);
}
// Use sequential search to find the element to remove
public Object remove(Comparable k) {
Object temp = find(k);
if (temp != null) { list.remove(); }
return temp;
}
// Remove the last element
public Object removeAny() {
if (size() != 0) {
list.moveToEnd();
list.prev();
KVPair e = (KVPair)list.remove();
return e.value();
}
else { return null; }
}
// Find k using sequential search
// Return the record with key value k
public Object find(Comparable k) {
for(list.moveToStart(); list.currPos() < list.length();
list.next()) {
KVPair temp = (KVPair)list.getValue();
if (k.compareTo(temp.key()) == 0) {
return temp.value();
}
}
return null; // "k" does not appear in dictionary
}
// Return list size
public int size() { return list.length(); }
}
Examining class UALdict
(UAL stands for “unsorted array-based
list”), we can easily see that insert
is a constant-time operation, because it simply inserts the new record
at the end of the list.
However, find
, and remove
both require \(\Theta(n)\) time
in the average and worst cases, because we need to do a sequential
search.
Method remove
in particular must touch every record in the
list, because once the desired record is found, the remaining records
must be shifted down in the list to fill the gap.
Method removeAny
removes the last record from the list, so
this is a constant-time operation.
As an alternative, we could implement the dictionary using a linked
list.
The implementation would be quite similar to that for
UALDictionary
, and the cost of the functions should be the same
asymptotically.
Another alternative would be to implement the dictionary with a sorted
list.
The advantage of this approach would be that we might be able to speed
up the find
operation by using a binary search.
To do so, first we must define a variation on the List
ADT to
support sorted lists.
A sorted list is somewhat different from an unsorted list in that it
cannot permit the user to control where elements get inserted.
Thus, the insert
method must be quite different in a sorted
list than in an unsorted list.
Likewise, the user cannot be permitted to append elements onto the
list.
For these reasons, a sorted list cannot be implemented with
straightforward inheritance from the List
ADT.
The cost for find
in a sorted list is \(\Theta(\log n)\) for a
list of length \(n\).
This is a great improvement over the cost of find
in an
unsorted list.
Unfortunately, the cost of insert
changes from constant time in
the unsorted list to \(\Theta(n)\) time in the sorted list.
Whether the sorted list implementation for the dictionary ADT is more
or less efficient than the unsorted list implementation depends on the
relative number of
insert
and find
operations to be performed.
If many more find
operations than insert
operations are
used, then it might be worth using a sorted list to implement the
dictionary.
In both cases, remove
requires \(\Theta(n)\) time in the worst
and average cases.
Even if we used binary search to cut down on the time to find the
record prior to removal, we would still need to shift down the
remaining records in the list to fill the gap left by the
remove
operation.
Search trees are search structures that can perform all three key operations of insert, search, and delete in \(\Theta(\log n)\) time.