序

本文简单介绍下apache collection4中的PatriciaTrie的使用。

Trie树

Trie树，又称字典树，单词查找树或者前缀树，是一种用于快速检索的多叉树结构。

• 应用
  经常被搜索引擎系统用于文本词频统计。同时，它也是很多算法和复杂数据结构的基础，如后缀树，AC自动机等
• 优点
  最大限度地减少无谓的字符串比较，查询效率比哈希表高。
• 缺点
  如果系统中存在大量字符串且这些字符串基本没有公共前缀，则相应的trie树将非常消耗内存，这也是trie树的一个缺点。

maven

                
     
      org.apache.commons
                 
     
      commons-collections4
                 
     
      4.1
             
    

使用

@Test    public void testContains(){        PatriciaTrie
    
      t = new PatriciaTrie
     
      ();        t.put("ronak", 100.0);        t.put("ronald", 90.0);        t.put("rat", 50.0);        t.put("robert", 200.0);        t.put("bat", 44.0);        t.put("batman", 440.0);        System.out.println(t.containsKey("ronak"));        System.out.println(t.selectKey("ro"));        System.out.println(t.prefixMap("r"));        System.out.println(t.prefixMap("ro"));        System.out.println(t.prefixMap("ron"));    }
     
    

输出

truerobert{rat=50.0, robert=200.0, ronak=100.0, ronald=90.0}{robert=200.0, ronak=100.0, ronald=90.0}{ronak=100.0, ronald=90.0}

doc