符号表可以使用链表来实现。

定义 API

实现

public class SequentialSearchST<Key, Value> {
    private int n = 0;
    private Node first = null;
    /**
     * 私有内部 Node 类来在链表中保存键和值。
     */
    private class Node {
        Key key;
        Value  val;
        Node next;
        public Node(Key key, Value val, Node next) {
            this.key = key;
            this.val = val;
            this.next = next;
        }
    }
    /**
     * 顺序地搜索链表查找给定的键（找到则返回相关联的值）。
     * @param key
     * @return
     */
    public Value get(Key key) {
        for(Node x = first; x != null; x = x.next) {
            if(key.equals(x.key)) return x.val;
        }
        return null;
    }
    /**
     * 顺序地搜索链表查找给定的键，如果找到则更新相关联的值，否则用给定的键值对创建一个新的结点并将其插入到链表的开头。
     * @param key
     * @param val
     */
    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++; //链表大小加 1
    }
    public void delete(Key key) {
        if(key == null) throw new IllegalArgumentException("argument to delete() is null");
        first = delete(first, key);
    }
    /**
     * 递归实现删除方法，如果链表过大会导致爆栈。
     * @param x
     * @param key
     * @return
     */
    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;
    }
    /**
     * 返回符号表的大小
     * @return
     */
    public int size() {
        return n;
    }
    /**
     * 根据 size() 是否为 0 来判断。
     * @return
     */
    public boolean isEmpty() {
        return size() == 0;
    }
    public static void main(String[] args) {
        SequentialSearchST<Integer, String> st = new SequentialSearchST<>();
        for(int i = 0; i < 10; i++) {
            //  生成随机字符串
            int leftLimit = 97; // letter 'a'
            int rightLimit = 122; // letter 'z'
            int targetStringLength = 10;
            Random random = new Random();
            String generatedString = random.ints(leftLimit, rightLimit + 1)
                    .limit(targetStringLength)
                    .collect(StringBuilder::new, StringBuilder::appendCodePoint, StringBuilder::append)
                    .toString();
            st.put(i, generatedString);
        }
        System.out.println("st.size(): " + st.size());
        st.delete(1);
        System.out.println("st.size(): " + st.size());
    }
}

使用链表实现符号表查找需要 次比较，插入也是需要 次比较。所以用链表实现是非常低效的。

参考：

• 《算法 4》 第三章 符号表