Wo finde ich eine Standard-basierte Kartenimplementierung in Java?

Ich habe ein Java-Programm, das viele Zuordnungen von Strings zu verschiedenen Objekten speichert.

Im Moment sind meine Optionen entweder Hashing (via HashMap) oder Binärsuche (via TreeMap). Ich frage mich, ob es eine effiziente und standardmäßige trie-basierte Kartenimplementierung in einer beliebten und hochwertigen Bibliothek gibt.

Ich habe in der Vergangenheit meine eigene geschrieben, aber ich würde lieber mit etwas Standard gehen, wenn verfügbar.

Schnelle Klärung: Während meine Frage allgemein ist, habe ich es im aktuellen Projekt mit vielen Daten zu tun, die durch vollständig qualifizierte classnnamen oder Methodensignaturen indiziert werden. Daher gibt es viele gemeinsame Präfixe.

Solutions Collecting From Web of "Wo finde ich eine Standard-basierte Kartenimplementierung in Java?"

Vielleicht möchten Sie sich die Trie-Implementierung ansehen , die Limewire zur Google Guava beiträgt .

In den Java-corebibliotheken gibt es keine Trie-Datenstruktur.

Dies liegt möglicherweise daran, dass Versuche normalerweise zum Speichern von Zeichenketten konzipiert sind, während Java-Datenstrukturen allgemeiner sind und normalerweise jedes Object (Gleichheit und eine Hash-Operation definieren), obwohl sie manchmal auf Comparable Objekte (Definieren einer Reihenfolge) beschränkt sind. Es gibt keine übliche Abstraktion für “eine Folge von Symbolen”, obwohl CharSequence für Zeichenketten geeignet ist, und ich nehme an, Sie könnten etwas mit Iterable für andere Arten von Symbolen tun.

Hier ist noch ein weiterer Punkt: Wenn Sie versuchen, einen herkömmlichen Trie in Java zu implementieren, werden Sie schnell mit der Tatsache konfrontiert, dass Java Unicode unterstützt. Um jede Art von Speicherplatzeffizienz zu haben, müssen Sie die Zeichenfolgen in Ihrem Trie auf eine Teilmenge von Symbolen beschränken oder den herkömmlichen Ansatz des Speicherns von Kindknoten in einem durch ein Symbol indizierten Array aufgeben. Dies könnte ein weiterer Grund sein, warum Versuche nicht als allgemein genug für die Aufnahme in die Core-Bibliothek angesehen werden und etwas, auf das Sie achten sollten, wenn Sie Ihre eigenen implementieren oder eine Bibliothek eines Drittanbieters verwenden.

Überprüfen Sie auch gleichzeitig Bäume . Sie unterstützen sowohl Radix- als auch Suffix-Bäume und sind für Umgebungen mit hohem Parallelitätsgrad konzipiert.

Apache Commons Collections v4.0 unterstützt jetzt Trie-Strukturen.

Weitere Informationen finden Sie in den org.apache.commons.collections4.trie Paketinformationen . Überprüfen Sie insbesondere die PatriciaTrie class:

Implementierung eines PATRICIA Trie (praktischer Algorithmus zum Abrufen alphanumerisch codierter Informationen).

Eine PATRICIA Trie ist eine komprimierte Trie. Anstatt alle Daten an den Kanten des Trie zu speichern (und leere interne Knoten zu haben), speichert PATRICIA Daten in jedem Knoten. Dies ermöglicht sehr effiziente Traversierungs-, Einfüge-, Lösch-, Vorgänger-, Nachfolger-, Präfix-, Bereichs- und Auswahloperationen (Object). Alle Operationen werden im schlechtesten Fall in der O (K) Zeit ausgeführt, wobei K die Anzahl der Bits in dem größten Element in dem Baum ist. In der Praxis benötigen Operationen tatsächlich O (A (K)) Zeit, wobei A (K) die durchschnittliche Anzahl von Bits aller Elemente in dem Baum ist.

Ich habe hier eine einfache und schnelle Implementierung geschrieben und veröffentlicht.

Was Sie brauchen, ist org.apache.commons.collections.FastTreeMap , denke ich.

Apaches Commons-Sammlungen: org.apache.commons.collections4.trie.PatriciaTrie

Sie können sich auch diesen TopCoder anschauen (Registrierung erforderlich …).

Wenn Sie eine sortierte Karte benötigen, dann sind Versuche lohnenswert. Wenn du das nicht machst, ist hashmap besser. Hashmap mit Stringschlüsseln kann gegenüber der Standard-Java-Implementierung verbessert werden: Array-Hash-Map

Wenn Sie sich nicht darum sorgen, die Scala-Bibliothek zu übernehmen, können Sie diese raumsparende Implementierung verwenden, die ich von einem Burst-Trie geschrieben habe .

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

Im Folgenden finden Sie eine grundlegende HashMap-Implementierung eines Trie. Manche Leute könnten das nützlich finden …

 class Trie { HashMap root; public Trie() { root = new HashMap(); } public void addWord(String word) { 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()); } node = node.get(currentLetter); } } public boolean containsPrefix(String word) { 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; } } 

Hier ist meine Implementierung, genießen Sie es über: 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 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 getAllDistinctWords() { allDistinctWords = new ArrayList(); depthSearchWord(0, ""); return allDistinctWords; } public int getWordCount(String str) { int len = str.length(); int p = 0; for(int i=0;i 0; } public void insert(String str) { int len = str.length(); int p = 0; for(int i=0;i 

Ich habe gerade meine eigene Concurrent-TRIE-Implementierung ausprobiert, basiert aber nicht auf Zeichen, sondern auf HashCode. Immer noch können wir dies mit Map of Map für jeden CHAR-Hasencode verwenden.
Sie können dies mit dem Code https://github.com/skanagavelu/TrieHashMap/blob/master/src/TrieMapPerformanceTest.java https://github.com/skanagavelu/TrieHashMap/blob/master/src/TrieMapValidationTest.java testen

 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 array; //This is needed to ensure array elements are volatile public Edge(int size) { array = new AtomicReferenceArray(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; } } 

Sie können die Completely Java-Bibliothek mit einer PatriciaTrie- Implementierung testen . Die API ist klein und einfach zu starten, und sie ist im zentralen Repository von Maven verfügbar.