Definition
A symbol table is a data structure for key-value pairs that supports two operations:
- insert (put) a new pair into the table
- search for (get) the value associated with a given key
- 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
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.
In a conventional array, keys are integer indices that we use to quickly access array values; in an associative array (symbol table), keys are of arbitrary type, but we can still use them to quickly access values.
Keys must not be null. As with many mechanisms in Java, use of a null key results in an exception at runtime
In java, no key can be associated with the value null.
Searching cost model
When studying symbol-table implementations, we count compares (equality tests or key comparisons). In (rare) cases where compares are not in the inner loop, we count array accesses.