J'ai besoin d'une structure de données avec les propriétés suivantes:
Aucune autre opération n'est requise pour cette structure. Une implémentation naïve avec une liste nécessitera presque O (1) heure pour le temps POP et O (n) pour ajouter (car toute la liste doit être vérifiée pour assurer unicité). J'utilise actuellement un arbre noir rouge pour répondre aux besoins de cette structure de données, mais je me demande si je peux utiliser quelque chose de moins compliqué pour atteindre presque la même performance.
Je préfère les réponses en C #, mais Java, JavaScript et C ++ sont également acceptables.
Ma question est similaire à Cette question , cependant Je n'ai pas besoin de rechercher ou de supprimer la valeur maximale ou minimale (ou même un type de valeur particulière), alors j'espérais qu'il y aurait des améliorations à cet égard. Si l'une des structures de cette question est appropriée ici, faites-le-moi savoir.
Donc, quelle structure de données ne permet que des éléments uniques, prend en charge rapidement et supprimer, et est moins compliqué qu'un arbre noir rouge?
3 Réponses :
Qu'en est-il de l'intégré hashset ?
Il contient uniquement des éléments uniques. Supprimer (POP) est O (1) et Ajouter est O (1) Sauf si le tableau interne doit être redimensionné.
Merci pour le pointeur. Je suis intéressé, cependant, dans la manière dont HashSet est mis en œuvre, au cas où je devrais faire la même chose pour d'autres langues. Si je comprends bien, Hashset n'a été introduit que dans .NET 3.5. Je suis inquiet, cependant, que Hashset, en raison de son nom, des comparaisons avec des codes de hash uniquement, plutôt que de comparer des éléments les uns aux autres. Si tel est le cas, un hashset n'est pas vraiment approprié.
Comme son nom l'indique, il est mis en œuvre comme une hache de hashtable, de sorte qu'il peut y avoir une recherche rapide des éléments.
Regarde mon édition. J'ai bien peur qu'un jeu de hachage ne soit pas approprié ici.
@Peter, le code de hachage est le premier chèque de rond, l'égalité est la seconde. En d'autres termes, lorsque les codes de hasch correspondent -> Vérifiez l'égalité complète. C'est ce qui le rend vite, il peut équilibrer à l'interne via le code de hachage et vérifier uniquement un petit nombre d'éléments pour l'égalité.
Ah, cela ferait des ensembles de hash plus appropriés alors. J'apprécierais cependant que si quelqu'un expliquerait des détails sur la manière de mettre en œuvre un hasch moi-même. Ce serait utile aux autres aussi. Cette réponse entre-temps semble être la meilleure.
Anthony a raison, s'il y a plus d'un élément avec le même hashcode, nous comparons simplement pour l'égalité pour obtenir / supprimer le bon élément.
@Peter: Dans ce cas, vous devriez poser une nouvelle question sur la mise en œuvre de Hashset, s'il n'a pas déjà été demandé.
Comme dit par Meta-Knight, un hashset est la structure de données la plus rapide à faire exactement cela. Les recherches et les déménagements prennent une heure constante O (1) (sauf dans de rares cas lorsque votre hachage est nul, puis vous avez besoin de multiples rénumes ou que vous utilisez un godet HashSet). Toutes les opérations sur un HASHSET prennent O (1) heure, le seul inconvénient est qu'il nécessite plus de mémoire, car le hachage est utilisé comme index dans un tableau (ou un autre bloc de mémoire alloué). Donc, à moins que vous soyez vraiment strict sur la mémoire, allez avec Hashset. Je n'explique que la raison pour laquelle vous devriez aller avec cette approche et que vous devriez accepter les méta-chevaliers de répondre comme étant la première fois.
Utilisation de HASHES est OK car vous remplacez généralement les fonctions HashCode () et Equals (). Ce que le hashset génère en interne génère le hachage, puis s'il est égal à l'égalité (juste en cas de collision de hachage). S'ils ne le sont pas, cela doit appeler une méthode pour faire quelque chose appelé REVASHING, qui génère un nouveau hachage qui est généralement un décalage pavé étrange à partir du hachage d'origine (non sûr si .NET le fait que d'autres langues font) et répète le processus si nécessaire. .
Merci. La mémoire n'est pas une préoccupation pour moi.
Les implémentations de hashset simples ne sont pas prudentes si vous vous attendez à une contribution des attaquants. Dans ce cas, ajoutez fonctionner peut prendre jusqu'à O (n ^ 2) au lieu de O (1). Voir Hash DOS Attack : Thehackernews.com/2011/12/... (et pour une introduction amusante: anchor.com.au/blog/2012/12/... )
Le .NET Framework était également vulnérable à l'attaque de hachage DOS en 2011: arstechnica.com/business/2011/12/... - il devrait être corrigé d'ici maintenant.
Suppression d'un élément aléatoire est assez facile d'un hashset ou d'un dictionnaire.
Tout est en moyenne O (1), que dans le monde réel signifie O (1).
Exemple: presque tout ce qui peut être comparé peut également être haché :) dans mon expérience.
J'aimerais savoir s'il y a quelqu'un qui sait quelque chose qui ne peut pas être haché. à mon expérience cela s'applique également à des comparaisons de points flottants avec la tolérance à l'aide de techniques spéciales. Un hachage Fonction pour une table de hachage n'a pas besoin d'être parfaite, il faut juste être assez bon.
De plus, si vos données sont très compliquées, les fonctions de hachage sont généralement moins compliquées que les arbres noirs rouges ou les arbres AVL.
Ils sont utiles car ils gardent les choses commandées, mais vous n'avez pas besoin de cela. Pour montrer comment faire un simple hashset, je vais considérer un dictionnaire simple avec des clés entier.
Cette implémentation est très rapide et très bonne pour les matrices rares pour des exemples.
Je n'ai pas écrit le code pour développer la table du seau, car il est ennuyeux et généralement une source de gros bugs, mais comme il s'agit d'une preuve de concept, elle devrait suffire.
Je n'ai pas écrit itérateur ni. Je l'ai écrit par rayure, il peut y avoir des bugs. Si vous errez si cette implémentation est bonne ou Ce n'est pas une implémentation très similaire de ce que le Framework .NET faire pour la classe de dictionnaire :) Pour en faire un hashset, supprimez simplement le t et vous avez un hashset d'entiers.
Si vous devez obtenir des hashcodes pour des objets génériques, utilisez simplement X.GetHashCode ou fournissez votre fonction de code de hachage. Pour écrire des itérateurs, vous devez modifier plusieurs choses, mais ne voulez pas ajouter trop d'autres choses Dans ce post :)