2011/2/23 Victor Carbune <victor.carb...@gmail.com>: > Salut, > > 2011/2/23 Laura Vasilescu <vasilescu.la...@gmail.com>: >> 2011/2/23 Daniel Baluta <daniel.bal...@gmail.com>: >>> 2011/2/23 Victor Carbune <victor.carb...@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) _______________________________________________ http://elf.cs.pub.ro/so/wiki/resurse/lista-discutii
