Où puis-je trouver un standard Trie en fonction de la carte de mise en œuvre en Java?

Il n'y a pas de trie de la structure des données dans la base de bibliothèques Java.

Ce peut-être parce que la tente sont en général conçus pour stocker des chaînes de caractères, alors que Java des structures de données plus générales, généralement de la détention d'une Object (définition de l'égalité et une opération de hachage), même si elles sont parfois limitées à Comparable objets (de la définition d'un ordre). Il n'y a aucune commune de l'abstraction pour "une séquence de symboles," bien que CharSequence est adapté pour les chaînes de caractères, et je suppose que vous pourriez faire quelque chose avec Iterable pour d'autres types de symboles.

Voici un autre point à prendre en compte: lorsque vous essayez de mettre en œuvre un classique trie en Java, vous êtes rapidement confronté avec le fait que Java prend en charge Unicode. Pour toute sorte de l'efficacité de l'espace, vous devez restreindre les chaînes dans votre trie à un certain sous-ensemble de symboles, ou de renoncer à l'approche conventionnelle de stockage des nœuds enfants dans un tableau indexé par le symbole. Ce pourrait être une autre raison pour laquelle tente ne sont pas considérés comme usage général assez pour inclusion dans le noyau de la bibliothèque, et quelque chose à regarder si vous implémentez votre propre ou de l'utilisation d'une bibliothèque tierce.

Apache Commons Collections v4.0 prend désormais en charge trie structures.

Voir le org.apache.commons.collections4.trie paquet d'info pour plus d'informations. En particulier, vérifier la PatriciaTrie classe:

Mise en œuvre de PATRICIA Trie (Algorithme de Pratique pour Récupérer des Informations Codées dans Alphanumériques).

Une PATRICIA Trie est un comprimé Trie. Au lieu de stocker toutes les données sur les bords de la Trie (et d'avoir vide nœuds internes), PATRICIA stocke les données dans chaque nœud. Cela permet très efficace de la traversée, insérer, supprimer, prédécesseur, successeur, préfixe, la gamme, et sélectionnez(Objet) des opérations. Toutes les opérations sont effectuées au pire en O(K) temps, où K est le nombre de bits dans le plus grand élément dans l'arbre. Dans la pratique, les opérations de réellement prendre O(A(K)) le temps, où A(K) est le nombre moyen de bits de tous les éléments de l'arbre.

Apache commons collections:
org.apache.commons.collections4.trie.PatriciaTrie

Vous pouvez essayer le Complètement bibliothèque Java, il dispose d'un PatriciaTrie mise en œuvre. L'API est petit et facile à prendre en main, et il est disponible dans la Dépôt central de Maven.

Si vous devez triés carte, puis tente en valent la peine.
Si vous n'avez pas alors hashmap est mieux.
Table de hachage avec des clés de chaîne peut être amélioré au cours de la Java standard de mise en œuvre:
Tableau de hachage carte

Ci-dessous est une base HashMap mise en œuvre d'un Trie. Certaines personnes peuvent trouver cela utile...

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;
    }
}

J'ai juste essayé de faire de mon propre Simultanées TRIE de mise en œuvre, mais pas basé sur des personnages, il est basé sur HashCode. Néanmoins, On peut utiliser ceci pour avoir la Carte de la Carte pour chaque CHAR hascode.

Vous pouvez tester cela en utilisant le code @ https://github.com/skanagavelu/TrieHashMap/blob/master/src/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;
}
}