[so] Tema0

[Daniel Baluta]

2014-02-21 20:43 GMT+02:00 Alexandra Sandulescu
<alecsandra.sandulescu at gmail.com>:
> 1. Ce sunt exact bucketurile ?

Un bucket este reprezentat de lista cheilor cu aceeasi valoare a
functiei de hashing.

> 2. daca acestia sunt linii dintr-o matrice, cum stiu cand adaug in ce bucket
> ? (e precizat ca bucketurile au lungime oricat)

Aplici functia de hashing si obtii slot-ul (bucket-ul) unde trebuie sa
inserezi cuvantul.
E bine sa tii o lista si nu un vector ca sa nu trebuiasca sa realoci
de fiecare data cand
atingi limita vectorului.

> 3. ce inseamna SIZE? acest SIZE -> "Hashtable-ul implementat va conține SIZE
> bucketuri."

numarul de bucket-uri.

Mai multe info aici: http://en.wikipedia.org/wiki/Hash_table

Exemplu:

Cum arata un hash de dimensiune 3. Presupunem ca functia de hashing este

F(cuvant) = (suma caracterelor ) % 3.

Cum dimensiunea hash-ului este 3, functia de hashing va intoarce intotdeauna
0, 1, 2 (note the %3).

Initial hash-ul este gol:
0:
1:
2:

Dorim sa adaugam cuvantul AB; F(AB) = ('A' + 'B') %3 = (65+66) % 3 = 2;

Hash-ul arata acum:

0:
1:
2: AB

Daca vom introduce pe rand AC, AD, AE avem F(AC) = 0, F(AD) = 1, F(AE) = 2

Hash-ul final va arata

0:AC
1:AD
2:AB AE

Hope this helps.

thanks,
Daniel.


















http://en.wikipedia.org/wiki/Hash_table