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

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

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) pour générer la valeur booléenne de savoir si x est contenu dans le définir ou non? La probabilité pour! Contains() est d'environ 5 fois plus élevée.

Est-ce que toutes les structures de la carte fournissent o (1) opération? Est-ce que HashSet est le moyen le plus rapide?

Source

2010-07-16 codechobo

102

Regardez les implémentations basées sur set (Hashset, enumset) et hash (HashMap, linkedhash ..., idnetityhash ..). ils ont O (1) pour contient()

This cheatsheet est d'une grande aide.

Source

2010-07-16 17:57:43

Pour ce que ça vaut, les cartes de hachage en général ne sont pas O (1) dans la recherche lorsque des collisions de hachage se produisent (et elles peuvent arriver assez souvent, si très peu à la fois). Le pire des cas est O (n) dans la recherche. – Blindy

Je suis d'accord avec Blindy. Les performances de la collecte basée sur le hachage sont limitées par la performance de la fonction de hachage. – sbidwai

Quand je suis allé récemment, le site était en panne. Si cela vous arrive, vous pouvez utiliser ce lien [http://web.archive.org/web/20120105103844/http://www.coderfriendly.com/wp-content/uploads/2009/05/java_collections_v2. pdf) – EasilyBaffled

-2

hash (jeu de hachage) est le meilleur avec O (1)

Source

2010-07-16 18:07:10 Satish

Il y a 8 minutes entre votre réponse et celle de Pangea. Le vôtre n'ajoute aucune valeur supplémentaire, alors pourquoi l'afficher? –

@bart réelle connexion Internet lente – Will

@Will, peut-être. Si oui, alors maintenant @Satish a eu le temps d'enlever sa réponse redondante. Pourtant, il choisit de le laisser pendre. Peut-être dans l'espoir de recueillir certains points? Peut-être que c'était l'intention de commencer, qui sait? –

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

Source

2010-07-16 22:15:20 starblue

La seule structure de données plus rapide que HashSet est susceptible d'être TIntHashSet de Trove4J. Cela utilise des primitives évitant le besoin d'utiliser des objets entiers.

Si le nombre d'entiers est petit, vous pouvez créer un booléen [] où chaque valeur présente est transformée en "vrai". Ce sera O (1). Remarque: HashSet n'est pas garanti être O (1) et est plus susceptible d'être O (log (log (N))).

Vous obtiendrez seulement O (1) pour une distribution de hachage idéale. Cependant, il est plus probable que vous obtiendrez des collisions de seaux hachés et certaines recherches devront vérifier plus d'une valeur.

Source

2010-07-17 07:23:45

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

Répondre

Questions connexes