[so] [SO] [Tema1] General questions

Laura Vasilescu vasilescu.laura at gmail.com
Wed Feb 23 15:42:37 EET 2011


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.

-- 
Laura
http://swarm.cs.pub.ro/~laura/


More information about the so mailing list