A Maintenant, étant donné qu'un est dans l'ensemble de hachage, je veux récupérer un dans O (1) donné (1) (qui est égal à A du point de vue de l'ensemble de hachage). P> hashset
égale () code> et
gethascode () code> sur ma classe personnalisée, je peux avoir un objet A et un autre objet A "qui sont pas em> égale par identité mais pour laquelle
est égal () code> renvoie
true code> et
gethascode () code> retourne le même code de hachage.
var a = new MyClass("A");
var a_prime = new MyClass("A");
Debug.Assert(a.Equals(a_prime));
Debug.Assert(a.GetHashCode() == a_prime.GetHashCode());
var set = new HashSet<MyClass>();
set.Add(a);
Debug.Assert(set.Contains(a_prime));
// This:
var retrieved_a = set.Get(a_prime);
3 Réponses :
Il n'y a pas de méthode sur Vous pouvez utiliser un dictionnaire hashset code> qui fait ce que vous voulez.
code> à la place: p>
var dict = new Dictionary<MyClass, MyClass>();
dict[a] = a;
Debug.Assert(dict.ContainsKey(a_prime));
var retrieved_a = dict[a_prime];
J'ai toujours évité de faire des dicts qui se cachent. Est-ce mauvaise pratique? Ou est-ce que je m'inquiète juste pour rien?
@Hans comme toujours, cela dépend. Pourquoi pensez-vous que c'est une mauvaise pratique? Pourquoi les évitez-vous?
@svick Je ne sais pas, ça me semble étrange. Je suppose que je n'ai pas de raisons concrètes pour l'éviter, mais je n'ai jamais eu à utiliser une construction comme ça, mais pour une raison quelconque en regardant dict [a] = A; code> me fait grincer .
Cela me fait aussi craindre. Si rien d'autre, il a une redondance évidente. Probablement ne valant pas la peine de résoudre sauf que vous ne frappiez pas un problème de performance, cependant.
Si je me rappelle correctement, Dictionnaire code> n'a pas d'implémentation de temps constante des opérations de sélection de base, tandis que
hashset code> a. Voici un moyen de la mettre en œuvre avec une recherche égale de temps constante, sans augmenter d'autres complexités de Hashset. Il est crucial d'utiliser cette approche si vous devez saisir de nombreux éléments aléatoires. Ce que j'écris ci-dessous est la syntaxe Java, comme je ne sais pas C #, mais l'idée est indépendante de la langue.
Désolé, le hasard était une faute de frappe, je voulais dire égal au lieu de aléatoire. J'ai corrigé la méthode maintenant. Fondamentalement, au lieu d'utiliser un hashset, j'utilise un hachemap et i> une arrachelist, contenant les mêmes éléments et avec le hashmap pointant vers les indices de cet élément dans la graisse. Au lieu de la simple "oui, j'ai déjà cette clé" à partir du hashmet, le hashmap dit "Oui, j'ai déjà cette clé et cela pointe vers l'entier i code>". Ensuite, dans le tableau, vous pouvez récupérer votre objet en prenant l'objet en position
i code>.
Merci pour les corrections! Maintenant, il est beaucoup plus pertinent! À titre de note latérale, je ferais toujours très attention à cette réclamation «temps constante». Je ne pense pas que les hashmaps ont garanti le pire cas-O (1) de récupération, je pense qu'il est moyen-o (1) et vous pouvez devenir beaucoup moins pire si vous, par exemple, WayRoldy Tinker avec GethashCode des clés des clés de la carte. Quoi qu'il en soit, supprimé -1 et le commentaire précédent, car il ne correspond pas à l'article tel qu'il est maintenant.
Vous avez raison, avec "temps constant", je voulais dire "temps moyen: constante".
C'est brillant, +1. Bien que la performance-ist dans moi implémenterait cela comme hashmap code> et implémenter les opérations définies manuellement.
Une petite correction, je pense: vous ne pouvez pas faire contenu.get (contenu.size () - 1) code> Après avoir supprimé l'élément du contenu
code>. Cela vous donnera le mauvais article. Il devrait être
indices.set (contenu.get (contenu.size () - 1), index); code> avant
contenu.Retirer (contenu.size () - 1); Code >
Pourquoi ne pas simplement utiliser un mappage de dictionnaire
A code> à
A code>?
Dupliqué possible de Comment récupérer l'article réel de HASHSET?
Un autre Comment-accès-the- Valeurs de référence-of-a-hashset-sans-énumération?