Eenvoudig hash algoritme gezocht.

[-DarkShadow-]

Ik heb een matrix met daarin bijvoorbeeld:

code:

11111
10000
11100
10000
11111

Als je goed kijkt zie je dat dit een 'E' voorstelt. Nu wil ik deze 'E' matchen met een 'E' die al bekend is. Nu lijkt het mij het gemakkelijkst om dit te doen dmv een hashtable. Het gaat hier namelijk om een relatief klein aantal kleine matrices en snelheid heeft de hoogste prioriteit.

Nu ben ik op zoek naar een algoritme om dit te hashen. MD5, SHA e.d. zijn allemaal veels te groot en ingewikkeld.

Ik zat te denken aan het volgende:

C:

for(i = 0; i < width; i++){
   for(j = 0; j < height; j++){
      a += i * j * matrix[i][j];
   }
}
return 300^a;

Ik ben bang dat dit 'algoritme' geen mooie verdeling over de hashtable geeft. Ik zoek eigenlijk een dergelijk algoritme dat wel goed werkt.

[beriz]

Kan je gewoon niet de sommen van kolommen en rijen nemen?
als snelheid dan toch een rol speelt?...

[.oisyn]

Staan er echt alleen maar 0en en 1en in de matrix? Dan zou ik die eerst omzetten naar binaire data, om dat vervolgens terug te brengen naar een 32 of 64 bits hash.

MD5 en SHA zijn natuurlijk een beetje onnodig, die zijn voornamelijk bedoeld als veilige hash algoritmes die je niet makkelijk om kunt draaien. Voor jouw doeleinde boeit het natuurlijk niet als je makkelijk een input bij een hash kunt verzinnen, zolang je maar gewoon een goede (uniforme) verdeling hebt. En dan voldoet het simpelweg om de binaire string op te hakken in blokjes van 32/64 bits en die met elkaar te xorren.

Voor je hashtable zelf loont het natuurlijk om een (pseudo) priemgetal als lengte van je array te nemen, zodat de hashes ook beter in je table gedistribueerd zijn.

[ Voor 13% gewijzigd door .oisyn op 27-02-2006 12:50 ]

[Janoz]

Omzetten nar een hash? Dat ding bestaat maar uit 30 bits. Zet de laatste 2 op nul en je hebt al een leuke int om mee te vergelijken. Veel sneller zul je het niet krijgen.

[-DarkShadow-]

Janoz schreef op maandag 27 februari 2006 @ 12:49:
Omzetten nar een hash? Dat ding bestaat maar uit 30 bits. Zet de laatste 2 op nul en je hebt al een leuke int om mee te vergelijken. Veel sneller zul je het niet krijgen.

Breedte en hoogte zijn variabel en kunnen 2 tot 3 keer zo hoog zijn.

.oisyn schreef op maandag 27 februari 2006 @ 12:45:
Staan er echt alleen maar 0en en 1en in de matrix? Dan zou ik die eerst omzetten naar binaire data, om dat vervolgens terug te brengen naar een 32 of 64 bits hash.

Dat is een goed idee, het uiteindelijke vergelijken gaat dan ook sneller.

Voor je hashtable zelf loont het natuurlijk om een (pseudo) priemgetal als lengte van je array te nemen, zodat de hashes ook beter in je table gedistribueerd zijn.

Dat wist ik nog niet. Waar slaat dat (pseudo) eigenlijk op?

[.oisyn]

-DarkShadow- schreef op maandag 27 februari 2006 @ 13:03:
Dat wist ik nog niet. Waar slaat dat (pseudo) eigenlijk op?

De officiele definitie is wat generieker, maar 2ⁿ-1 valt er ook onder en dat is natuurlijk een stuk makkelijker te bepalen dan een priemgetal

[Soultaker]

Een hele simpele goede hash-functie is FNV-1a.

Een iets sterkere hash kun je zelf maken met wat tables. Stel bijvoorbeeld dat je een matrix hebt van maximaal 30 hoog en 20 breed, dan maak je een tabel die per rij aan elke mogelijke combinatie van bits in die rij een random code toekent. De codes van alle rijen combineer je dan.

Het is dan natuurlijk handig als je de rijen al binair hebt gecodeerd in een int. Dan wordt de code zoiets:

C:

int codes[30][1<<20]; // initialiseren met random hash codes

int hash(int *matrix, int height)
{
    int hc = 0, r;
    for(r = 0; r < height; ++r)
        hc ^= codes[r][matrix[r]];
    return hc;
}

Deze functie levert mooi uniforme hash codes op, die bovendien goed bestand zijn tegen simpele verwisseling van bits, rijen of kolommen. Verder kun je 'm nog steeds vrij snel berekenen omdat er geen vermenigvuldigingen in voorkomen, maar daar staat tegenover dat 'ie wel erg geheugenintensief is (in tegenstelling tot de FNV hash functies).

Of het de kwaliteit van de hash codes in de praktijk beter is dan FNV-1a is maar de vraag.

[Daos]

MD5 en SHA zijn gemaakt voor beveiliging (om te laten zie dat de data niet veranderd is) en niet voor het opzoeken van data.

Vaak doe ik som van alle getallen mod een constante. FNV werkt ook wel goed en gebruik ik ook soms. MD5 kan ook snel zijn (afhankelijk van de implementatie die je ergens gestolen hebt).


Met google kan je heel goed meer over hashes vinden: voorbeeldje.


Nog tipje/opmerking:
Bij elke hashfunctie kan je een botsing krijgen. Twee objecten met dezelfde hash betekent niet dat de objecten hetzelfde zijn. Het is alleen erg waarschijnlijk dat ze hetzelfde zijn.

[.oisyn]

Soultaker schreef op maandag 27 februari 2006 @ 15:00:
Een hele simpele goede hash-functie is FNV-1a.

Een iets sterkere hash kun je zelf maken met wat tables. Stel bijvoorbeeld dat je een matrix hebt van maximaal 30 hoog en 20 breed, dan maak je een tabel die per rij aan elke mogelijke combinatie van bits in die rij een random code toekent. De codes van alle rijen combineer je dan.

Het is dan natuurlijk handig als je de rijen al binair hebt gecodeerd in een int. Dan wordt de code zoiets:

C:

int codes[30][1<<20]; // initialiseren met random hash codes

Oeh, lekker cache vriendelijk. Dan is het vermenigvuldigen van de elementen in de matrix toch echt een stuk sneller

[Blackbird-ce]

beriz schreef op maandag 27 februari 2006 @ 12:44:
Kan je gewoon niet de sommen van kolommen en rijen nemen?
als snelheid dan toch een rol speelt?...

Nee, want:

code:

1 0 0
0 1 0
0 0 1

geeft dan voor elke rij en kolom 1.

code:

0 0 1
0 1 0
1 0 0

geeft dan voor elke rij en kolom ook 1.


Maar wat iemand hierboven ook al zei (afhankelijk van wat je nu precies wilt gaan doen met je vergelijkingen): waarom uberhaupt hashen en niet gewoon als 1 lange string pakken?

[Soultaker]

.oisyn schreef op maandag 27 februari 2006 @ 15:09:
[...]

Oeh, lekker cache vriendelijk. Dan is het vermenigvuldigen van de elementen in de matrix toch echt een stuk sneller

edit:
In een daadwerkelijk programma kan dat anders zijn (inderdaad vanwege het cache effect) maar als ik de functies in een lus tegen elkaar benchmark is de tabelvariant toch echt sneller, ondanks dat die tabel zelf echt niet in mijn 512KB L2 cache past.

Het is dus geen uitgemaakte zaak. Als er inderdaad nog veel cache afhankelijke code om de hash functie call heen zit is de kans groot dat FNV-1a toch qua performance toch een beter keuze is, maar dan is de snelheid van de hash functie waarschijnlijk toch al minder van belang omdat de hash code gedomineerd wordt door de andere code.

Ik had dit getest met een constante invoer in de lus en dat klopt natuurlijk niet. Met random invoer is FNV-1a inderdaad een stuk sneller. Waarschijnlijk is die dus gewoon beter, tenzij je verwacht dat de invoer een heel beperkt aantal verschillende matrices is.

[ Voor 34% gewijzigd door Soultaker op 27-02-2006 15:46 ]