Avatar billede farouche Nybegynder
03. november 2004 - 19:56 Der er 35 kommentarer og
1 løsning

Effektiv hashing

Hej jeg vil gerne ha' nogle forslag til den mest effektive metode til at beregne en hashvalue for en "Collection" bestående af simple Field objekter.


internal class Field
{
private string _fieldName;
private object _fieldValue;

public Field(string fieldName, object fieldValue)
{
  this._fieldName = fieldName;
  this._fieldValue = fieldValue;
}

public int GetHashcode()
{
  Return ????????
}
}

HashCode for Field klassen skal selvfølgelig baseres på en kombination af Name og Value.

Disse Field objekter gemmes i en HashTable :



internal class FieldGroup : Hashtable
{

public int GetHashCode()
{
  string key;
  Field fld;
 
  foreach (int key in this.Keys) {
    fld = this(key);
      ?????????
  }
}
}


FieldGroup fyldes med Fields efter følgende recept, med FieldName som key.



FieldGroup fg = new FieldGroup();
string aName;
object aValue;
fg(aName) = new Field(myName, myValue);



Jeg kunne godt tænke mig nogle bud på den mest effektive metode til at beregne en unik hashcode for sådan et FieldGroup objekt baseret på dennes Field objekter. Se venligst gennem fingre med den meget eksemplificerede kode :)


På forhånd tak
Avatar billede arne_v Ekspert
03. november 2004 - 20:07 #1
Den første løses vel nemmest med:

public int GetHashcode()
{
  return _fieldName.GetHashCode() + _fieldValue.GetHashCode();
}

Umiddelbart tror jeg at den både er hurtig og giver en god fordeling.
Avatar billede arne_v Ekspert
03. november 2004 - 20:10 #2
Den anden. Måske:

public int GetHashCode()
{
  int res = 0;
  string key;
  Field fld;
  foreach (int key in this.Keys) {
    fld = this(key);
    res + = fld.GetHashCode();
  }
  return res;
}

igen en ret simpel løsning.
Avatar billede arne_v Ekspert
03. november 2004 - 20:10 #3
Husk at du også skal implementere Equals.
Avatar billede farouche Nybegynder
03. november 2004 - 20:13 #4
den første der den holder da vist ikke hva'

Det kan meget nemt gi to ens hashværdier.

Forestil dig eksemplet :

fieldName = "4" og fieldValue = 5

sammenlignet med

fieldName = "3" og fieldValue = 6


Ved godt at det er meget konceptuelt, men teoretisk set vil en sådan situation kunne skabe samme hashværdi for to forskellige objekter
Avatar billede arne_v Ekspert
03. november 2004 - 20:18 #5
For det første er der altid forskellige værdier som giver samme hash code.

For det andet er jeg ikke helt overbevist om at dit eksempel giver samme værdi.
Avatar billede arne_v Ekspert
03. november 2004 - 20:20 #6
using System;

class MainClass
{
    public static void Main(string[] args)
    {
        Console.WriteLine("4".GetHashCode() + 5.GetHashCode());
        Console.WriteLine("3".GetHashCode() + 6.GetHashCode());
    }
}

output:

177558
177564

så nej !
Avatar billede arne_v Ekspert
03. november 2004 - 20:21 #7
Det er ikke helt nemt at lave god ehash funktioner, men du kan godt regne med at
Microsoft har gjordt et godt arbejde, så hvis din kode bygger oven på deres, så
går du ikke helt galt.
Avatar billede farouche Nybegynder
03. november 2004 - 20:22 #8
Nej nej det var ikke ment som noget der VILLE gi det samme, blot et eksempel på at det teoretisk kan ske.

Og kan det det, er det vel ikke brugbart f,eks. som key i en HashTable ??
Avatar billede arne_v Ekspert
03. november 2004 - 20:23 #9
Jo da.
Avatar billede arne_v Ekspert
03. november 2004 - 20:25 #10
En hashtable kan sagtens håndtere forskellige keys med samme hash værdi.

Det er en nødvendighed. Tænk på hvor mange forskellige string værdier der
er og hvor mange forskellige int værdier der findes. Logisk set må mange string værdier
hashes til samme int værdi.

Pointen er at hvis rigtigt mange værdier hashes til samme hash code så går det
ud over performance af Hashtable.

Men et tilfældigt match her og der gør ikke noget.
Avatar billede farouche Nybegynder
03. november 2004 - 20:26 #11
Så er der noget helt generelt jeg misforstår her. En hashtable laver så vidt jeg har erfaret sin sammenligning af om to objekter er ens ud fra en IHashCodeProvider.

Og kommer to forskellige objekter frem til samme HashVærdi vil en af dem jo ikke kunne være i HashTablen ???
Avatar billede arne_v Ekspert
03. november 2004 - 20:30 #12
Forkert.

Den bruger hash code til at lave et hurtigt opslag på det rigtige sted i
den interne data struktur.

Så sammenligner den selve objekterne med Equals.

Hvis det ikke matcher så finde den et andet sted til det forskellige objekt med
samme hash code.
Avatar billede farouche Nybegynder
03. november 2004 - 20:31 #13
Men en anden ting er at dit forslag som det er lavet i dit eksempel producerer en Arithmetic overflow, så det jeg gør isdet nu er dette :

Return (Me._fieldName.GetHashCode.ToString() + "|" + Me._fieldValue.GetHashCode.ToString()).GetHashCode

Synes bare den virker lidt søgt, men det kan godt være det er metoden :)
Avatar billede farouche Nybegynder
03. november 2004 - 20:32 #14
ok, ja så er det ogsåp vigtigt at implementere Equals optimalt, ja det har du ret i.
Avatar billede farouche Nybegynder
03. november 2004 - 20:33 #15
Den er nu implementeret som følger :
public override bool Equals(object obj)
{
Field toCompare = ((Field)obj);
return (this._fieldName.Equals(toCompare.FieldName)) & (this._fieldValue.Equals(toCompare.FieldValue));
}
Avatar billede arne_v Ekspert
03. november 2004 - 20:34 #16
En primitiv hash tabel kan laves som med 3 felter key,value,next.

Så allokerer du 200 elementer i alle 3 arrays.

Når du indsætter så tager du modulus 10 af hash code af key. Og bruger det
som index i arraysene. Hvis pladsen er tom indsætter du. Hvis pladsen er
i brug finder du det første frie plads med index >= 10 og lader next
i det først fundne pege på det index.
Avatar billede arne_v Ekspert
03. november 2004 - 20:35 #17
Return (Me._fieldName.GetHashCode.ToString() + "|" + Me._fieldValue.GetHashCode.ToString()).GetHashCode

forstår jeg ikke - den returnerer da ikke int
Avatar billede farouche Nybegynder
03. november 2004 - 20:35 #18
Ja du ved tydeligvis mere om det end jeg gør :)

Jeg kan godt se at det i kombination med Equals giver mening
Avatar billede arne_v Ekspert
03. november 2004 - 20:36 #19
Ja Equals er vigtig. Det står også meget meget tydeligt i dokumentationen for GetHashCode !
Avatar billede farouche Nybegynder
03. november 2004 - 20:36 #20
Jo den laver en GetHashCode på den samlede string
Avatar billede farouche Nybegynder
03. november 2004 - 20:37 #21
fik lige sneget noget VB kode ind i det, håber du kan abstrahere fra det ;)
Avatar billede arne_v Ekspert
03. november 2004 - 20:38 #22
Og der er ingen grund til at være bange for overflow !

C# laver ikke exception af den grund.

Og overflowede værdier er helt ok som hash codes.
Avatar billede arne_v Ekspert
03. november 2004 - 20:39 #23
Nå sådan.

Det kan du også.

Jeg er dog ikke sikker på at den er bedre.
Avatar billede farouche Nybegynder
03. november 2004 - 21:19 #24
Jeg har lige lavet et par performance målinger mellem at bruge streng metoden og din int metode hvor jeg godt nok dividerer med 2 for ikke at få overflow resultatet er ret overbevisende : (Jeg laver en distinct udvælgelse af records i en DataTable med 102.368 rows - Burde være rimelig worst case)

STRENGE

End DB SELECT: 8,55306506817516 sec.
Start DISTINCT VIEW
End DISTINCT VIEW: 2,5897787560622 sec.
Total count:  102368
Distinct count:  35


INT / 2

End DB SELECT: 8,50959844079225 sec.
Start DISTINCT VIEW
End DISTINCT VIEW: 1,3752819430457 sec.
Total count:  102368
Distinct count:  35


Så der er altså med disse datamængder næsten en faktor 2 til forskel
Avatar billede arne_v Ekspert
03. november 2004 - 21:27 #25
ToString og String+ koster lidt.

/2 mener jeg stadigvæk er overflødig.
Avatar billede farouche Nybegynder
03. november 2004 - 21:39 #26
det fejler uden men det er i VB, så måske er det derfor
Avatar billede arne_v Ekspert
03. november 2004 - 21:48 #27
Det kan muligvis godt gøre en forskel.
Avatar billede farouche Nybegynder
03. november 2004 - 21:58 #28
Ja det tror jeg.

Men det virker skam glimrende med / 2, den kan holde det unikt på over 100.000 objekter, så er jeg overbevist ;)
Avatar billede arne_v Ekspert
03. november 2004 - 22:10 #29
OK at jeg ligger et svar så
Avatar billede farouche Nybegynder
03. november 2004 - 22:28 #30
Har faktisk fået det optimeret endnu mere da du lærte mig at det der med det unikke ikke er 100% vitigt for hashcodes, bare equels styrer det. Så nu laver jeg kun hashcode på value, det barberede lidt mere af tiden, dog ikke så meget
Avatar billede arne_v Ekspert
03. november 2004 - 22:31 #31
Det er også OK.

Men vær opmærksom på at hvis du har mange Fields med samme value men forskellig name,
så vil det give dårlige lookup tider fordi de får samme hash code.
Avatar billede farouche Nybegynder
03. november 2004 - 22:40 #32
ok, ja jeg bør jo tage lookup performane med i min test
Avatar billede arne_v Ekspert
21. november 2004 - 20:33 #33
Tid at få afsluttet spørgsmålet ?
Avatar billede farouche Nybegynder
25. november 2004 - 00:17 #34
Jep sorry, den var røget i glemmebogen.
Avatar billede arne_v Ekspert
26. november 2004 - 23:03 #35
Du skal markere mit navn så det bliver blåt inden du klikker accepter.

Hvis du bare klikker accepter så sker der ikke noget.

(og spørg mig ikke hvorfor det er lavet sådan ...)
Avatar billede farouche Nybegynder
28. november 2004 - 12:58 #36
Hmmm, det var bedre
Avatar billede Ny bruger Nybegynder

Din løsning...

Tilladte BB-code-tags: [b]fed[/b] [i]kursiv[/i] [u]understreget[/u] Web- og emailadresser omdannes automatisk til links. Der sættes "nofollow" på alle links.

Loading billede Opret Preview
Kategori
IT-kurser om Microsoft 365, sikkerhed, personlig vækst, udvikling, digital markedsføring, grafisk design, SAP og forretningsanalyse.

Log ind eller opret profil

Hov!

For at kunne deltage på Computerworld Eksperten skal du være logget ind.

Det er heldigvis nemt at oprette en bruger: Det tager to minutter og du kan vælge at bruge enten e-mail, Facebook eller Google som login.

Du kan også logge ind via nedenstående tjenester