我在哪里可以find一个标准的基于Trie的Java地图实现?

我有一个Java程序,它存储了很多从Strings到各种对象的映射。

现在,我的select是要依靠哈希(通过HashMap)或二进制search(通过TreeMap)。 我想知道在stream行和高质量的collections库中是否有一个高效和标准的基于树的地图实现?

我以前写过自己的,但是如果可以的话,我宁愿select标准的东西。

快速澄清:虽然我的问题是一般的,在当前的项目中,我正在处理大量的数据是由完全合格的类名或方法签名索引。 因此,有许多共享前缀。

你可能想看看Limewire为 Google Guava 贡献的Trie实现 。

核心Java库中没有trie数据结构。

这可能是因为尝试通常被devise为存储string,而Java数据结构更通用,通常包含任何Object (定义相等和散列操作),尽pipe它们有时仅限于Comparable对象(定义顺序)。 虽然CharSequence适用于string,但对于“一系列符号”没有共同的抽象,我想你可以用Iterable做其他types的符号。

还有一点需要考虑:当试图在Java中实现传统的trie时,您很快就会遇到Java支持Unicode的事实。 为了具有任何空间效率,您必须将string限制在符号的某个子集中,或者放弃将子节点存储在由符号索引的数组中的传统方法。 这可能是另一个原因,为什么尝试不被认为是包含在核心库中的通用目标,还有一些需要注意的地方,如果你自己实现或使用第三方库。

同时检查并发树 。 它们支持Radix和后缀树,专为高并发环境而devise。

我在这里写了一个简单而快速的实现。

Apache Commons Collections v4.0现在支持trie结构。

有关更多信息,请参阅org.apache.commons.collections4.trie包信息。 特别要检查PatriciaTrie类:

PATRICIA Trie(用字母数字编码检索信息的实用algorithm)的实现。

帕特里夏·特里是一个压缩的特里。 PATRICIA将数据存储在每个节点中,而不是存储Trie边缘的所有数据(并且具有空的内部节点)。 这允许非常有效的遍历,插入,删除,前置,后继,前缀,范围和select(对象)操作。 所有的操作在O(K)时间最差的情况下执行,其中K是树中最大项中的比特数。 在实践中,操作实际上需要O(A(K))时间,其中A(K)是树中所有项的平均比特数。

你想要的是org.apache.commons.collections.FastTreeMap ,我想。

Apache的公共集合: org.apache.commons.collections4.trie.PatriciaTrie

你也可以看看这个TopCoder (需要注册…)。

如果你需要sorting的地图,那么尝试是值得的。 如果你不这样hashmap是更好的。 使用string键的HashMap可以在标准的Java实现中得到改进: Array哈希映射

如果您不担心拉入Scala库,那么可以使用我写的突发线索库这个空间高效的实现。

https://github.com/nbauernfeind/scala-burst-trie

下面是一个Trie的基本HashMap实现。 有些人可能会觉得这有用…

 class Trie { HashMap<Character, HashMap> root; public Trie() { root = new HashMap<Character, HashMap>(); } public void addWord(String word) { HashMap<Character, HashMap> node = root; for (int i = 0; i < word.length(); i++) { Character currentLetter = word.charAt(i); if (node.containsKey(currentLetter) == false) { node.put(currentLetter, new HashMap<Character, HashMap>()); } node = node.get(currentLetter); } } public boolean containsPrefix(String word) { HashMap<Character, HashMap> node = root; for (int i = 0; i < word.length(); i++) { Character currentLetter = word.charAt(i); if (node.containsKey(currentLetter)) { node = node.get(currentLetter); } else { return false; } } return true; } } 

这里是我的实现,通过: GitHub – MyTrie.java享受它

 /* usage: MyTrie trie = new MyTrie(); trie.insert("abcde"); trie.insert("abc"); trie.insert("sadas"); trie.insert("abc"); trie.insert("wqwqd"); System.out.println(trie.contains("abc")); System.out.println(trie.contains("abcd")); System.out.println(trie.contains("abcdefg")); System.out.println(trie.contains("ab")); System.out.println(trie.getWordCount("abc")); System.out.println(trie.getAllDistinctWords()); */ import java.util.*; public class MyTrie { private class Node { public int[] next = new int[26]; public int wordCount; public Node() { for(int i=0;i<26;i++) { next[i] = NULL; } wordCount = 0; } } private int curr; private Node[] nodes; private List<String> allDistinctWords; public final static int NULL = -1; public MyTrie() { nodes = new Node[100000]; nodes[0] = new Node(); curr = 1; } private int getIndex(char c) { return (int)(c - 'a'); } private void depthSearchWord(int x, String currWord) { for(int i=0;i<26;i++) { int p = nodes[x].next[i]; if(p != NULL) { String word = currWord + (char)(i + 'a'); if(nodes[p].wordCount > 0) { allDistinctWords.add(word); } depthSearchWord(p, word); } } } public List<String> getAllDistinctWords() { allDistinctWords = new ArrayList<String>(); depthSearchWord(0, ""); return allDistinctWords; } public int getWordCount(String str) { int len = str.length(); int p = 0; for(int i=0;i<len;i++) { int j = getIndex(str.charAt(i)); if(nodes[p].next[j] == NULL) { return 0; } p = nodes[p].next[j]; } return nodes[p].wordCount; } public boolean contains(String str) { int len = str.length(); int p = 0; for(int i=0;i<len;i++) { int j = getIndex(str.charAt(i)); if(nodes[p].next[j] == NULL) { return false; } p = nodes[p].next[j]; } return nodes[p].wordCount > 0; } public void insert(String str) { int len = str.length(); int p = 0; for(int i=0;i<len;i++) { int j = getIndex(str.charAt(i)); if(nodes[p].next[j] == NULL) { nodes[curr] = new Node(); nodes[p].next[j] = curr; curr++; } p = nodes[p].next[j]; } nodes[p].wordCount++; } } 

我刚刚尝试过我自己的并发TRIE实现,但不基于字符,它基于HashCode。 仍然我们可以使用这个具有Map的地图的每个CHAR hascode。
你可以使用代码@ https://github.com/skanagavelu/TrieMapPerformanceTest.java https://github.com/skanagavelu/TrieHashMap/blob/master/src/TrieMapValidationTest.java

 import java.util.concurrent.atomic.AtomicReferenceArray; public class TrieMap { public static int SIZEOFEDGE = 4; public static int OSIZE = 5000; } abstract class Node { public Node getLink(String key, int hash, int level){ throw new UnsupportedOperationException(); } public Node createLink(int hash, int level, String key, String val) { throw new UnsupportedOperationException(); } public Node removeLink(String key, int hash, int level){ throw new UnsupportedOperationException(); } } class Vertex extends Node { String key; volatile String val; volatile Vertex next; public Vertex(String key, String val) { this.key = key; this.val = val; } @Override public boolean equals(Object obj) { Vertex v = (Vertex) obj; return this.key.equals(v.key); } @Override public int hashCode() { return key.hashCode(); } @Override public String toString() { return key +"@"+key.hashCode(); } } class Edge extends Node { volatile AtomicReferenceArray<Node> array; //This is needed to ensure array elements are volatile public Edge(int size) { array = new AtomicReferenceArray<Node>(8); } @Override public Node getLink(String key, int hash, int level){ int index = Base10ToBaseX.getBaseXValueOnAtLevel(Base10ToBaseX.Base.BASE8, hash, level); Node returnVal = array.get(index); for(;;) { if(returnVal == null) { return null; } else if((returnVal instanceof Vertex)) { Vertex node = (Vertex) returnVal; for(;node != null; node = node.next) { if(node.key.equals(key)) { return node; } } return null; } else { //instanceof Edge level = level + 1; index = Base10ToBaseX.getBaseXValueOnAtLevel(Base10ToBaseX.Base.BASE8, hash, level); Edge e = (Edge) returnVal; returnVal = e.array.get(index); } } } @Override public Node createLink(int hash, int level, String key, String val) { //Remove size for(;;) { //Repeat the work on the current node, since some other thread modified this node int index = Base10ToBaseX.getBaseXValueOnAtLevel(Base10ToBaseX.Base.BASE8, hash, level); Node nodeAtIndex = array.get(index); if ( nodeAtIndex == null) { Vertex newV = new Vertex(key, val); boolean result = array.compareAndSet(index, null, newV); if(result == Boolean.TRUE) { return newV; } //continue; since new node is inserted by other thread, hence repeat it. } else if(nodeAtIndex instanceof Vertex) { Vertex vrtexAtIndex = (Vertex) nodeAtIndex; int newIndex = Base10ToBaseX.getBaseXValueOnAtLevel(Base10ToBaseX.Base.BASE8, vrtexAtIndex.hashCode(), level+1); int newIndex1 = Base10ToBaseX.getBaseXValueOnAtLevel(Base10ToBaseX.Base.BASE8, hash, level+1); Edge edge = new Edge(Base10ToBaseX.Base.BASE8.getLevelZeroMask()+1); if(newIndex != newIndex1) { Vertex newV = new Vertex(key, val); edge.array.set(newIndex, vrtexAtIndex); edge.array.set(newIndex1, newV); boolean result = array.compareAndSet(index, vrtexAtIndex, edge); //REPLACE vertex to edge if(result == Boolean.TRUE) { return newV; } //continue; since vrtexAtIndex may be removed or changed to Edge already. } else if(vrtexAtIndex.key.hashCode() == hash) {//vrtex.hash == hash) { HERE newIndex == newIndex1 synchronized (vrtexAtIndex) { boolean result = array.compareAndSet(index, vrtexAtIndex, vrtexAtIndex); //Double check this vertex is not removed. if(result == Boolean.TRUE) { Vertex prevV = vrtexAtIndex; for(;vrtexAtIndex != null; vrtexAtIndex = vrtexAtIndex.next) { prevV = vrtexAtIndex; // prevV is used to handle when vrtexAtIndex reached NULL if(vrtexAtIndex.key.equals(key)){ vrtexAtIndex.val = val; return vrtexAtIndex; } } Vertex newV = new Vertex(key, val); prevV.next = newV; // Within SYNCHRONIZATION since prevV.next may be added with some other. return newV; } //Continue; vrtexAtIndex got changed } } else { //HERE newIndex == newIndex1 BUT vrtex.hash != hash edge.array.set(newIndex, vrtexAtIndex); boolean result = array.compareAndSet(index, vrtexAtIndex, edge); //REPLACE vertex to edge if(result == Boolean.TRUE) { return edge.createLink(hash, (level + 1), key, val); } } } else { //instanceof Edge return nodeAtIndex.createLink(hash, (level + 1), key, val); } } } @Override public Node removeLink(String key, int hash, int level){ for(;;) { int index = Base10ToBaseX.getBaseXValueOnAtLevel(Base10ToBaseX.Base.BASE8, hash, level); Node returnVal = array.get(index); if(returnVal == null) { return null; } else if((returnVal instanceof Vertex)) { synchronized (returnVal) { Vertex node = (Vertex) returnVal; if(node.next == null) { if(node.key.equals(key)) { boolean result = array.compareAndSet(index, node, null); if(result == Boolean.TRUE) { return node; } continue; //Vertex may be changed to Edge } return null; //Nothing found; This is not the same vertex we are looking for. Here hashcode is same but key is different. } else { if(node.key.equals(key)) { //Removing the first node in the link boolean result = array.compareAndSet(index, node, node.next); if(result == Boolean.TRUE) { return node; } continue; //Vertex(node) may be changed to Edge, so try again. } Vertex prevV = node; // prevV is used to handle when vrtexAtIndex is found and to be removed from its previous node = node.next; for(;node != null; prevV = node, node = node.next) { if(node.key.equals(key)) { prevV.next = node.next; //Removing other than first node in the link return node; } } return null; //Nothing found in the linked list. } } } else { //instanceof Edge return returnVal.removeLink(key, hash, (level + 1)); } } } } class Base10ToBaseX { public static enum Base { /** * Integer is represented in 32 bit in 32 bit machine. * There we can split this integer no of bits into multiples of 1,2,4,8,16 bits */ BASE2(1,1,32), BASE4(3,2,16), BASE8(7,3,11)/* OCTAL*/, /*BASE10(3,2),*/ BASE16(15, 4, 8){ public String getFormattedValue(int val){ switch(val) { case 10: return "A"; case 11: return "B"; case 12: return "C"; case 13: return "D"; case 14: return "E"; case 15: return "F"; default: return "" + val; } } }, /*BASE32(31,5,1),*/ BASE256(255, 8, 4), /*BASE512(511,9),*/ Base65536(65535, 16, 2); private int LEVEL_0_MASK; private int LEVEL_1_ROTATION; private int MAX_ROTATION; Base(int levelZeroMask, int levelOneRotation, int maxPossibleRotation) { this.LEVEL_0_MASK = levelZeroMask; this.LEVEL_1_ROTATION = levelOneRotation; this.MAX_ROTATION = maxPossibleRotation; } int getLevelZeroMask(){ return LEVEL_0_MASK; } int getLevelOneRotation(){ return LEVEL_1_ROTATION; } int getMaxRotation(){ return MAX_ROTATION; } String getFormattedValue(int val){ return "" + val; } } public static int getBaseXValueOnAtLevel(Base base, int on, int level) { if(level > base.getMaxRotation() || level < 1) { return 0; //INVALID Input } int rotation = base.getLevelOneRotation(); int mask = base.getLevelZeroMask(); if(level > 1) { rotation = (level-1) * rotation; mask = mask << rotation; } else { rotation = 0; } return (on & mask) >>> rotation; } } 

您可以尝试完全 Java库,它具有PatriciaTrie实现。 这个API很小,很容易上手,并且可以在Maven中央仓库中find 。