29 november 2012 Hashing. Een tijd-ruimte afweging Hashfuncties

29 november 2012

Hashing Inleiding Closed Hashing

Hashing Ferd van Odenhoven Fontys Hogeschool voor Techniek en Logistiek Venlo Software Engineering

29 november 2012

ODE/FHTBM

Hashing

Inleiding Closed Hashing

29 november 2012

1/30

Een tijd-ruimte afweging Hashfuncties

Hashing Een typisch gebruik van de implementatie van hashing zijn dictionairs. Elke dictionair bestaat uit een lijst van sleutel die aan een of meerdere (!) objecten gerelateerd zijn. Hashing is een uitbreiding van zoeken op index-sleutel en gaat verder dan de standaard zoektoepassingen. Het resultaat is wezenlijk verschillend voor de manier waarop gezocht wordt [en kan daarom onafhankelijk daarvan bekeken worden].

ODE/FHTBM

Hashing


29 november 2012

2/30


Hashing 2 Hashing is: direct naar elementen verwijzen via rekenkundige operaties. Se zullen diverse technieken beschouwen: Separate Chaining Linear Probing Double Hashing

Deze rekenkundige bewerkingen worden door zogenaamde hashfuncties ge¨ımplementeerd.

ODE/FHTBM

Hashing

29 november 2012

3/30

1

29 november 2012



Basis idee Zoekalgoritmen, die hashing gebruiken bestaan uit twee gescheiden delen. 1

2

Berekenen van een hashfunctie die de zoeksleutel omzet in een tabeladres, en een Methode om botsingen te verwerken voor deze sleutel.

De hashfunctie beeldt de sleutel af op een positie in een hashtabel. In het ideale geval: a Direct Access Table: (An array!?) 1

2 3

Als item i een sleutel k heeft en h(x) een hashfunctie is, wordt i op positie h(k) van de tabel afgebeeld. Hier geen collisions. Om te zoeken naar i berekenen we h(k) waarmee de positie gevonden kan worden. Als er geen element bestaat, zit die ook niet in de dictionary.

ODE/FHTBM

Hashing


29 november 2012

4/30


Voorbeeld: dictionair met studentgegevens De sleutels zijn de studentnummers (ID’s) (951000-952000) – niet meer dan 1001 studenten Hashfunctie: h(k) = k − 951000 beeldt de ID’s van de studenten af op een bepaalde tabelpositie in het bereik 0-1000. array table[1000]

[0]

[1]

[2]

[3]

[1000]

buckets

ODE/FHTBM

Hashing


29 november 2012

5/30


Voorbeeld: Dictionair met studentgegevens (2) In het gegeven voorbeeld zien we dat we O(N) tijd nodig hebben om de hashtabel te initialiseren (N is het aantal posities of buckets in de hashtabel) en O(1) tijd om toevoegen en zoeken uit te voeren. Het ideale geval is onrealistisch. Voor de implementering van een dictionair werkt het, maar een sleutelbereik kan te groot zijn voor een 1-1 afbeelding op de buckets! Voorbeeld: neem aan dat een sleutel een waarde kan hebben in 0 . . . 65535 (2-byte unsigned integer) Accepteer ongeveer 1000 records op een willekeurig moment. Een hashtabel met 65536 (>> 1000) posities is erg onhandig.

ODE/FHTBM

Hashing

29 november 2012

6/30

2

29 november 2012



Een tijd-ruimte(opslag) afweging Hashing is een goed voorbeeld van een afweging tussen looptijd en opslagruimte. Bekijken we eens de volgende extrema aan: 1

2

Als er onbeperkt geheugencapaciteit was, konden we elke willekeurige zoekopdracht met een enkele geheugenbewerking doen. De benodigde hoeveelheid geheugen kan ontoereikend zijn als de sleutels te lang zijn. Als er geen tijdslimiet was, konden we met een minimum aan geheugenruimte werken, door een sequentiële zoekmethode te gebruiken.

ODE/FHTBM

Hashing


29 november 2012

7/30


Een tijd-ruimte(opslag) afweging (2) Hashing maakt een balancering tussen geheugen en tijd mogelijk doordat van beide een bepaalde hoeveelheid nodig is. We kunnen een evenwicht bereiken doordat we de tabelgrootte aanpassen zonder de code te herschrijven of andere algoritmne toe te passen. We ondersteunen de belangrijke operaties search en insert. Gemiddeld verbruiken beide operaties search en insert constante tijd. In worst case is de tijd evenredig aan de verzameling operaties, die door de datastructuur (bijv. arrays) wordt vastgelegd. Hashing biedt geen efficiente implementaties voor andere symbooltabel-operaties zoals select of sort

ODE/FHTBM

Hashing


29 november 2012

8/30


Hashfuncties Keren we naar ons voorbeeld terug. Als het sleutelbereik te groot is, moeten we een hashtabel nemen met minder posities (buckets) en een hashfunctie die meerdere sleutels op dezelfde positie afbeeldt. h(k1 ) = β = h(k2 ) : voor k1 en k2 is er een collision bij positie β. Populaire hash-functies gebruiken: hashing by division (hashing door deling) h(k) = k%M; waarin M het aantal posities in de Hash-Tabelle is.

ODE/FHTBM

Hashing

29 november 2012

9/30

3

29 november 2012



Voorbeeld Voorbeeld: hashtabel met 11 posities h(k) = k%11 80 40 65 58

→ → → →

3 (80% 11 = 3) 7 10 3 collision!

ODE/FHTBM

Hashing


29 november 2012

10/30


String sleutels Tot nu toe hebben we met numerieke sleutels gewerkt. Java implementaties worden gerealiseerd via hashfuncties voor string sleutels. De sleutel wordt berekend via vermenigvuldigingen en optellingen per karakter in de sleutel. Methode von Horner mit umgesetzt in Array-Index: int hash ( String s , int M ) { int h = 0 , R = 127; for ( int i = 0; i < s . length (); i ++) h = ( R * h + s . charAt ( i )) % M ; return h ; } ODE/FHTBM

Hashing


29 november 2012

11/30


Voorbeeld We kunnen de hashfunctie berekenen voor: averylongkey Een 7-bit ASCII-code levert voor deze tekst: 97·12811 +118·12810 +101·1289 +114·1288 +121·1287 +108·1286 + 111·1285 +110·1284 +103·1283 +107·1282 +101·1281 +121·1280 . Een 84-bit getal! Het programma gebruikt 127 inplaats van 128 voor betere randomverdeelde sleutelwaarden. Als bijvoorbeeld M = 64, zou meermaals 128 erbij optellen leiden tot veel identieke sleutelwaarden. Als men pseudo-random coëfficiënten gebruikt heet de methode Universal Hashing. Zie hashU methode on next slide.

ODE/FHTBM

Hashing

29 november 2012

12/30

4

29 november 2012



Universal hash function (for string keys) static int hashU ( String s , int M ) { int h = 0 , r1 = 31415 , r2 = 27183; for ( int i =0; i < s . length (); i ++) { h = ( r1 * h + s . charAt ( i )) % M ; r1 = r1 * r2 % (M -1); } return h ; } Deze aanpak zorget er voor dat de kans op een collison tussen twee 1 is. identieke sleutels gelijk aan M

ODE/FHTBM

Hashing


29 november 2012

13/30


Universal hash function (for string keys) (2) In de hashU methode is een effectievere benadering geimplementeerd, gebruik (pseudo) random waarden voor de coefficienten in de berekening, en een andere random waarde voor elke positie in de sleutel. Deze procedure geeft een random-algoritme dat universal hashing wordt genoemd.

ODE/FHTBM

Hashing


29 november 2012

14/30


Implementatie voor zelfgedifieerd type public class Transaction { private final String who ; private final Date when ; private final double amount ; public int hashCode () { int hash = 17; hash = 31+ hash + who . hashCode (); hash = 31* hash + when . hashCode (); hash = 31* hash + (( Double ) amount ). hashCode (); return hash ; } } ODE/FHTBM

Hashing

29 november 2012

15/30

5

29 november 2012


Policies voor collision-afhandeling Linear Probing Verbeterde collision-afhandeling

Drie primaire voorwaarden voor een goede hash Ze moet consistent zijn: gelijke sluetels moeten dezelfde hashwaarde krijgen. Het moet efficient te berekenen zijn. De sleutels moeten uniform verdeeld zijn. “Een slechte hash-functie is een klassiek voorbeeld van een performance bug.”

ODE/FHTBM

Hashing


29 november 2012

16/30


Policies voor collision-afhandeling De collison-afhandeling beinvloedt de keuze voor de hashfunctie. We onderscheiden twee verschillende hashing-typen 1 2

Open hashing, (separate chaining) Gesloten hashing (closed hashing)

De verschillen zijn collisions opgeslagen worden buiten de tabel (open hashing) of dat collisions ervoor zorgen dat een deel van de data op een andere positie in de tabel opgeslagen wordt (gesloten hashing).

ODE/FHTBM

Hashing


29 november 2012

17/30


Rehash-strategie: Linear-probing Finde ein leeres bucket Aanname J: De hashfuncties die we gebruiken verdelen de sleutels uniform en onafhankelijk. Bij closed-hashing hoort een rehash-strategie: als we proberen x in positie h(x) onder te brengen die reeds bezet is, zoeken we alternatieve plaatsen h1(x), h2(x), enz. Als er geen lege plaats gevonden wordt is de tabel vol. h(x) heet home bucket. De eenvoudigste Rehash-strategie heet Linear Hashing of Linear Probing (lineair proberen) hi (x) = (h(x) + i)%M Onze collison oplossings-strategie is zodanig dat we een reeks van posities (probe sequence) in de hashtabel genereren die de data kan opnemen. Dan testen we elke bucket totdat we een lege vinden (probing). ODE/FHTBM

Hashing

29 november 2012

18/30

6

29 november 2012



Voorbeeld: Closed Hashing M = 8, de sleutels a, b, c, d hebben de hashwaarden: h(a) = 3, h(b) = 0, h(c) = 4 en werden al toegevoegd. Waar voegen we d met h(d) = 3 in? Bucket 3 is al gevuld. Die Probeer-reeks bij lineair hashing is h1 (d) h2 (d) h3 (d) etc. 7, 0, 1, 2

= = =

(h(d) + 1)%8 (h(d) + 2)%8 (h(d) + 3)%8

= = =

4%8 5%8 6%8

= = =

4 5 6

Loopt over naar begin van de tabel!

ODE/FHTBM

Hashing


29 november 2012

19/30


Resultaat van linair probing in voorbeeld lineair hashing [0] [1] [2] [3] [4] [5] [6] [7]

ODE/FHTBM

b

a c d

Hashing


29 november 2012

20/30


Nog een voorbeeld: Linear probing Wat gebeurt als het volgende item home-bucket 0 heeft? Er zijn enkele elementen met home-bucket 1 of 2. Het record komt op positie 3. Netzo worden records op 7 of 8 of 9 hashen uiteindelijk in 10 terecht komen. Records met hashing op 4 worden in 4 geplaatst; datzelfde geldt voor 5 en 6. 1052 bij home-bucket 7 invoegen (1052%11 = 7) Het volgende element wordt op positie 3 geplaatst.

ODE/FHTBM

Hashing

29 november 2012

21/30

7

29 november 2012

Hashing Policies voor collision-afhandeling Linear Probing Verbeterde collision-afhandeling


Nog een voorbeeld: Linear probing (2) [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10]

[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10]

1001 9537 3016

9874 2009 9875

ODE/FHTBM

Hashing

1001 9537 3016

9874 2009 9875 1052

29 november 2012

22/30



Linear Probing Voorbeeld items : A S E R C H I N G X M P hashcode : 7 3 9 9 8 4 11 7 10 12 0 8

G G G G

X X X

M M

S S S S S S S S S S S

0

1

2

3

H H H H H H H

P

4

5

ODE/FHTBM

6

A A A A A A A A A A A A

C C C C C C C C

E E E E E E E E E E

7

8

9 10 11 12

Hashing


R R R R R R R R R

I I I I I I

N N N N N

29 november 2012

23/30


Implementatie voor Lineair Probing Algorithm 3.6 public class LinearProbingHashST < Key , Value > { private private private private

int N ; int M = 16; Key [] keys ; Value [] vals ;

// // // //

number of key - value pairs in the symbol table size of linear probing table the keys the values

public L i n e a r P r o b i n g H a s h S T () { keys = ( Key []) new Object [ M ]; vals = ( Value []) new Object [ M ]; } private int hash ( Key key ) { return ( key . hashCode () & 0 x7fffffff ) % M ; } public void put ( Key key , Value val ) { if ( val == null ) delete ( key ); if ( N >= M /2) resize (2* M ); int i ; for ( i = hash ( key ); keys [ i ] != null ; i = ( i + 1) % M ) { if ( keys [ i ]. equals ( key )) { vals [ i ] = val ; return ; } } keys [ i ] = key ; vals [ i ] = val ; N ++; } public Value get ( Key key ) { for ( int i = hash ( key ); keys [ i ] != null ; i = ( i + 1) % M ) if ( keys [ i ]. equals ( key )) return vals [ i ]; return null ; }

ODE/FHTBM

Hashing

29 november 2012

24/30

8

29 november 2012



Operaties en lineaire probing: verwijderen Bekijk zoeken van een item: test h(k), h1 (k), h2 (k), . . . , totdat k of een lege positie of een home bucket vinden Als niets kan worden verwijderd functioneert de strategie! Wat gebeurt er als er moet worden verwijderd? Als we een lege bucket bereiken, kunnen we er niet zeker van zijn dat k niet ergens anders is en de lege bucket bezet was toen k ingevoegd werd. We hebben een speciale plaatshouder gewist nodig, om een bucket dat nooit werd gebruikt te kunnen onderscheiden van een die ooit een waarde bevatte. We moeten de hashtabel waarschijnlijk reorganiseren nadat er veel verwijderingen hebben plaatsgevonden.

ODE/FHTBM

Hashing


29 november 2012

25/30


Verwijderen bij linear probing (LinearProbingHashST.java) public void delete ( Key key ) { if (! contains ( key )) return ; int i = hash ( key ); while (! key . equals ( keys [ i ])) { i = ( i + 1) % M ; } keys [ i ] = null ; vals [ i ] = null ; i = ( i + 1) % M ; while ( keys [ i ] != null ) { Key keyToRehash = keys [ i ]; Value valToRehash = vals [ i ]; keys [ i ] = null ; vals [ i ] = null ; N - -; put ( keyToRehash , valToRehash ); i = ( i + 1) % M ; } N - -; if ( N > 0 && N <= M /8) resize ( M /2); } ODE/FHTBM

Hashing


29 november 2012

26/30


Analyse voor linear probing Inititalisatie: O(M), waar M het aantal buckets is Invoegen en zoeken: O(N), waarbij N het aantal elementen (of items) in de tabel is; alle N sleutelwaarden hebben dezelfde home bucket Voor het onderhoud van een woordenboek is er niets beter dan een lineaire lijst!

ODE/FHTBM

Hashing

29 november 2012

27/30

9

29 november 2012



Prestatieanalyse voor het gemiddelde geval De gemiddelde kosten van linear probing hangt af van de wijze waarop items clusteren in samenhangende groepen van bezette tablecellen bij het invoegen. We verwachten dat de kosten voor hashing een functie is van de mate waarin de tabel gevuld is: DEF: lastfactor α = N/M GHemiddelde kosten met aanname J van linear-probing: Definition (Propostion M.) 1 2

Aantal probes voor geslaagde zoekactie: Aantal probes voor gefaalde zoekactie:

1 2

∗ (1 +

∗ (1 +

1 1−α )

1 (1−α)2 )

Ondezoek de grenswaarden α = 0 en α = 1. ODE/FHTBM

Hashing


29 november 2012

28/30


Meerdere probing benaderingen Lineare Probing hi (x) = (h(x) + i)%M Alle buckets in de tabel zijn kandidaten voor invoegen van een nieuw record voordat de probe sequence naar de home positie terugkeert. Clustering van records leidt tot lange probeerreeksen

Lineaire probing met overslaan hi (x) = (h(x) + i ∗ c)%M c is een constante (6= 1) Records met dezelfde home-bucket volgen niet dezelfde probeerreeks

(Pseudo-)random probing hi (x) = (h(x) + ri )%M ri is de i-de waarde in een toevals-permutatie van getallen 1 tot M − 1; zie Universal Hashing. Invoegen en zoeken gebruiken dezelfde reeks van ”random”getallen.

ODE/FHTBM

Hashing


29 november 2012

29/30


Een ander soort verbetering: double hashing We gebruiken twee hashing-methoden: dubbele hashing (double hashing). Om clustering te vermijden: groepsvorming van gevulde cellen. void insert ( Item x ) { Key key = x . getKey (); int i = hash ( key , M ); int k = hashtwo ( key ); while ( storage [ i ] != null ) { i = (i+k) % M; } storage [ i ] = x ; N ++; // item stored } Item search ( Key key ) { int i = hash ( key , M ); int k = hashtwo ( key ); while ( storage [ i ] != null ) if ( equals ( key , storage [ i ]. getKey ())) { return storage [ i ]; // item found } else { i = (i+k) % M; } return null ; } ODE/FHTBM

Hashing

29 november 2012

30/30

10

29 november 2012 Hashing. Een tijd-ruimte afweging Hashfuncties

Recommend Documents