wat is hash-tabel

[Gast]

wie kan mij uitleggen wat een hash-tabel is ????

[EL PIÑO]

hash

 

Volgens mij bedoel jij hasj..

[Sammex]

Q muis.

Een hash-tabel is een arry waarin data wordt opgeslagen op een door een (hash function) aan de hand van de data berekende index.

info from Faculteit Wiskunde & Informatica.

vgr,

Sammex : <img src="/ubbthreads/images/graemlins/biggthumpup.gif" alt="" />

[trust]

 

Ik had niet gedacht , dat het zo simpel was

[Bigfoot]

Hoe die hash-tabel nou precies werkt in het hele seca-2 verhaal is mij ook nog steeds onduidelijk.

 

Kan een wiskundige misschien wat nader toelichten wat een hash-functie is (of hebben we die hier niet)?

[Psychosammie]

Een poging dan. Ben overigens geen wiskundige.

 

Het heeft te maken met het opslaan van gegevens in tabellen. Dat doe je niet zomaar, je wil ook in die tabellen kijken of een bepaald gegeven al in die tabel voorkomt of niet. Je zou dus de tabel van boven naar beneden kunnen doorlopen. Da's dus langzaam. Een andere manier is je gegevens door een hash functie te halen waarna er een sleutel uit komt. Het gegeven wordt nu opgeslagen op dat adres in de tabel. Opzoeken gaat nu eenvoudiger. Bereken de hash waarde en kijk op het gevonden adres of je gegevens daar staan of niet.

 

Dit alles vanuit een informatica perspectief.

 

Ik hoop dat het iets duidelijker is?

[Anmax]

Heel duidelijk, bedankt voor de uitleg.

[Satfreaked]

maar ik vond sjaaks zijn uitleg leuker...

<img src="/ubbthreads/images/graemlins/loldev.gif" alt="" /> <img src="/ubbthreads/images/graemlins/loldev.gif" alt="" /> <img src="/ubbthreads/images/graemlins/biggthumpup.gif" alt="" />

[Gast]

Simpel voorbeeld hashtable.

 

Ik wil wat postcodes opslaan, en wie daar woont.

 

5015AZ - Kees

3078BX - Piet

4652RV - Jan

4789KZ - Sjaak

7842PX - Truus

 

Ik wil snel kunnen opzoeken wie op welke code woont.

Ik maak een array waar ik ze in stop. Da's lastig, moet ik helemaal doorheen zoeken. Dus ik bedenk een simpele "hash functie": Ik neem het 1e cijfer van de postcode, en dat is waar ik 'm opsla. De hashtabel maak ik dus 10 elementen (want zoveel mogelijkheden heb ik) en ziet er zo uit:

 

0:

1:

2:

3: 3078BX - Piet

4: 4652RV - Jan 4789KZ - Sjaak

5: 5015AZ - Kees

6:

7: 7842PX - Truus

8:

9:

 

In dit tabelletje kan ik best snel zoeken. Als ik wil weten wie op 7842PX woont, is de hash code '7', en op 7 staat alleen Truus.

 

Jan en Sjaak hebben dezelfde hash code '4', dit noemen we een hash "collision" (botsing). Om een code die met een 4 begint op te zoeken hebben we dus meer tijd nodig... Of een betere hash functie. De eerste twee cijfers (tabel wordt 100 groot) zou al werken. We zouden ook alle cijfers kunnen optellen. En van de letters kunnen we ook wel iets maken, bijvoorbeeld de ASCII code, of A=1, B=2 enzovoorts.

 

Hoe goed zo'n hashtable werkt, hangt dus af van hoe groot die tabel is (groter is meestal sneller) en hoe goed de hash functie is in verhouding tot de waardes die je opslaat. Onze "eerste twee cijfers" functie zou heel slecht werken als al mijn kennissen in 't zelfde dorp wonen (kan ik beter de letters gebruiken).

 

De meest gebruikte functie voor strings (willekeurige data dus, een rijtje bytes) is deze:

Code:

const int PRIEMGETAL = 23;int hash = 0;for (i = 0, i < array.length-1, i++) {    hash = hash * PRIEMGETAL + array[i];}return hash;

 

Nu levert dit een willekeurig groot getal op (PRIEMGETAL is meestal een veel groter getal want voor een computer is 2x2 net zo moeilijk als 1204987x293), en onze tabel mag niet willekeurig groot worden. Daarom gebruiken we de 'modulo' (rest na deling) truuk. De tabel maken we een bepaalde grootte, meestal een priemgetal, bijvoorbeeld '7'. De hash code delen we eerst door de grootte van onze tabel, en de 'rest' na deze deling is de index in deze tabel. Dus als de hash code '25' is (25/7 = 3, rest = 4) moeten we deze waarde op plaats 4 in de tabel zetten (of zoeken!).

 

Hash tabellen worden veel gebruikt voor databases, en voor coderingen om bijvoorbeeld voorberekende uitkomsten in op te slaan om het rekenwerk sneller te maken.

[Bigfoot]

Bedankt Psychosammie & Milo voor de toelichting!

 

Nu zal de hash-tabel die op de seca-2 kaarten gebruikt wordt wel niet zo logisch in elkaar zitten, ik vermoed eerder dat er random data in staat om de keys zelf nog een keer te versleutelen... ?

[Gast]

Wat ik er zo over gevonden heb (en da's niet veel), lijkt het erop dat er in SECA2 3 "hash tables" gebruikt worden, waarvan er twee 'gevonden' zijn. Rara welke gebruikt wordt door de providers die weer 'zwart' werden <img src="/ubbthreads/images/graemlins/wink.gif" alt="" />

 

Ik heb geen officieel document kunnen vinden waarin SECA 2 wordt uitgelegd in wiskunde termen.

 

Zie de hash table in dit geval maar als de lijst TAN codes van Girotel (hij vraagt om code 173, en je tikt die 6 cijfers in), of dat 'rekenmachientje' van de rabobank.

[realist]

@ all,

Wie weet welke waarden er nu bij Seca 2 gehashed worden.

Zijn het de keys ? of wat anders?

@ MiLo . Allereerst <img src="/ubbthreads/images/graemlins/xyxthumbs.gif" alt="" />

 

Citaat:

const int PRIEMGETAL = 23; int hash = 0; for (i = 0, i < array.length-1, i++) { hash = hash * PRIEMGETAL + array; } return hash;

 

Stel ik wil bovenstaande hashfunctie loslaten op: 01 23 45 67 89 AB CD EF

Dat kan toch hè.?

Is het ook uit te leggen welke hashwaarde dit oplevert? Wat dat snap ik echt niet hoor.

[Psychosammie]

Zoals Milo al aangaf kies je (als programmeur) zelf je hashfunctie. Er zijn wel wat regeltjes waar je rekening mee moet houden. Zo wil je niet teveel colissions krijgen want daar moet je dan weer bijzonder maatregelen voor treffen. Je kan dus nooit zeggen "ik stop dit erin en wat is dan de haswaarde?". Je moet dus de hashfunctie kennen.

[Gast]

Milo,

 

bedankt voor jouw prachtige posting. <img src="/ubbthreads/images/graemlins/lezen.gif" alt="" /> <img src="/ubbthreads/images/graemlins/biggthumpup.gif" alt="" /> <img src="/ubbthreads/images/graemlins/xyxthumbs.gif" alt="" />

[Gast]

Citaat:

Stel ik wil bovenstaande hashfunctie loslaten op: 01 23 45 67 89 AB CD EF

Voor mijn hash functie (0xNN = hexadecimaal getal, dus 23 = 0x17):
hash = 0
hash = hash * 23 + 0x01 = 0x01
0x01 * 23 + 0x23 = 0x3A
0x3A * 23 + 0x45 = 0x57B
0x57B * 23 + 0x67 = 0x7E74
etcetera (de rest wordt als oefening voor de student gelaten)