25. oktober 2006 - 06:00Der er
6 kommentarer og 1 løsning
Hashing i C#
Hej eksperter
Jeg mangler lidt hjælp til at lave en smart hashing funktion og tænkte, at jeg ville lufte mit problem herinde.
Jeg har en klasse A, der indeholder 2 instanser af en anden klasse B. B dækker primært over en List af ints og så lidt kløgtig logik(naturligvis).
Eksempel [ 01 02 03 ] [ 00 25 12 ]
Elementerne i listen i B kan kun antage følgende værdier [ 00 03 04 06 12 25 ] og der kan være op til ca 20 elementer i hver B liste
Jeg vil gerne gemme en unik hashcode for A i en dictionary sammen med et fitness tal, der er en funktion af, hvordan de 2 B lister så ud.
Det sjove ved den hashing funktion jeg gerne vil ende op med er at min fitness værdi vil være det samme for totalt 4 symmetri sammensætninger af de 2 B'er i A.
Så derfor kunne det jo være super smart, hvis jeg udfra 1 hashcode også kunne se om de 3 andre symmetriske instanser var i min Dictionary. Så skulle jeg jo ikke gemme og evaluere 4 dobbelt
Jeg har udtænkt en mulig bit repræsentation hvor hver integer i B listerne optager 5 bits i min endelige hashkey for klassen A. Det er ud fra en erkendelse af, at mac værdien 25 kan repræsenteres ved 5 bits.
Så det jeg gerne ville gøre er følgende:
GetHashKey() decimal key; foreach(int i in B-list) { key = key & i; key = key << 5; }
Mit første problem er, at C# ikke vil lade mig bruge bit operationer på decimal typen, der ellers lige med nød passer med 128 bit / 5 bit/element = 25. Hvad dulen gør man så. 64 bit er jo for lidt. Kan man få nogle flere bits at gemme i.
Derudover mangler jeg noget kløgtig logik til at komme fra en hashkey rep til de 3 andre.
Hvis jeg kan genere en hashcode for start situationen og derudover også genere de 3 andre symmetrisk hashkeys, så kan jeg vel adde alle 4 til min dictionary, såfremt den første ikke fandtes i dictionary'en.
På den måde vil min dictionary naturligvis blive 4 gange så stor, men jeg kan vel stadig slå op og udnytte at min key var unik?
Jeg har fået klyttet en GetHashKey funktion sammen, der returnere en string. Denne string har jeg været nødt til at sammensætte ud fra andre strings af formatet "04" og jeg har derfor mange flere bits i key stringen end jeg havde tænkt mig.
Jeg havde kun planer om at bruge 5 bits til repræsentationen af et element, men er endt op med 2 chars til hver, altså 32 bits. Jeg kan ikke lure, hvordan man kan tage 5 bits ud af gangen fra en string og hvordan man kan indsætte de 5 bits.
Dictionary tilbyder et interface hvor du kan slå en value op via en key
Dictionary implementerer det via en hash table som bruger hash code
men du kan ikke bruge den implementation til noget
du kan få det til ikke at virke ved at bryde Equals/GetHashCode kontrakten og du kan ødelægge performance ced en meget dårlig hahs funktion, men det er det
du bliver nødt til at træde et skridt tilbage og angribe det egentlige problem anderledes
Så hvis jeg opretter min Dictionary med <string, double>, så kalder Dictionary'en selv default GetHashCode på min key-string og laver den om til en int værdi og så er jeg lige vidt. For så vil jeg jo aldrig kunne have mere end int32's precisions forskellige værdier som keys. Er det korrekt forstået.
Hvis ja, så er det jo ren øv for min "smarte idé"... Så er der jo nok ikke meget jeg gøre....
Jeg fandt desværre ikke hvad jeg søgte efter... Lukker
Synes godt om
Ny brugerNybegynder
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.
