符号表
Symbol Tables
Symbol tables is a data structure that supports key-value pair abstraction.
- Insert a value with specified key.
- Given a key, search for the corresponding value.
Some conventions.
- Values are not
null. - Method
get()returnsnullif key not present. - Method
put()overwrites old values with new value.
In Java implementation, Value type could be any generic type, Key type:
- If we specify
Comparablein API, assume keys areComparable, usecompareTo(). - Assume keys are any generic type, use
equals()to test equality. - Assume keys are any generic type, use
equals()to test equality, usehashCode()to scramble keys.
We will introduce several implementations of symbol tables below. They have different application scenarios.
- Elementary symbol table.
- Linked-list implementation with sequential search. [unordered keys]
- Resizing-array implementation with binary search. [ordered keys]
- BST-based symbol table. [ordered keys]
- Ordinary BST.
- Balanced Search Tree. (ex. 2-3 tree, red-black tree)
- Hash table. [unordered keys]
See the ordered symbol table API below. (Note that BST-based symbol table is also ordered)
java
public class ST<Key extends Comparable<Key>, Value> {
ST();
void put(Key key, Value val);
Value get(Key key);
void delete(Key key);
boolean contains(Key key);
boolean isEmpty();
int size();
Key min();
Key max();
Key floor(Key key);
Key ceiling(Key key);
int rank(Key key);
Key select(int k);
void deleteMin();
void deleteMax();
int size(Key lo, Key hi);
Iterable<Key> keys(Key lo, Key hi);
Iterable<Key> keys();
}
