java - 通讯录的高效搜索

Question

假设我有一个对象的名字、姓氏和电子邮件(调用 AddressBook)。我使用什么数据结构(在 Java 中)来存储此对象，以便我需要按以某些字母开头的姓氏进行搜索。例如，如果姓氏是 John 或 Johnson，我按 John 查询，它应该返回姓氏以 John 开头的所有 AddressBook 对象。

最有效的方法是什么？

假设有 10 个姓 X 的人，那么我可以将这个 X 作为映射的键，其值为包含 10 个 AddressBook 对象的列表。

这里的姓氏可能是 X、X1、X12、X13、XA。在这方面需要帮助。

Answer 1

拍一个trie : 每个节点都将与姓氏以该节点中包含的字符串开头的一组人相关联。

[更新] 最好看看 Patricia Trie .或者甚至更好地将此代码作为 trie 的示例，它允许在前缀末尾使用通配符“*”标记节点，因此您可以查找诸如“John*”之类的内容:

/**
 * Tatiana trie -- variant of Patricia trie
 * (http://en.wikipedia.org/wiki/Patricia_tree, http://en.wikipedia.org/wiki/Trie)
 * in which edge associated not with substring, but with regular expressions.
 * <b>Every child node RE defines match-set which is proper subset of parent node ER's match-set.</b>
 * <b>Null keys aren't permitted</b>
 * <p/>
 * Following wildcards <b>at the end</b> of RE are accepted:
 * * -- any string of length >= 0
 * <p/>
 * Examples of valid RE: <pre>a, abra*, </pre>
 * Example of invalid RE: <pre>a*a</pre>
 * <p/>
 */
public class TatianaTree<T> {
    private final Node<T> root;

    /**
     * Creates tree with <code>null</code> associated with root node.
     */
    public TatianaTree() {
        this(null);
    }

    /**
     * Creates tree with given element associated with root node.
     *
     * @param el element to associate with root
     */
    public TatianaTree(T el) {
        root = new Node<T>(null, el);
    }

    public TatianaTree<T> add(Node<T> node) {
        if (null == node.key)
            throw new IllegalArgumentException("Can't add node with null key");
        root.add(node);
        return this;
    }

    public Node<T> findNode(String key) {
        return root.findNode(Node.normalize(key));
    }

    /**
     * Removes most-specific node which matches given key.
     *
     * @return element of type <code>T</code> associated with deleted node or <code>null</code>.
     *         The only case when <code>null</code> will be returned is when root node corresponds to given key.
     */
    public T remove(String key) {
        Node<T> node = findNode(key);
        if (root == node)
            return null;

        node.removeSelf();
        return node.el;
    }

    public Node<T> getRoot() {
        return root;
    }

    public static class Node<T> {
        private static final String INTERNAL_ROOT_KEY = ".*";
        private static final String ROOT_KEY = "*";
        private static final Pattern KEY_WRONG_FORMAT_PATTERN = Pattern.compile("\\*.+");

        private static final String ROOT_KEY_IN_NODE_MSG = "Can't add non-root node with root key";
        private static final String WRONG_KEY_FORMAT_MSG = "Valid format is ^[A-Za-z0-9_]+(\\*){0,1}$";

        private final String key;
        private final T el;
        private final List<Node<T>> children = new ArrayList<Node<T>>();
        private Node<T> parent;

        public Node(String key) {
            this(key, null);
        }

        public Node(String key, T el) {
            String k = INTERNAL_ROOT_KEY;
            if (null != key) {
                k = normalize(key);
            }

            this.key = k;
            this.el = el;
            this.parent = null;
        }

        /**
         * Subset-check function.
         *
         * @param s    string to check
         * @param base string to check against
         * @return <code>true</code> if base is superset of s, <code>false</code> otherwise
         */
        private boolean isSubset(String s, String base) {
            String shortestS = s.replaceFirst("\\*$", "");
            String baseRE = "^" + base;
            Pattern p = Pattern.compile(baseRE);
            return p.matcher(shortestS).matches();
        }

        public T getEl() {
            return el;
        }

        private void add(Node<T> node) {
            boolean addHere = true;

            for (Node<T> child : children) {
                if (isSubset(child.key, node.key)) {
                    insertAbove(node);
                    addHere = false;
                    break;
                } else if (isSubset(node.key, child.key)) {
                    child.add(node);
                    addHere = false;
                    break;
                }
            }
            if (addHere) {
                children.add(node);
                node.parent = this;
            }
        }

        private void insertAbove(Node<T> newSibling) {
            List<Node<T>> thisChildren = new ArrayList<Node<T>>(),
                    newNodeChildren = new ArrayList<Node<T>>();
            for (Node<T> child : children) {
                if (isSubset(child.key, newSibling.key)) {
                    newNodeChildren.add(child);
                    child.parent = newSibling;
                } else {
                    thisChildren.add(child);
                }
            }
            newSibling.children.clear();
            newSibling.children.addAll(newNodeChildren);

            this.children.clear();
            this.children.addAll(thisChildren);
            this.children.add(newSibling);
            newSibling.parent = this;
        }

        private Node<T> findNode(String key) {
            for (Node<T> child : children) {
                if (isSubset(key, child.key))
                    return child.findNode(key);
            }
            return this;
        }

        public int getChildrenCount() {
            return children.size();
        }

        private static String normalize(String k) {
            if (ROOT_KEY.equals(k))
                throw new IllegalArgumentException(ROOT_KEY_IN_NODE_MSG);
            k = k.replaceFirst("\\*$", ".*").replaceAll("\\[", "\\\\[").replaceAll("\\]", "\\\\]");
            Matcher m = KEY_WRONG_FORMAT_PATTERN.matcher(k);
            if (m.find())
                throw new IllegalArgumentException(WRONG_KEY_FORMAT_MSG);
            return k;
        }

        private void removeSelf() {
            parent.children.remove(this);
            for (TatianaTree.Node<T> child : children)
                child.parent = parent;
            parent.children.addAll(children);
        }
    }
}