[so] [SO] [Tema1] General questions

[Victor Carbune]

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ă.

Victor