Structure de données la plus rapide pour contains() en Java ?

Question

Quelle est la structure de données en Java qui a l'opération la plus rapide pour contains() ?

Par exemple, j'ai un ensemble de nombres { 1, 7, 12, 14, 20... }

Étant donné un autre nombre arbitraire x, quel est le moyen le plus rapide (en moyenne) de générer la valeur booléenne indiquant si x est contenu dans l'ensemble ou non ? La probabilité pour !contains() est environ 5 fois plus élevée.

Toutes les structures de cartes fournissent-elles une opération o(1) ? Le HashSet est-il la solution la plus rapide ?

Answer 1

Regardez les implémentations basées sur les ensembles (Hashset, enumset) et les hachages (HashMap, linkedhash..., idnetityhash...). elles ont O(1) pour contains().

Cette fiche d'information est d'une grande aide.

Answer 2

Pour votre cas particulier de nombres avec une densité relativement élevée, j'utiliserais un BitSet, qui sera plus rapide et beaucoup plus petit qu'un ensemble de hachage.

Answer 3

La seule structure de données plus rapide que HashSet est probablement TIntHashSet de Trove4J. Elle utilise des primitives, ce qui évite d'avoir recours aux Integer Objects.

Si le nombre d'entiers est faible, vous pouvez créer un boolean[] où chaque valeur présente est transformée en "vrai". Ce sera O(1). Remarque : il n'est pas garanti que HashSet soit O(1) et il est plus probable qu'il soit O(log(log(N))).

Vous n'obtiendrez que O(1) pour une distribution de hachage idéale. Cependant, il est plus probable que vous obteniez des collisions entre les buckets hachés et que certaines recherches nécessitent de vérifier plus d'une valeur.

Answer 4

Hashing(hash set) est le meilleur avec O(1)