符号表

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() returns null if 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 Comparable in API, assume keys are Comparable, use compareTo().
  • Assume keys are any generic type, use equals() to test equality.
  • Assume keys are any generic type, use equals() to test equality, use hashCode() 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]

Order-of-Growth for symbol tables with  items

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();
}
CC BY-NC-SA 4.0
正在加载评论…