Symbol Tables

The primary purpose of a symbol table is to associate a value with a key. The client can insert key–value pairs into the symbol table with the expectation of later being able to search for the value associated with a given key.

We consider several design choices for our implementations to make our code consistent, compact, and useful.

• Generics. We consider the methods without specifying the types of keys and values being processed, using generics.

• Duplicate keys. Only one value is associated with each key (no duplicate keys in a table). When a client puts a key-value pair into a table already containing that key (and an associated value), the new value replaces the old one. These conventions define the associative array abstraction, where you can think of a symbol table as being just like an array, where keys are indices and values are array entries.

• Null values. No key can be associated with the value null. This convention is directly tied to our specification in the API that get() should return null for keys not in the table. This convention has two (intended) consequences: First, we can test whether or not the symbol table defines a value associated with a given key by testing whether get() returns null. Second, we can use the operation of calling put() with null as its second (value) argument to implement deletion.

• Deletion. Deletion in symbol tables generally involves one of two strategies: lazy deletion, where we associate keys in the table with null, then perhaps remove all such keys at some later time, and eager deletion, where we remove the key from the table immediately. As just discussed, the code put(key, null) is an easy (lazy) implementation of delete(key). When we give an (eager) implementation of delete(), it is intended to replace this default.

• Iterators. The keys() method returns an Iterable<Key> object for clients to use to iterate through the keys.

• Key equality. Java requires that all objects implement an equals() method and provides implementations both for standard types such as Integer, Double, and String and for more complicated types such as Date, File and URL. For applications involving these types of data, you can just use the built-in implementation. For example, if x and y are String values, then x.equals(y) is true if and only if x and y have the same length and are identical in each character position. In practice, keys might be more complicated, as in Person.java. For such client-defined keys, you need to override equals(). Java's convention is that equals() must implement an equivalence relation:
  • Reflexive: x.equals(x) is true.
  • Symmetric: x.equals(y) is true if and only if y.equals(x) is true.
  • Transitive: if x.equals(y) and y.equals(z) are true, then so is x.equals(z).

  In addition, equals() must take an Object as argument and satisfy the following properties:

  • Consistency: multiple invocations of x.equals(y) consistently return the same value, provided neither object is modified
  • Not null: x.equals(null) returns false.

  A best practice is to make Key types immutable, because consistency cannot otherwise be guaranteed.