[so] [SO] [Tema1] General questions

[Stefan Munteanu]

2011/2/23 Victor Carbune <victor.carbune at gmail.com>:
> Salut,
>
> 2011/2/23 Laura Vasilescu <vasilescu.laura at gmail.com>:
>> 2011/2/23 Daniel Baluta <daniel.baluta at gmail.com>:
>>> 2011/2/23 Victor Carbune <victor.carbune at gmail.com>:
>>>> Eu bănuiesc că trebuie să refolosim memoria alocată în hash, şi nu să
>>>> alocăm un "nou hash".
>>>
>>> Hmm, depinde de implementare aici. Dacă ai folosit liste pentru buckets
>>> atunci clar refolosești memoria.
>>
>> Problema cu varianta propusă de Ștefan în care dacă hash-ul este
>> identic, acesta trebuie scos și readăugat la sfârșitul listei e că în
>> loc să nu faci nimic, faci o operație de ștergere (care e O(1) pentru
>> varianta cu liste pentru buckets) și o adăugare (care poate fi ceva
>> mai costisitoare, întrucât trebuie să inserezi la sfârșitul listei).
>> Desigur, s-ar putea implementa o funcție diferită pentru adăugarea
>> elementelor în caz de resize (reținându-se un pointer către sfârșitul
>> listei), dar mi se pare ineficient din punct de vedere al
>> modularizării. Funcția de adăugare în caz de resize trebuie să fie
>> aceeași cu cea pentru adăugarea unui element nou în hashTable.
>
> Asta e și nelămurirea mea.
> Ambele variante sunt deterministe și pot fi testate, însă una dintre
> ele e ineficientă.

Salut,

Sorry de rapunsurile tarzii, dar momentan sunt pe alt fus orar.
Here it  goes:
Comportamentul dorit la resize este unul echivalent cu urmatorul: se
creeaza un nou hash, se itereaza prin bucketurile din vechiul hash si
se adauga in noul hash.
Modul acesta de rezolvare este unul simplist, care poate fi facut de
toata lumea fara probleme. Este interesanta si varianta lui Victor si
poate fi aplicata si fara probleme, doar ca trebuie ajustata astfel
incat sa aiba aceleasi rezultate ca cealalta.
In final, ambele solutii au aceeasi complexitate, dar una se comporta
un pic mai bine.
Nu va sugerez nicio rezolvare anume, cu cat mai multe idei cu atat mai
bine :) Singura conditie este sa treaca testele.

Stefan

PS Hashtable-ul din java se comporta la fel (ceea ce e logic, incat
acolo nu exista realloc)