• 在hash中，例如现在要输入两个串911，911456，如果要同时查询这两个串，且查询串的同时若hash中没有则存入。那么，这个查询与建立的过程就是先查询其中一个串911，没有，然后存入9、91、911；而后查询第二个串911456，没有然后存入9、91、911、9114、91145、911456。因为程序没有记忆功能，所以并不知道911在输入数据中出现过，只是照常以例行事，存入9、91、911、9114、911...。也就是说用hash必须先存入所有子串，然后for循环查询。
• 而trie树中，存入911后，已经记录911为出现的字符串，在存入911456的过程中就能发现而输出答案；倒过来亦可以，先存入911456，在存入911时，当指针指向最后一个1时，程序会发现这个1已经存在，说明911必定是某个字符串的前缀。

1.4、查询

• 3、有一个1G大小的一个文件，里面每一行是一个词，词的大小不超过16字节，内存限制大小是1M。返回频数最高的100个词。
• 9、1000万字符串，其中有些是重复的，需要把重复的全部去掉，保留没有重复的字符串。请怎么设计和实现？
• 10、 一个文本文件，大约有一万行，每行一个词，要求统计出其中最频繁出现的前10个词，请给出思想，给出时间复杂度分析。
• 13、 寻找热门查询：搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来，每个查询串的长度为1-255字节。假设目前有一千万个记录，这些查询 串的重复读比较高，虽然总数是1千万，但是如果去除重复和，不超过3百万个。一个查询串的重复度越高，说明查询它的用户越多，也就越热门。请你统计最热门 的10个查询串，要求使用的内存不能超过1G。
  (1) 请描述你解决这个问题的思路；
  (2) 请给出主要的处理流程，算法，以及算法的复杂度。

  public class TrieST<Value> {    private static final int R = 256;        // extended ASCII    private Node root;      // root of trie    private int n;          // number of keys in trie    // R-way trie node    private static class Node {        private Object val;        private Node[] next = new Node[R];    }   /**     * Initializes an empty string symbol table.     */    public TrieST() {    }    /**     * Returns the value associated with the given key.     * @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 NullPointerException if {@code key} is {@code null}     */    public Value get(String key) {        Node x = get(root, key, 0);        if (x == null) return null;        return (Value) x.val;    }    /**     * Does this symbol table contain the given key?     * @param key the key     * @return {@code true} if this symbol table contains {@code key} and     *     {@code false} otherwise     * @throws NullPointerException if {@code key} is {@code null}     */    public boolean contains(String key) {        return get(key) != null;    }    private Node get(Node x, String key, int d) {        if (x == null) return null;        if (d == key.length()) return x;        char c = key.charAt(d);        return get(x.next[c], key, d+1);    }    /**     * Inserts the key-value pair into the symbol table, overwriting the old value     * with the new value if the key is already in the symbol table.     * If the value is {@code null}, this effectively deletes the key from the symbol table.     * @param key the key     * @param val the value     * @throws NullPointerException if {@code key} is {@code null}     */    public void put(String key, Value val) {        if (val == null) delete(key);        else root = put(root, key, val, 0);    }    private Node put(Node x, String key, Value val, int d) {        if (x == null) x = new Node();        if (d == key.length()) {            if (x.val == null) n++;            x.val = val;            return x;        }        char c = key.charAt(d);        x.next[c] = put(x.next[c], key, val, d+1);        return x;    }    /**     * 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;    }    /**     * Is this symbol table empty?     * @return {@code true} if this symbol table is empty and {@code false} otherwise     */    public boolean isEmpty() {        return size() == 0;    }    /**     * 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 as an {@code Iterable}     */    public Iterable<String> keys() {        return keysWithPrefix("");    }    /**     * Returns all of the keys in the set that start with {@code prefix}.     * @param prefix the prefix     * @return all of the keys in the set that start with {@code prefix},     *     as an iterable     */    public Iterable<String> keysWithPrefix(String prefix) {        Queue<String> results = new Queue<String>();        Node x = get(root, prefix, 0);        collect(x, new StringBuilder(prefix), results);        return results;    }    private void collect(Node x, StringBuilder prefix, Queue<String> results) {        if (x == null) return;        if (x.val != null) results.enqueue(prefix.toString());        for (char c = 0; c < R; c++) {            prefix.append(c);            collect(x.next[c], prefix, results);            prefix.deleteCharAt(prefix.length() - 1);        }    }    /**     * Returns all of the keys in the symbol table that match {@code pattern},     * where . symbol is treated as a wildcard character.     * @param pattern the pattern     * @return all of the keys in the symbol table that match {@code pattern},     *     as an iterable, where . is treated as a wildcard character.     */    public Iterable<String> keysThatMatch(String pattern) {        Queue<String> results = new Queue<String>();        collect(root, new StringBuilder(), pattern, results);        return results;    }    private void collect(Node x, StringBuilder prefix, String pattern, Queue<String> results) {        if (x == null) return;        int d = prefix.length();        if (d == pattern.length() && x.val != null)            results.enqueue(prefix.toString());        if (d == pattern.length())            return;        char c = pattern.charAt(d);        if (c == ‘.‘) {            for (char ch = 0; ch < R; ch++) {                prefix.append(ch);                collect(x.next[ch], prefix, pattern, results);                prefix.deleteCharAt(prefix.length() - 1);            }        }        else {            prefix.append(c);            collect(x.next[c], prefix, pattern, results);            prefix.deleteCharAt(prefix.length() - 1);        }    }    /**     * Returns the string in the symbol table that is the longest prefix of {@code query},     * or {@code null}, if no such string.     * @param query the query string     * @return the string in the symbol table that is the longest prefix of {@code query},     *     or {@code null} if no such string     * @throws NullPointerException if {@code query} is {@code null}     */    public String longestPrefixOf(String query) {        int length = longestPrefixOf(root, query, 0, -1);        if (length == -1) return null;        else return query.substring(0, length);    }    // returns the length of the longest string key in the subtrie    // rooted at x that is a prefix of the query string,    // assuming the first d character match and we have already    // found a prefix match of given length (-1 if no such match)    private int longestPrefixOf(Node x, String query, int d, int length) {        if (x == null) return length;        if (x.val != null) length = d;        if (d == query.length()) return length;        char c = query.charAt(d);        return longestPrefixOf(x.next[c], query, d+1, length);    }    /**     * Removes the key from the set if the key is present.     * @param key the key     * @throws NullPointerException if {@code key} is {@code null}     */    public void delete(String key) {        root = delete(root, key, 0);    }    private Node delete(Node x, String key, int d) {        if (x == null) return null;        if (d == key.length()) {            if (x.val != null) n--;            x.val = null;        }        else {            char c = key.charAt(d);            x.next[c] = delete(x.next[c], key, d+1);        }        // remove subtrie rooted at x if it is completely empty        if (x.val != null) return x;        for (int c = 0; c < R; c++)            if (x.next[c] != null)                return x;        return null;    }}