quel type de structure de données est le meilleur?

Question

Dans ma demande, nous avons déjà

Map<String, List<String>> 

Maintenant, nous avons eu une autre utilisation cas où la nécessité de trouver une clé qui est mis en correspondance avec une chaîne particulière dans la liste.

Je pense à l'écriture suivante:

string getKey(Map<String, List<String>> m, String str) { 
    for (Entry<String, List<String>> entry :m.entrySet()) { 
    if(entry.getValue().contains(str)) { 
     retrun entry.getKey(); 
    } 
    } 
    return null; 
} 

Map peut avoir à entrées max 2000. et chaque List peut avoir au maximum 500 String s.

Des suggestions qui pourraient être mieux adaptées? Je peux changer la structure de données initiale (Map) aussi s'il y a une meilleure manière de le faire.

Answer 1

Je suggérerais que vous ajoutiez une autre carte qui donne le mappage inverse - d'une chaîne à la liste des clés. Cela nécessitera un peu plus de travail pour rester synchronisé avec la première carte mais donnera les meilleures performances pour votre tâche. Cependant, si vous pensez que la fréquence de ces requêtes sera relativement faible, peut-être que votre solution pourrait être meilleure (bien que plus lente, le temps que vous économiserez pour conserver les deux cartes en synchronisation compensera cela).

Answer 2

Connaissez-vous l'API Guava? Si vous avez la liberté d'ajouter/modifier des dépendances, il vaut vraiment la peine de vérifier, en particulier les implémentations de l'interface Multimap. C'est exactement construit pour les cas où la même clé peut être mappée à plusieurs valeurs. Dans le cas où j'ai mal compris la question et la même clé ne sera pas mappée à plusieurs valeurs, vous devrez peut-être reformuler/repenser votre question comme votre idée actuelle Map<String, List<String>> est essentiellement juste cela.