Java Reference
In-Depth Information
example in Figure 8.1, at the point where method f is invoked.
Amoree
cient approach avoids touching each stack when a scope is
abandoned. The idea is to maintain a separate linking of symbol table entries
that are declared at the same scope level. Section 8.3.3 presents this organiza-
tion in greater detail. The details of maintaining a symbol table using ordered
lists are explored in Exercise 6. Although ordered lists o
er fast retrieval,
insertion into an ordered list is relatively expensive. Thus, ordered lists are
advantageous when the space of symbols is known in advance, as in the case
of reserved keywords.
ff
Binary Search Trees
Binary search trees are designed to combine the e
ciency of a linked data
structure for insertion with the e
ciency of binary search for retrieval. Given
random inputs, it is expected that a name can be inserted or found in
O
(
log n
)
time, where
n
is the number of names in the tree. Unfortunately, average-case
performance does not necessarily hold for symbol tables—programmers do
not choose identifier names at random! Thus, a tree of
n
names could have
depth
n
, causing name lookup to take
O
(
n
) time. An advantage of binary
search trees is their simple, widely known implementation. This simplicity
and the common perception of reasonable average-case performance make
binary search trees a popular technique for implementing symbol tables. As
with the list structures, each name (node) in the binary search tree is actually
a stack of currently active scopes that declare the name.
Balanced Trees
The worst-case scenario for a binary search tree can be avoided if a search tree
can be maintained in
balanced
form. The time spent balancing the tree can be
amortized over all operations so that a symbol can be inserted or found in
O
(
log n
) time, where
n
is the number of names in the tree. Examples of such
trees include red-black trees and splay trees. Exercises 9 and 10 further explore
symbol table implementations based on balanced-tree structures.
Hash Tables
Hash tables are the most common mechanism for managing symbol tables,
owing to their excellent performance. Given a su
ciently large table, a good
hash function, and appropriate collision-handling techniques, insertion or re-
trieval can performed in constant time, regardless of the number of entries in
the table. The implementation discussed in Section 8.3.3 uses a hash table, with
collisions handled by chaining. Hash tables are widely implemented. Some
languages (including Java) contain hash table implementations in their core
