1 Symbol table

1 application & define

  • Key-value pair abstraction.
  • ・Insert a value with specified key.
  • ・Given a key, search for the corresponding value.

1 application

  • Ex. DNS lookup.
  • ・Insert domain name with specified IP address.

  • ・Given domain name, find corresponding IP address

  • web search

2 实现

  1. public class ST<Key extends Comparable<Key>, Value> implements Iterable<Key> {
  3.     private TreeMap<Key, Value> st;
  5.     /**
  6.      * Initializes an empty symbol table.
  7.      */
  8.     public ST() {
  9.         st = new TreeMap<Key, Value>();
  10.     }
  12.     public Value get(Key key) {
  13.         if (key == null) 
  14.             throw new IllegalArgumentException("calls get() with null key");
  15.         return st.get(key);
  16.     }
  19.     public void put(Key key, Value val) {
  20.         if (key == null) 
  21.             throw new IllegalArgumentException("calls put() with null key");
  22.         if (val == null) st.remove(key);
  23.         else             st.put(key, val);
  24.     }
  27.     public void delete(Key key) {
  28.         if (key == null) 
  29.             throw new IllegalArgumentException("calls delete() with null key");
  30.         st.remove(key);
  31.     }
  34.     public boolean contains(Key key) {
  35.         if (key == null) 
  36.             throw new IllegalArgumentException("calls contains() with null key");
  37.         return st.containsKey(key);
  38.     }
  41.     public int size() {
  42.         return st.size();
  43.     }
  46.     public boolean isEmpty() {
  47.         return size() == 0;
  48.     }
  50.     /**
  51.      * Returns all keys in this symbol table.
  52.      * <p>
  53.      * To iterate over all of the keys in the symbol table named {@code st},
  54.      * use the foreach notation: {@code for (Key key : st.keys())}.
  55.      *
  56.      * @return all keys in this symbol table
  57.      */
  58.     public Iterable<Key> keys() {
  59.         return st.keySet();
  60.     }
  62.     /**
  63.      * Returns all of the keys in this symbol table.
  64.      * To iterate over all of the keys in a symbol table named {@code st}, use the
  65.      * foreach notation: {@code for (Key key : st)}.
  66.      * <p>
  67.      * This method is provided for backward compatibility with the version from
  68.      * <em>Introduction to Programming in Java: An Interdisciplinary Approach.</em>
  69.      *
  70.      * @return     an iterator to all of the keys in this symbol table
  71.      * @deprecated Replaced by {@link #keys()}.
  72.      */
  73.     @Deprecated
  74.     public Iterator<Key> iterator() {
  75.         return st.keySet().iterator();
  76.     }
  78.     /**
  79.      * Returns the smallest key in this symbol table.
  80.      *
  81.      * @return the smallest key in this symbol table
  82.      * @throws NoSuchElementException if this symbol table is empty
  83.      */
  84.     public Key min() {
  85.         if (isEmpty()) 
  86.             throw new NoSuchElementException("calls min() with empty symbol table");
  87.         return st.firstKey();
  88.     }
  90.     /**
  91.      * Returns the largest key in this symbol table.
  92.      *
  93.      * @return the largest key in this symbol table
  94.      * @throws NoSuchElementException if this symbol table is empty
  95.      */
  96.     public Key max() {
  97.         if (isEmpty()) 
  98.             throw new NoSuchElementException("calls max() with empty symbol table");
  99.         return st.lastKey();
  100.     }
  102.     /**
  103.      * Returns the smallest key in this symbol table greater than or equal to {@code key}.
  104.      *
  105.      * @param  key the key
  106.      * @return the smallest key in this symbol table greater than or equal to {@code key}
  107.      * @throws NoSuchElementException if there is no such key
  108.      * @throws IllegalArgumentException if {@code key} is {@code null}
  109.      */
  110.     public Key ceiling(Key key) {
  111.         if (key == null) throw new IllegalArgumentException("argument to ceiling() is null");
  112.         Key k = st.ceilingKey(key);
  113.         if (k == null) throw new NoSuchElementException("all keys are less than " + key);
  114.         return k;
  115.     }
  117.     /**
  118.      * Returns the largest key in this symbol table less than or equal to {@code key}.
  119.      *
  120.      * @param  key the key
  121.      * @return the largest key in this symbol table less than or equal to {@code key}
  122.      * @throws NoSuchElementException if there is no such key
  123.      * @throws IllegalArgumentException if {@code key} is {@code null}
  124.      */
  125.     public Key floor(Key key) {
  126.         if (key == null) 
  127.             throw new IllegalArgumentException("argument to floor() is null");
  128.         Key k = st.floorKey(key);
  129.         if (k == null) 
  130.             throw new NoSuchElementException("all keys are greater than " + key);
  131.         return k;
  132.     }
  134.     /**
  135.      * Unit tests the {@code ST} data type.
  136.      *
  137.      * @param args the command-line arguments
  138.      */
  139.     public static void main(String[] args) {
  140.         ST<String, Integer> st = new ST<String, Integer>();
  141.         for (int i = 0; !StdIn.isEmpty(); i++) {
  142.             String key = StdIn.readString();
  143.             st.put(key, i);
  144.         }
  145.         for (String s : st.keys())
  146.             StdOut.println(s + " " + st.get(s));
  147.     }
  148. }

2 线性表

  • 主要API
  • get
  • put
  • delete
  • contains
  • isEmpty
  • Keys() =>遍历键

sq .png·

public class SequentialSearchST<Key, Value> {
    private int n;           // number of key-value pairs
    private Node first;      // the linked list of key-value pairs

    // a helper linked list data type
    private class Node {
        private Key key;
        private Value val;
        private Node next;

        public Node(Key key, Value val, Node next)  {
            this.key  = key;
            this.val  = val;
            this.next = next;
        }
    }

    /**
     * Initializes an empty symbol table.
     */
    public SequentialSearchST() {
    }

    /**
     * Returns the number of key-value pairs in this symbol table.
     *
     * @return the number of key-value pairs in this symbol table
     */
    public int size() {
        return n;
    }

    /**
     * Returns true if this symbol table is empty.
     *
     * @return {@code true} if this symbol table is empty;
     *         {@code false} otherwise
     */
    public boolean isEmpty() {
        return size() == 0;
    }

    /**
     * Returns true if this symbol table contains the specified key.
     *
     * @param  key the key
     * @return {@code true} if this symbol table contains {@code key};
     *         {@code false} otherwise
     * @throws IllegalArgumentException if {@code key} is {@code null}
     */
    public boolean contains(Key key) {
        if (key == null) 
            throw new IllegalArgumentException("argument to contains() is null");
        return get(key) != null;
    }

    /**
     * Returns the value associated with the given key in this symbol table.
     *
     * @param  key the key
     * @return the value associated with the given key if the key is in the symbol table
     *     and {@code null} if the key is not in the symbol table
     * @throws IllegalArgumentException if {@code key} is {@code null}
     */
    public Value get(Key key) {
        if (key == null) 
            throw new IllegalArgumentException("argument to get() is null"); 
        for (Node x = first; x != null; x = x.next) {
            if (key.equals(x.key))
                return x.val;
        }
        return null;
    }

    /**
     * Inserts the specified key-value pair into the symbol table, overwriting the old 
     * value with the new value if the symbol table already contains the specified key.
     * Deletes the specified key (and its associated value) from this symbol table
     * if the specified value is {@code null}.
     *
     * @param  key the key
     * @param  val the value
     * @throws IllegalArgumentException if {@code key} is {@code null}
     */
    public void put(Key key, Value val) {
        if (key == null) 
            throw new IllegalArgumentException("first argument to put() is null"); 
        if (val == null) {
            delete(key);
            return;
        }

        for (Node x = first; x != null; x = x.next) {
            if (key.equals(x.key)) {
                x.val = val;
                return;
            }
        }
        first = new Node(key, val, first);
        n++;
    }

    /**
     * Removes the specified key and its associated value from this symbol table     
     * (if the key is in this symbol table).    
     *
     * @param  key the key
     * @throws IllegalArgumentException if {@code key} is {@code null}
     */
    public void delete(Key key) {
        if (key == null) 
            throw new IllegalArgumentException("argument to delete() is null"); 
        first = delete(first, key);
    }

    // delete key in linked list beginning at Node x
    // warning: function call stack too large if table is large
    private Node delete(Node x, Key key) {
        if (x == null) return null;
        if (key.equals(x.key)) {
            n--;
            return x.next;
        }
        x.next = delete(x.next, key);
        return x;
    }


    /**
     * Returns all keys in the symbol table as an {@code Iterable}.
     * To iterate over all of the keys in the symbol table named {@code st},
     * use the foreach notation: {@code for (Key key : st.keys())}.
     *
     * @return all keys in the symbol table
     */
    public Iterable<Key> c()  {
        Queue<Key> queue = new Queue<Key>();
        for (Node x = first; x != null; x = x.next)
            queue.enqueue(x.key);
        return queue;
    }


    /**
     * Unit tests the {@code SequentialSearchST} data type.
     *
     * @param args the command-line arguments
     */
    public static void main(String[] args) {
        SequentialSearchST<String, Integer> st = new SequentialSearchST<String, Integer>();
        for (int i = 0; !StdIn.isEmpty(); i++) {
            String key = StdIn.readString();
            st.put(key, i);
        }
        for (String s : st.keys())
            StdOut.println(s + " " + st.get(s));
    }
}