Discussion :

[olibara]

Bonjour

Je vais essayer de me familiariser avec le HashSet mais je ne sais pas encore vraiment comment aborder le truc et si finalement il ne vaut pas mieux utiliser une liste

Voici le principe
J'ai une collection de string
A chaque string distinct j'aimerais attribuer une clef numerique ordinale
Pour la comparaison de string j'utilise une clef representant la string "nettoyée"

Je cree donc une classe

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
public Classe KString
{
   public string sKey;         // la clef
   public string sOrg;         // la string originale
   public int Val;                // la valeur attribuée
}

Avec une list, pas de probleme, je fais un compareur sur sKey; je verifie l'existense et j'insere si necessaire en attribuant a Val le Count+1 de ma liste


Mais avec un HashSet : comment peut fonctionner cette logique ?

Faire un Contains a la place du Find ca ne marchera evidement pas
Si c'est pour faire un find alors autant utiliser une liste

[olibara]

Salut

Bon j'ai dis deux conneries mais je me ratrappe :

1- Le HashSet n'a pas de methode Find, il ne connait que le contains, donc sauf erreur de ma part c'est pas tres souple utiliser si on ne travaille avec des objets simples style string, int, etc;

2- Considérant cela il semble que la liste soit le plus approprie sauf que j'ai oublié de mentionner qu'un aspect contraignant de la liste c'est l'obligation du tri apres chaque insertion

3- J'avais résolu ce point en C en creant une fonction bInsearch, qui faisait une recherche dichotomique mais qui generait l'insertion au bon endroit de la liste si la clef n'etait pas trouvée
Peut on faire ca avec les méthodes native cSharp sans tout réecrire ???

[The_badger_man]

N'as tu pas lu ce superbe tuto: http://badger.developpez.com/tutoriels/dotnet/hashset/ ?

Il faut que tu utilises un EqualityComparer.

[olibara]

C'est vrai j'ai loupé le tuto

Mais dans le EqualityComparer je dois definir une fonction de HashCode pour mon string et ca devient un peu lourd

Au passage le GetHashcode mentioné dans le tuto me semble bien léger !!!

Par ailleurs j'avais encore dit une autre connerie a propos de la liste, c'est evidement un BinaRySearch que je dois faire et pas un Find

[olibara]

Ouups

Je viens de voir qu'il y avait la fonction GetHashCode dans String, je suis passé fois a coté sans y faire attention !

Ca resoud evidement le probleme de l'equality comparer

Mais je me dis qu'il y a redondance

Si le Hashset a besoin qu'on lui donne la fonction de Hashage dans le compareur pourquoi a-il besoin de la fonction d'egalité ? Puisque le Hashcode qu'on lui donne est sencé etre unique

Si j'en deduit que ce HashCode n'est pas stocké pour creer un index sur le set a quoi sert le hashset ? Une liste peut faire la meme chose et plus !

[olibara]

N'as tu pas lu ce superbe tuto: http://badger.developpez.com/tutoriels/dotnet/hashset/ ?

Il faut que tu utilises un EqualityComparer.

Existe-t-il le meme tuto pour les dictionnaire ?
Je ne sais pas si pour ce que je veux faire un dictionnaire ou un Hashset sera mieux ?

[StormimOn]

Je ne sais pas si pour ce que je veux faire un dictionnaire ou un Hashset sera mieux ?

Si tu as besoin uniquement de gérer une liste sans doublon le HashSet suffit.
Si tu as besoin de gérer une paire clé/valeur afin de pouvoir retrouver rapidement la valeur connaissant la clé, utilise un dictionnaire.

[olibara]

Merci StormimOn

Mais sauf errreur de ma part la maniere dont j'utiliserais le HashSet c'est un peu comme si j'avais fait un dictionnaire non ?
J'ai encore du mal a distinguer les nuances entre les deux

Et comme je l'avais signalé je ne comprends pas tres bien pourquoi le Hashset a besoin du GetHashCode ET de la fonction d'egalité dans son comparer c'est un peu redondant il me semble ??

S'il a le HashCode il devrait pouvoir traiter l'egalité sur cette clef

Ou alors il peut gerer les double sur le meme hashcode et ca ne me semble pas bien expliqué dans la doc
Ou alors il ne maintiens pas de set indexé sur Hashcode

[StormimOn]

J'ai relu le post et comme dans ton cas comme tu as besoin de pouvoir accéder à un élément (pour gérer le nombre d'entrées identiques), le HashSet ne t'aidera pas. Je vais peut être taper à côté, mais tu cherches quelque chose dans ce style si j'ai bien compris

Classe KString et le comparateur pour le dictionnaire

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
public class KString
{
    private string _sKey;
    private string _sOrg;
 
    public string SKey
    {
        get { return _sKey; }
    }
 
    public string SOrg
    {
        get { return _sOrg; }
    }
 
    public KString(string sKey, string sOrg)
    {
        _sKey = sKey;
        _sOrg = sOrg;
    }
}
 
public class KStringComparer : IEqualityComparer<KString>
{
    bool IEqualityComparer<KString>.Equals(KString x, KString y)
    {
        return x.SKey.Equals(y.SKey);
    }
 
    int IEqualityComparer<KString>.GetHashCode(KString obj)
    {
        return obj.SKey.GetHashCode();
    }
}

Ajout des informations au dictionnaire

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
private Dictionary<KString, int> dico = new Dictionary<KString, int>(new KStringComparer());
 
private void Test()
{
    KString key = new KString("TEST", "T.e.s.t");
    AjoutDico(key);
 
    key = new KString("TEST", "t-é-s-t");
    AjoutDico(key);
 
    key = new KString("TEST", "T-e.S-t  ");
    AjoutDico(key);
}
 
private void AjoutDico(KString key)
{
    if (dico.ContainsKey(key))
    {
        dico[key] += 1;
    }
    else
    {
        dico[key] = 1;
    }
}

A ce stade, le dictionnaire contient une seule entrée, car elles sont toutes identiques du point de vue de la chaîne qui sert de clé (sKey). Pour chaque clé du dictionnaire, on aura comme valeur le nombre de chaînes "identiques" trouvées.

En espérant ne pas être à côté de la plaque

Et comme je l'avais signalé je ne comprends pas tres bien pourquoi le Hashset a besoin du GetHashCode ET de la fonction d'egalité dans son comparer c'est un peu redondant il me semble ??

IEqualityComparer impose de définir Equals ainsi que GetHashCode. Après peut être que seule la partie HashCode est utilisée, de ce côté j'avoue que je ne pourrais pas répondre ^^

[olibara]

Merci StorminOn

Tu as bien compris

Mais a mon avis ca marche tout aussi bien avec un Hashset

Pour autant bien entendu que la methode Contains utilise bien le comparer qu'on lui à donné

Il suffit d'ajouter dans ma classe Kstring le count et meme l'id ordinal que je vais attribuer a chaque nouvel clef !

Tu ne crois pas ?

[olibara]

En réfléchissant j'ai compris la nécessité d'avoir la fonction de comparaison d"'egalité EN PLUS de la génération du HashCode

D'ailleurs l'exemple du Tuto exploite implicitement cette nécessité !

Explication : le HashCode etant un int, il n'est pas tout a fait impossible que deux chaines distincte rendent le meme HashCode

Donc comme tout HashSet qui se respecte il y aura chainage des entités ayant le meme HashCode.
Le compareur d'égalité permettra de retrouver la clef exacte par recherche séquentielle interne

Il est certain qu'au moins le HashCode est discriminant, au plus le chainage est profond et on perds l'avantage du hashset, a l'extreme on se retrouve avec une bete liste chainée d'acces O(n)

A ce titre l'exemple du tuto est mauvais et enduit d'erreur

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
    public int GetHashCode(Personne p)
    {
        return (p.Id & 1);
    }

[olibara]

Je viens de capter qu'un fois qu'un élément est mis dans un HashSet on ne peut plus y acceder
Donc pour ce que je veux faire ca marche pas !

A moins de chipoter en detruisant l'element que je veux modifier afin d'ajouter le nouvel elément

Et du coup je conclus que l'usage d'un Hashset est vraiment tres limité !

Mais je constate que c'est la meme chose pour un Dictionary

Donc en pratique il n'existe pas la possibilité de maintenir un ensemble d'objet modifiables accessible en O(1)

C'est malheureux de consacrer tant d'effort pour proposer des Classe HashSet et Dictionary qui ne permettent que de l'ajout !

Je vais ressortir mes anciennes librairies en C, ecrire une fonction de dichotomie qui permet l'insertion dans une liste triée

Et ecrire un veritable Hashset qui permet de maintenir une clef O(1) sur un ensemble d'eléments modifiables !

[StormimOn]

Le but du HashSet c'est de pouvoir construire une collection sans doublons. Dans cette logique, l'intérêt d'accéder à un élément en particulier n'est pas important à ce moment car c'est l'ensemble que l'on considère et non pas une valeur en particulier. Enfin c'est mon avis.

Par contre le dictionnaire permet de faire ce que tu veux il me semble. Rien n'empêche d'avoir quelque chose comme

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

Dictionary<KString, KString> dico;

ou si on se limite à la clé qui est une chaîne

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

Dictionary<string, KString> dico;

Ca te permet d'accéder rapidement à un élément pour pouvoir le modifier.

[olibara]

Bonjour StormimOn


Ben non justement
A mon avis la seule chose que propose le dictionary en plus c'est la notion de clef
Mais ni le dictionary ni le Hashset de disposent de methode d'acces a la value (element stocké)

La methode contains rend un bool

Donc soit je dois passer par une List<T> en utilisant un BinarySearch et je suis en O(n) avec obligation de tri a chaque insertion

Soit j'utilise un HashSet en faisant un remove et un ajout si je veux modifier une valeur de l'objet

Ou quelque chose m'echappe encore !!

[StormimOn]

Mais ni le dictionary ni le Hashset de disposent de methode d'acces a la value (element stocké)

Avec un dictionnaire tu accèdes à la valeur depuis la clé, c'est tout l'intérêt du dictionnaire d'ailleurs (accès O(1) à une valeur connaissant la clé).

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
Dictionary<string, string> dico;
...
dico["TEST"] = "12345";
string valeur = dico["TEST"];
// valeur vaut "12345";

C'est sûr que si tu passes à côté de ça, tu passes à côté de tout ce qu'est le dictionnaire. Ou alors je suis con et j'ai rien compris de la discussion depuis le début

[olibara]

Non non tu n'est pas con !
C'est moi qui cherchait comme un con une methode d'acces style .Find

Je n'avais pas assimilé que l'acces se faisait implicitement par index sur la clef

Je viens de faire un petit test

Evidement si je fais dico["MaClef"] si ma clef n'est pas dans le dico, je ramasse une exception j'aurais essperé recevoir un null
Je dois maintenant trouver comment tester cela !

[StormimOn]

Evidement si je fais dico["MaClef"] si ma clef n'est pas dans le dico, je ramasse une exception j'aurais essperé recevoir un null

Si la partie valeur est une référence, null est une valeur valide, donc l'exception est la seule solution. Par contre tu as une méthode ContainsKey pour tester la présence de la clé

[olibara]

Voila je viens de remplacer avantageusement ma cuisine de sort et d'insert par un dictionaire !