1. Tire树

Trie树，也叫字典树，是一种快速对子字符串（但不仅限于字符串）进行查询的树，是一种哈希树的变种。 具有最大限度地减少无谓的字符串比较的优点，具有极高的查询效率（高于哈希表）。

运行结果：

trie build: insert apple, banana, orange
---Search---
Search 'apple' : true
Search 'orange': true
Search 'pear'  : false
Search 'app'   : true
Search 'ban'   : true
Search 'grape' : false

2. 附1：源代码

public class Trie {

    public static void main(String[] args) {
        Trie trie = new Trie();

        // append words
        trie.insert("apple");
        trie.insert("banana");
        trie.insert("orange");
        System.out.println("trie build: insert apple, banana, orange\n---Search---");         // 输出: true

        // search
        System.out.println("Search 'apple' : " + trie.search("apple"));     // 输出: true
        System.out.println("Search 'orange': " + trie.search("orange"));    // 输出: true
        System.out.println("Search 'pear'  : " + trie.search("pear"));      // 输出: false 
        System.out.println("Search 'app'   : " + trie.startsWith("app"));   // 输出: true
        System.out.println("Search 'ban'   : " + trie.startsWith("ban"));   // 输出: true
        System.out.println("Search 'grape' : " + trie.startsWith("grape")); // 输出: false
    }

    private TrieNode root;
    public Trie() {
        root = new TrieNode();
    }

    public void insert(String word) {
        root.insert(word);
    }

    public boolean search(String word) {
        return root.search(word);
    }

    public boolean startsWith(String prefix) {
        return root.startsWith(prefix);
    }


    class TrieNode {
        private TrieNode[] children;
        private boolean isEndOfWord;

        public TrieNode() {
            children = new TrieNode[26]; // lower-case only
            isEndOfWord = false;
        }

        public void insert(String word) {
            TrieNode current = this;

            for (char c : word.toCharArray()) {
                int index = c - 'a';
                if (current.children[index] == null) {
                    current.children[index] = new TrieNode();
                }
                current = current.children[index];
            }

            current.isEndOfWord = true;
        }

        public boolean search(String word) {
            TrieNode current = this;

            for (char c : word.toCharArray()) {
                int index = c - 'a';
                if (current.children[index] == null) {
                    return false;
                }
                current = current.children[index];
            }

            return current.isEndOfWord;
        }

        public boolean startsWith(String prefix) {
            TrieNode current = this;

            for (char c : prefix.toCharArray()) {
                int index = c - 'a';
                if (current.children[index] == null) {
                    return false;
                }
                current = current.children[index];
            }

            return true;
        }
    }
}