For general key values from too large a range for them to be used as indices, one simple approach for a symbol-table implementation is to store the items contiguously in an array, in order. When a new item is to be inserted, we put it into the array by moving larger elements over one position as we did for insertion sort; when a search is to be performed, we look through the array sequentially. Because the array is in order, we can report a search miss when we encounter a key larger than the search key. Moreover, since the array is in order, both select and sort are trivial to implement. is a symbol-table implementation that is based on this approach.

It is worthwhile to revisit the issue of item and key representation. While we do so in the context of this specific implementation, the same issues arise in most other implementations. To be specific, suppose that we have a symbol table whose records are integer keys with associated floating-point numbers (as in our example in ). When we use the ADTs of , we need two references to access each key, as depicted at the bottom in . These references may be no problem in an app that involves thousands of searches on thousands of keys but may represent excessive cost in an app that involves billions of searches on millions of keys. As discussed in , it is not difficult to use a primitive type instead of KEY, which saves one reference per item, as depicted in the center in . When the associated information is also primitive (or there is none), we can use parallel arrays, with no references, as depicted at the top in . This arrangement would involve changing our interfaces and implementations to accept primitive-type parameters for both keys and associated information (see ). Such improvements can have substantial effects in performance-critical apps, and they apply to most of the symbol-table implementations that we will consider. We use the separate ITEM and KEY abstractions to express our algorithms with more precision and because they are quite useful in practical situations that involve complicated records and keys, which are common.

Screenshot Item and key object representations

This diagram depicts Java representations for ordered-array symbol tables of records with integer keys and floating-point associated information, using three different representations for the records: parallel arrays (top); an item class with two primitive-type fields (center); and an item class that uses a key class (bottom). A fourth option, where the associated information is also an object type, is not shown.

Java graphics 12fig01

We could slightly improve the inner loop in the implementation of search in by using a sentinel to eliminate the test for running off the end of the array in the case that no item in the table has the search key. Specifically, we could reserve the position after the end of the array as a sentinel, then fill its key field with the search key before a search. Then the search loop will always terminate with an item containing the search key, and we can determine whether or not the key was in the table by checking whether that item is the sentinel.

Array-based symbol table (ordered)

Like , this implementation uses an array of items, but it does not require the keys to be small integers. We keep the array in order when inserting a new item by moving larger items to make room, in the same manner as insertion sort. Then, the search method can scan through the array to look for an item with the specified key, returning null when encountering an item with a larger key. The select method is trivial, and the implementations of remove and toString are left as an exercise (see ). 

class ST { private boolean less(KEY v, KEY w) { return v.less(w); } private boolean equals(KEY v, KEY w) { return v.equals(w); } private ITEM[] st; private int N = 0; ST(int maxN) { st = new ITEM[maxN]; } int count() { return N; } void insert(ITEM x) { int i = N++; KEY v = x.key(); while (i > 0 && less(v, st[i-1].key())) { st[i] = st[i-1]; i--; } st[i] = x; } ITEM search(KEY key) { int i = 0; for ( ; i < N; i++) if (!less(st[i].key(), key)) break; if (i == N) return null; if (equals(key, st[i].key())) return st[i]; return null; } ITEM select(int k) { return st[k]; } }

Alternatively, we could develop an implementation where we do not insist that the items in the array be kept in order. When a new item is to be inserted, we put it at the end of the array; when a search is to be performed, we look through the array sequentially. The characteristic property of this approach is that insert is fast but select and sort require substantially more work (they each require one of the methods in Chapters through ). We can remove an item with a specified key by doing a search for it, then moving the final item in the array to its position and decrementing the size by 1; and we can remove all items with a specified key by iterating this operation. If a handle giving the index of an item in the array is available, the search is unnecessary and remove takes constant time.

Another straightforward option for a symbol-table implementation is to use a linked list. Again, we can choose to keep the list in order, to be able to easily support the sort operation, or to leave it unordered, so that insert can be fast. is an implementation of the latter. As usual, the advantage of using linked lists over arrays is that we do not have to predict the maximum size of the table in advance; the disadvantages are that we need extra space (for the links) and we cannot support select efficiently.

The unordered-array and ordered-list approaches are left for exercises (see and ). These four implementation approaches (array or list, ordered or unordered) could be used interchangeably in apps, differing only (we expect) in time and space requirements. In this and the next several chapters, we will examine numerous different approaches to the symbol-table-implementation problem.

Keeping the items in order is an illustration of the general idea that symbol-table implementations generally use the keys to structure the data in some way to provide for fast search. The structure might allow fast implementations of some of the other operations, but this savings has to be balanced against the cost of maintaining the structure, which might be slowing down other operations. We shall see many examples of this phenomenon. For example, in an app where the sort operation is needed frequently, we would choose an ordered (array or list) representation because the chosen structure of the table makes the sort operation trivial, as opposed to it needing a full sort implementation. In an app where we know that the select operation might be performed frequently, we would choose an ordered array representation because this structure of the table makes select constant-time. By contrast, select takes linear time in a linked list, even an ordered one.

Linked-list-based symbol table (unordered)

This implementation of construct, count, search, and insert uses a singly linked list with each node containing an item with a key and a link. The insert method puts the new item at the beginning of the list and takes constant time. The search member method uses a private recursive method searchR to scan through the list.

The private equals method is the same as in and is omitted. Implementations of the select and sort operations are also omitted because this data structure does not support efficient implementations of those operations, and remove is left as an exercise (see ). 

class ST { private class Node { ITEM item; Node next; Node(ITEM x, Node t) { item = x; next = t; } } private Node head; private int N; ST(int maxN) { head = null; N = 0; } int count() { return N; } void insert(ITEM x) { head = new Node(x, head); N++; } private ITEM searchR(Node t, KEY key) { if (t == null) return null; if (equals(t.item.key(), key)) return t.item; return searchR(t.next, key); } ITEM search(KEY key) { return searchR(head, key); } public String toString() { Node h = head; String s = ""; while (h != null) { s += h.item + "\n"; h = h.next; } return s; } }

To analyze the performance of sequential search for random keys in more detail, we begin by considering the cost of inserting new keys and by considering separately the costs of successful and unsuccessful searches. We often refer to the former as a search hit, and to the latter as a search miss. We are interested in the costs for both hits and misses, on the average and in the worst case. Strictly speaking, our ordered-array implementation (see ) uses two comparisons for each item examined (one equal and one less). For the purposes of analysis, we regard such a pair as a single comparison throughout Chapters through , since we normally can effectively combine them into a three-way comparison (see, for example, ).

Property 12.2

Sequential search in a symbol table with N items uses about N/2 comparisons for search hits (on the average).

See . The argument applies for arrays or linked lists, ordered or unordered. Screenshot

Property 12.3

Sequential search in a symbol table of N unordered items uses a constant number of steps for inserts and N comparisons for search misses (always).

These facts are true for both the array and linked-list representations and are immediate from the implementations (see and ). Screenshot

Property 12.4

Sequential search in a symbol table of N ordered items uses about N/2 comparisons for insertion, search hits, and search misses (on the average).

See . Again, these facts are true for both the array and linked-list representations and are immediate from the implementations (see and ). Screenshot

Building an ordered table by successive insertion is essentially equivalent to running the insertion-sort algorithm of . The total running time to build the table is quadratic, so we would not use this method for large tables. If we have a huge number of search operations in a small table, then keeping the items in order is worthwhile, because Properties and tell us that this policy can save a factor of 2 in the time for search misses. If items with duplicate keys are not to be kept in the table, the extra cost of keeping the table in order is not as burdensome as it might seem, because an insertion happens only after a search miss, so the time for insertion is proportional to the time for search. On the other hand, if items with duplicate keys may be kept in the table, we can have a constant-time insert implementation with an unordered table. The use of an unordered table is preferred for apps where we have a huge number of insert operations and relatively few search operations.

Beyond these differences, we have the standard tradeoff that linked-list implementations use space for the links, whereas array implementations require that the maximum table size be known ahead of time or that the table undergo amortized growth (see ). Also, as discussed in , a linked-list implementation has the flexibility to allow efficient implementation of other operations such as join and remove.

summarizes these results and puts them in context with other search algorithms discussed later in this chapter and in Chapters and . In , we consider binary search, which brings the search time down to lg N and is therefore widely used for static tables (when insertions are relatively infrequent).

In Sections through , we consider binary search trees, which have the flexibility to admit search and insertion in time proportional to lg N, but only on the average. In , we shall consider red-black trees and randomized binary search trees, which guarantee logarithmic performance or make it extremely likely, respectively. In , we shall consider hashing, which provides constant-time search and insertion, on the average, but does not efficiently support sort and some other operations. In ,we shall consider the radix search methods that are analogous to the radix sorting methods of ; in , we shall consider methods that are appropriate for files that are stored externally.

Table 12.1. Costs of insertion and search in symbol tables

The entries in this table are running times within a constant factor as a function of N, the number of items in the table, and M, the size of the table (if different from N), for implementations where we can insert new items without regard to whether items with duplicate keys are in the table. Elementary methods (first four lines) require constant time for some operations and linear time for others; more advanced methods yield guaranteed logarithmic or constant-time performance for most or all operations. The N lg N entries in the column for select represent the cost of sorting the items-a linear-time select for an unordered set of items is possible in theory but is not practical (see ). Starred entries indicate worst-case events that are extremely unlikely.

worst case

average case

insert search select insert search hit search miss
key-indexed array 1 1 M 1 1 1
ordered array N N 1 N/2 N/2 N/2
ordered linked list N N N N/2 N/2 N/2
unordered array 1 N N lg N 1 N/2 N
unordered linked list 1 N N lg N 1 N/2 N
binary search N lg N 1 N/2 lg N lg N
binary search tree N N N lg N lg N lg N
red-black tree lg N lg N lg N lg N lg N lg N
randomized tree N* N* N* lg N lg N lg N
hashing 1 N* N lg N 1 1 1

Exercises

Java graphics icon01 12.18 Complete our ordered-array-based symbol-table implementation () by adding implementations of remove and toString. (Since the table is ordered, toString can put the items in order of their keys.)

Java graphics icon01 12.19 Implement searchinsert methods for our list-based () and array-based () symbol-table implementations. They should search the symbol table for items with the same key as a given item, then insert the item if there is none.

Write a symbol-table ADT interface for an app that needs to associate floating-point numbers with integer keys.

Write an implementation of your interface from that uses two arrays (an ordered array of ints and a parallel array of doubles) and no references.

Implement a remove (by key) operation for our list-based symbol-table implementation ().

Give the number of comparisons required to put the keys E A S Y Q U E S T I O N into an initially empty table using ADTs that are implemented with each of the four elementary approaches: ordered or unordered array or list. Assume that a search is performed for each key, then an insertion is done for search misses, as in .

Implement the construct, search, and insert operations for the symbol-table interface in , using an unordered array to represent the symbol table. Your program should match the performance characteristics set forth in .

ScreenshotImplement the construct, search, insert, select, and sort operations for the symbol-table interface in , using an ordered linked list to represent the symbol table. Your program should meet the performance characteristics set forth in .

ScreenshotChange our list-based symbol-table implementations () to use doubly linked lists so that they can support client item handles (see ); add an implementation of a clone (see ); and write a driver program that tests your interface and implementation.

Write a performance driver program that uses insert to fill a symbol table, then uses select and remove to empty it, doing so multiple times on random sequences of keys of various lengths ranging from small to large; measures the time taken for each run; and prints out or plots the average running times.

Write a performance driver program that uses insert to fill a symbol table, then uses search such that each item in the table is hit an average of 10 times and there is about the same number of misses, doing so multiple times on random sequences of keys of various lengths ranging from small to large; measures the time taken for each run; and prints out or plots the average running times.

Write an exercise driver program that uses the methods in our symbol-table interface on difficult or pathological cases that might turn up in practical apps. Simple examples include files that are already in order, files in reverse order, files where all keys are the same, and files consisting of only two distinct values.

ScreenshotWhich symbol-table implementation would you use for an app that does 102 insert operations, 103 search operations, and 104 select operations, randomly intermixed? Justify your answer.

Screenshot(This exercise is five exercises in disguise.) Answer for the other five possibilities of matching up operations and frequency of use.

A self-organizing search algorithm is one that rearranges items to make those that are accessed frequently likely to be found early in the search. Modify your search implementation for to perform the following action on every search hit: move the item found to the beginning of the list, moving all items between the beginning of the list and the vacated position to the right one position. This procedure is called the move-to-front heuristic.

Java graphics icon01 12.33 Give the order of the keys after items with the keys E A S Y Q U E S T I O N have been put into an initially empty table with search, then insert on search miss, using the move-to-front self-organizing search heuristic (see ).

Write a driver program for self-organizing search methods that uses insert to fill a symbol table with N keys, then does 10N searches to hit items according to a predefined probability distribution.

Use your solution to to compare the running time of your implementation from with your implementation from , for N = 10, 100, and 1000, using the probability distribution where search hits the ith largest key with probability 1/2i for 1 Screenshot i Screenshot N.

Do for the probability distribution where search hits the ith largest key with probability 1/(iHN) for 1 Screenshot i Screenshot N. This distribution is called Zipf's law.

Compare the move-to-front heuristic with the optimal arrangement for the distributions in Exercises and , which is to keep the keys in increasing order (decreasing order of their expected frequency). That is, use , instead of your solution to , in .