Trouver la position de l'élément dans un TreeMap Java

une fois que vous avez construit votre arborescence, copiez ses clés triées dans un tableau, et utilisez Arrays.binarySearch pour chercher l'index dans le temps O(logN). Si vous avez besoin de la valeur, faites une recherche sur la carte originale aussi.

Edit: c'est comme ça que vous copiez les clés dans un tableau

String[] mapKeys = new String[treeMap.size()];
int pos = 0;
for (String key : treeMap.keySet()) {
    mapKeys[pos++] = key;
}

il n'y a pas une telle implémentation dans le JDK lui-même. Bien que TreeMap itère naturel de commande de clés, ses structures de données internes sont toutes basées sur les arbres et de ne pas les tableaux (rappelez-vous que Maps ne pas commander de touches, par définition, malgré le cas d'utilisation très courant).

cela dit, vous devez faire un choix car il n'est pas possible D'avoir O(1) le temps de calcul pour vos critères de comparaison à la fois pour l'insertion dans le Map et indexOf(key) calcul. Cela est dû à le fait que l'ordre lexicographique n'est pas stable dans une structure de données mutable (par opposition à l'ordre d'insertion, par exemple). Un exemple: une fois que vous insérez la première paire clé-valeur (entrée) dans la carte, sa position sera toujours un. Cependant, selon la deuxième touche insérée, cette position peut changer car la nouvelle touche peut être "plus grande" ou" plus basse " que celle de la touche Map. Vous pouvez certainement mettre en œuvre ceci en maintenant et en mettant à jour une liste indexée de clés pendant l'opération d'insertion, mais ensuite, vous devrez O(n log(n)) pour vos opérations d'insertion (besoin de commander à nouveau un tableau). Cela peut être souhaitable ou non, selon vos modèles d'accès aux données.

ListOrderedMap et LinkedMap dans Apache Commons, les deux se rapprochent de ce dont vous avez besoin, mais dépendent de l'ordre d'insertion. Vous pouvez vérifier leur mise en œuvre et de développer votre propre solution au problème avec peu à modérée effort, je crois (qui devrait être juste une question de remplacer le ListOrderedMap s tableau de soutien interne avec un liste triée - TreeList dans Apache Commons, par exemple).

vous pouvez également calculer l'indice vous - même, en soustrayant le nombre d'éléments qui sont inférieurs à la clé donnée (ce qui devrait être plus rapide qu'en effectuant une itération dans la liste à la recherche de votre élément, dans le cas le plus fréquent-car vous ne comparez rien).

une solution alternative serait d'utiliser TreeMapheadMap méthode. Si le mot existe dans le TreeMap, puis size() de sa tête est égale à l'index du mot dans le dictionnaire. C'est peut-être un peu inutile par rapport à mon autre réponse, à travers.

Ici est de savoir comment vous code en Java:

import java.util.*;

class Test {
    public static void main(String[] args) {
        TreeMap<String,String> tm = new TreeMap<String,String>();
        tm.put("quick", "one");
        tm.put("brown", "two");
        tm.put("fox", "three");
        tm.put("jumps", "four");
        tm.put("over", "five");
        tm.put("the", "six");
        tm.put("lazy", "seven");
        tm.put("dog", "eight");
        for (String s : new String[] {
            "quick", "brown", "fox", "jumps", "over",
            "the", "lazy", "dog", "before", "way_after"}
        ) {
            if (tm.containsKey(s)) {
                // Here is the operation you are looking for.
                // It does not work for items not in the dictionary.
                int pos = tm.headMap(s).size();
                System.out.println("Key '"+s+"' is at the position "+pos);
            } else {
                System.out.println("Key '"+s+"' is not found");
            }
        }
    }
}

voici le résultat produit par le programme:

Key 'quick' is at the position 6
Key 'brown' is at the position 0
Key 'fox' is at the position 2
Key 'jumps' is at the position 3
Key 'over' is at the position 5
Key 'the' is at the position 7
Key 'lazy' is at the position 4
Key 'dog' is at the position 1
Key 'before' is not found
Key 'way_after' is not found

j'ai eu le même problème. Alors j'ai pris le code source de java.util.TreeMap et écrit IndexedTreeMap. Il implémente mon propre IndexedNavigableMap:

public interface IndexedNavigableMap<K, V> extends NavigableMap<K, V> {
   K exactKey(int index);
   Entry<K, V> exactEntry(int index);
   int keyIndex(K k);
}

l'implémentation est basée sur la mise à jour des poids des noeuds dans l'arbre rouge-noir quand il est modifié. Le poids est le nombre de noeuds enfant sous un noeud donné, plus un-moi. Par exemple, lorsqu'un arbre tourne à gauche:

    private void rotateLeft(Entry<K, V> p) {
    if (p != null) {
        Entry<K, V> r = p.right;

        int delta = getWeight(r.left) - getWeight(p.right);
        p.right = r.left;
        p.updateWeight(delta);

        if (r.left != null) {
            r.left.parent = p;
        }

        r.parent = p.parent;


        if (p.parent == null) {
            root = r;
        } else if (p.parent.left == p) {
            delta = getWeight(r) - getWeight(p.parent.left);
            p.parent.left = r;
            p.parent.updateWeight(delta);
        } else {
            delta = getWeight(r) - getWeight(p.parent.right);
            p.parent.right = r;
            p.parent.updateWeight(delta);
        }

        delta = getWeight(p) - getWeight(r.left);
        r.left = p;
        r.updateWeight(delta);

        p.parent = r;
    }
  }

updatewweight met tout simplement à jour les poids jusqu'à la racine:

   void updateWeight(int delta) {
        weight += delta;
        Entry<K, V> p = parent;
        while (p != null) {
            p.weight += delta;
            p = p.parent;
        }
    }

Et quand nous avons besoin de trouver l'élément à l'index ici est la mise en œuvre qui utilise des pondérations:

public K exactKey(int index) {
    if (index < 0 || index > size() - 1) {
        throw new ArrayIndexOutOfBoundsException();
    }
    return getExactKey(root, index);
}

private K getExactKey(Entry<K, V> e, int index) {
    if (e.left == null && index == 0) {
        return e.key;
    }
    if (e.left == null && e.right == null) {
        return e.key;
    }
    if (e.left != null && e.left.weight > index) {
        return getExactKey(e.left, index);
    }
    if (e.left != null && e.left.weight == index) {
        return e.key;
    }
    return getExactKey(e.right, index - (e.left == null ? 0 : e.left.weight) - 1);
}

est également très pratique pour trouver l'index d'une clé:

    public int keyIndex(K key) {
    if (key == null) {
        throw new NullPointerException();
    }
    Entry<K, V> e = getEntry(key);
    if (e == null) {
        throw new NullPointerException();
    }
    if (e == root) {
        return getWeight(e) - getWeight(e.right) - 1;//index to return
    }
    int index = 0;
    int cmp;
    if (e.left != null) {
        index += getWeight(e.left);
    }
    Entry<K, V> p = e.parent;
    // split comparator and comparable paths
    Comparator<? super K> cpr = comparator;
    if (cpr != null) {
        while (p != null) {
            cmp = cpr.compare(key, p.key);
            if (cmp > 0) {
                index += getWeight(p.left) + 1;
            }
            p = p.parent;
        }
    } else {
        Comparable<? super K> k = (Comparable<? super K>) key;
        while (p != null) {
            if (k.compareTo(p.key) > 0) {
                index += getWeight(p.left) + 1;
            }
            p = p.parent;
        }
    }
    return index;
}

J'implémenterai bientôt IndexedTreeSet, en attendant vous pouvez utiliser le jeu de touches de IndexedTreeMap.

mise à Jour: la version indexée de TreeSet est implémentée maintenant.

Vous pouvez découvrir le résultat de ce travail à https://github.com/geniot/indexed-tree-map

je suis D'accord avec Isolvieira. Peut-être la meilleure approche serait d'utiliser une structure différente de TreeMap.

cependant, si vous voulez toujours aller avec le calcul de l'index des clés, une solution serait de compter combien de clés sont inférieures à la clé que vous recherchez.

Voici un extrait de code:

    java.util.SortedMap<String, String> treeMap = new java.util.TreeMap<String, String>();
    treeMap.put("d", "content 4");
    treeMap.put("b", "content 2");
    treeMap.put("c", "content 3");
    treeMap.put("a", "content 1");

    String key = "d"; // key to get the index for
    System.out.println( treeMap.keySet() );

    final String firstKey = treeMap.firstKey(); // assuming treeMap structure doesn't change in the mean time
    System.out.format( "Index of %s is %d %n", key, treeMap.subMap(firstKey, key).size() );

Avez-vous pensé à rendre les valeurs dans votre TreeMap contenir la position dans votre dictionnaire? Je suis à l'aide d'un BitSet voici les détails de mon dossier.

cela ne fonctionne pas aussi bien que mon autre idée ci-dessous.

Map<String,Integer> dictionary = new TreeMap<String,Integer> ();

private void test () {
  // Construct my dictionary.
  buildDictionary();
  // Make my file data.
  String [] file1 = new String[] {
    "1", "3", "5"
  };
  BitSet fileDetails = getFileDetails(file1, dictionary);
  printFileDetails("File1", fileDetails);
}

private void printFileDetails(String fileName, BitSet details) {
  System.out.println("File: "+fileName);
  for ( int i = 0; i < details.length(); i++ ) {
    System.out.print ( details.get(i) ? 1: -1 );
    if ( i < details.length() - 1 ) {
      System.out.print ( "," );
    }
  }
}

private BitSet getFileDetails(String [] file, Map<String, Integer> dictionary ) {
  BitSet details = new BitSet();
  for ( String word : file ) {
    // The value in the dictionary is the index of the word in the dictionary.
    details.set(dictionary.get(word));
  }
  return details;
}

String [] dictionaryWords = new String[] {
  "1", "2", "3", "4", "5"
};

private void buildDictionary () {
  for ( String word : dictionaryWords ) {
    // Initially make the value 0. We will change that later.
    dictionary.put(word, 0);
  }
  // Make the indexes.
  int wordNum = 0;
  for ( String word : dictionary.keySet() ) {
    dictionary.put(word, wordNum++);
  }
}

ici la construction des détails du fichier se compose d'une seule recherche dans le TreeMap pour chaque mot dans le fichier.

si vous prévoyez d'utiliser le value dans le dictionnaire TreeMap pour quelque chose d'autre que vous peut toujours composer avec un Integer.

Ajouté

en y réfléchissant davantage, si le value champ Map est réservé pour quelque chose que vous pouvez toujours utiliser des touches spéciales qui calculent leur propre position dans le Map et comme String s pour comparaison.

private void test () {
  // Dictionary
  Map<PosKey, String> dictionary = new TreeMap<PosKey, String> ();
  // Fill it with words.
  String[] dictWords = new String[] {
                       "0", "1", "2", "3", "4", "5"};
  for ( String word : dictWords ) {
    dictionary.put( new PosKey( dictionary, word ), word );
  }
  // File
  String[] fileWords = new String[] {
                       "0", "2", "3", "5"};
  int[] file = new int[dictionary.size()];
  // Initially all -1.
  for ( int i = 0; i < file.length; i++ ) {
    file[i] = -1;
  }
  // Temp file words set.
  Set fileSet = new HashSet( Arrays.asList( fileWords ) );
  for ( PosKey key : dictionary.keySet() ) {
    if ( fileSet.contains( key.getKey() ) ) {
      file[key.getPosiion()] = 1;
    }
  }

  // Print out.
  System.out.println( Arrays.toString( file ) );
  // Prints: [1, -1, 1, 1, -1, 1]

}

class PosKey
    implements Comparable {
  final String key;
  // Initially -1
  int position = -1;
  // The map I am keying on.
  Map<PosKey, ?> map;

  public PosKey ( Map<PosKey, ?> map, String word ) {
    this.key = word;
    this.map = map;
  }

  public int getPosiion () {
    if ( position == -1 ) {
      // First access to the key.
      int pos = 0;
      // Calculate all positions in one loop.
      for ( PosKey k : map.keySet() ) {
        k.position = pos++;
      }
    }
    return position;
  }

  public String getKey () {
    return key;
  }

  public int compareTo ( Object it ) {
    return key.compareTo( ( ( PosKey )it ).key );
  }

  public int hashCode () {
    return key.hashCode();
  }
}

NB: suppose qu'une fois getPosition() a été appelé, le dictionnaire n'est pas changé.

je suggérerais que vous écriviez une liste de sélection pour stocker votre dictionnaire, puisque cela offrira toujours des recherches O(log N), l'insertion et la suppression tout en étant capable de fournir un index (les implémentations d'arbre ne peuvent généralement pas retourner un index puisque les noeuds ne le connaissent pas, et il y aurait un coût à les garder à jour). Malheureusement, L'implémentation java de Competientskiplistmap ne fournit pas d'index, vous devrez donc implémenter votre propre version.

Obtention de la index d'un élément serait O (log N), Si vous vouliez à la fois l'index et la valeur sans faire 2 recherches, alors vous auriez besoin de retourner un objet wrapper contenant les deux.