Le moyen le plus rapide de vérifier si une liste <String> contient une chaîne unique

Question

En gros, j'ai environ 1 000 000 de chaînes. Pour chaque demande, je dois vérifier si une chaîne appartient ou non à la liste.

La performance m'inquiète, alors quelle est la meilleure méthode? ArrayList ? Hacher?

Answer 1

Votre meilleur pari est d'utiliser un HashSet et de vérifier si une chaîne existe dans le jeu via l' contains() méthode. HashSets sont construits pour un accès rapide via l'utilisation de méthodes de l'Objet hashCode() et equals(). La Javadoc de HashSet membres de:

Cette classe offre constante de la performance en temps pour les opérations de base (ajouter, supprimer, contient et la taille),

HashSet magasins des objets dans des seaux de hachage qui est-à-dire que la valeur retournée par l' hashCode méthode permettra de déterminer quel contenant un objet est stocké. De cette façon, le montant de l'égalité des vérifications de l' HashSet a effectuer via l' equals() méthode est réduite à l'd'autres Objets dans le même compartiment de hachage.

Pour utiliser HashSets et HashMaps efficacement, vous devez vous conformer à l' equals et hashCode contrat décrites dans la javadoc. Dans le cas d' java.lang.String ces méthodes ont déjà été mises en œuvre pour ce faire.

Answer 2

En général, un HashSet vous donnera de meilleures performances, puisqu'il n'a pas à examiner chaque élément et de les comparer, comme une liste de tableaux, mais généralement compare à la plupart des quelques éléments, où le hashcodes sont égaux.

Cependant, pour 1M de chaînes, les performances de hashSet peut-être pas encore optimale. Beaucoup de défauts de cache va ralentir la recherche de l'ensemble. Si toutes les cordes sont tout aussi probable, alors c'est inévitable. Toutefois, si certaines chaînes sont le plus souvent demandées que d'autres, alors vous pouvez placer les chaînes communes dans un petit hashSet, et vérifier que tout d'abord, avant de vérifier l'ensemble plus vaste. La petite hashset doit être de taille à tenir dans le cache (par exemple, quelques centaines de K au plus). Frappe à la petite hashset sera alors très rapide, tandis que les consultations de la plus grande hashset procéder à une vitesse limitée par la bande passante de la mémoire.

Answer 3

Avant d'aller plus loin, veuillez considérer ceci: Pourquoi êtes-vous inquiet au sujet de la performance? Quelle est la fréquence de cette vérification appelé?

Comme pour les solutions possibles:

• Si la liste est déjà triée, puis vous pouvez utiliser java.util.Collections.binarySearch qui offre les mêmes caractéristiques de performance comme un java.util.TreeSet.

• Sinon, vous pouvez utiliser un java.util.HashSet que comme une caractéristique de performance de O(1). Notez que le calcul du hash code pour une chaîne qui n'en a pas encore calculé est un O(m) fonctionnement avec m=string.length(). Aussi garder à l'esprit que les tables de hachage ne travaille bien jusqu'à ce qu'ils atteignent un facteur de charge, c'est à dire les tables de hashage utilisera plus de mémoire que la plaine des listes. Le facteur de charge par défaut utilisé par HashSet est .75, ce qui signifie qu'en interne un HashSet pour 1e6 les objets à utiliser un tableau avec 1.3e6 entrées.

• Si le HashSet ne fonctionne pas pour vous (par exemple parce qu'il y a beaucoup de hachage-collisions, parce que la mémoire est serré ou parce qu'il y a beaucoup d'insertions), que de considérer l'aide d'un Trie. Recherche dans un Trie le pire des cas, la complexité de O(m), où m=string.length(). Un Trie a aussi quelques extra-avantages qui pourraient être utiles pour vous: par exemple, il peut vous donner le plus proche apte pour une chaîne de recherche. Mais gardez à l'esprit que le meilleur code pas de code, donc rouler votre propre Trie implementiation si les avantages emporte sur les coûts.

• Envisagez l'utilisation d'une base de données si vous souhaitez des requêtes plus complexes, par exemple correspondre à une sous-chaîne ou une expression régulière.

Answer 4

Je voudrais utiliser un Set , dans la plupart des cas HashSet c'est bien.

Answer 5

Avec un si grand nombre de cordes, je pense immédiatement à un Trie . Cela fonctionne mieux avec un ensemble de caractères plus limité (tels que des lettres) et / ou lorsque le début de nombreuses chaînes se chevauchent.