Symbol tables

1.  Key-value pair abstraction. (Associative array abstraction. Associate one value with each key)

    a)  Insert a value with specified key.

    b)  Given a key, search for the corresponding value.

 

2.  Symbol Table Applications:

 

3.  Basic symbol table API:

public class ST<Key, Value> {
    ST() {...} //create a symbol table
    void put(Key key, Value val) {...} //put key-value pair into the table (remove key from table if value is null)
    Value get(Key key) {...} //value paired with key (null if key is absent)
    void delete(Key key) {...} //remove key (and its value) from table
    boolean contains(Key key) {...} //is there a value paired with key?
    boolean isEmpty() {...} //is the table empty?
    int size() {...} //number of key-value pairs in the table
    Iterable<Key> keys() {...} //all the keys in the table
}

 

4.  Java requirements for eaquals method: For any non-null references x, y and z:

    a)  Reflexive: x.equals(x) is true.

    b)  Symmetric: x.equals(y) iff y.equals(x).

    c)  Transitive: if x.equals(y) and y.equals(z), then x.equals(z).

    d)  Non-null: x.equals(null) is false.

 

5.  Standard "recipe" for writting equals method for user-defined types.

    a)  Optimization for reference equality.

    b)  Check against null.

    c)  Check that two objects are of the same type and cast.

    d)  Compare each significant field:

        1)  if field is a primitive type, use ==

        2)  if field is an object, use equals()

        3)  if field is an array, apply to each entry (alternatively, use Arrays.equals(a, b) or Arrays.deepEquals(a, b) )

    Best practices.

    a)  No need to use calculated fields that depend on other fields.

    b)  Compare fields mostly likely to differ first.

    c)  Make compareTo() consistent with equals().

 

6.  Frequency counter implementation:

public class FrequencyCounter
{
    public static void main(String[] args)
    {
        int minlen = Integer.parseInt(args[0]);
        ST<String, Integer> st = new ST<String, Integer>();
        while (!StdIn.isEmpty())
        {
            String word = StdIn.readString();
            if (word.length() < minlen) continue;
            if (!st.contains(word)) st.put(word, 1);
            else st.put(word, st.get(word) + 1);
        }
        String max = "";
        st.put(max, 0);
        for (String word : st.keys())
            if (st.get(word) > st.get(max))
                max = word;
        StdOut.println(max + " " + st.get(max));
    }
}

 

7.  Elementary Implementation by an unordered linked list:

    a)  Data structure : Maintain an (unordered) linked list of key-value pairs.

    b)  Search : Scan through all keys until find a match.

    c)  Insert : Scan through all keys until find a match; if no match add to front.

 

8.  Elementary Implementation by an ordered linked list:

    a)  Data structure : Maintain an ordered array of key-value pairs.

    b)  Key point : Binary Search

    c)  Problem : To insert, need to shift all greater keys over.

    d)  Rank helper function. How many keys < k :

    

public Value get(Key key)
{
    if (isEmpty()) return null;
    int i = rank(key);
    if (i < N && keys[i].compareTo(key) == 0) return vals[i];
    else return null;
}

private int rank(Key key)
{//binary search
    int lo = 0, hi = N-1;
    while (lo <= hi)
    {
        int mid = lo + (hi - lo) / 2;
        int cmp = key.compareTo(keys[mid]);
        if (cmp < 0) hi = mid - 1;
        else if (cmp > 0) lo = mid + 1;
        else if (cmp == 0) return mid;
    }
    return lo;
}

 

9.  Ordered Symbol Table API :

public class ST<Key extends Comparable<Key>, Value>
{
    ST() {...} //create an ordered symbol table
    void put(Key key, Value val) {...} //put key-value pair into the table (remove key from table if value is null)
    Value get(Key key) {...} //value paired with key (null if key is absent)
    void delete(Key key) {...} //remove key (and its value) from table
    boolean contains(Key key) {...} //is there a value paired with key?
    boolean isEmpty() {...} //is the table empty?
    int size() {...} //number of key-value pairs
    Key min() {...} //smallest key
    Key max() {...} //largest key
    Key floor(Key key) {...} //largest key less than or equal to key
    Key ceiling(Key key) {...} //smallest key greater than or equal to key
    int rank(Key key) {...} //number of keys less than key
    Key select(int k) {...} //key of rank k
    void deleteMin() {...} //delete smallest key
    void deleteMax() {...} //delete largest key
    int size(Key lo, Key hi) {...} //number of keys in [lo..hi]
    Iterable<Key> keys(Key lo, Key hi) {...} //keys in [lo..hi], in sorted order
    Iterable<Key> keys() {...} //all keys in the table, in sorted order
}