W dniu 2013-03-28 19:20, M.M. pisze:
> W dniu czwartek, 28 marca 2013 17:15:55 UTC+1 użytkownik bartekltg napisał:
>
>> Ojtam, realokujesz do większej. Vector robi to samo. Tutaj
>> pewnie tylko raz jeszcze musisz policzy.
> Nie wiem jaki jest najsprytniejszy algorytm realokacji hash-table.
> Naiwny wygląda mniej/więcej tak:
> 1) Przydziel większą tablicę
> 2) Dla każdego elementu z tablicy mniejszej:
> a) policz funkcję hash
> b) wrzuć do większej
> 3) Zwolnij pamięć list
> 4) Zwolni mniejszą tablicę
>
> W tym zadaniu faktycznie można dać tablicę 1.5 * ilosc_znaków i się
> nie martwić. Ale w ogólnym przypadku (chyba) trochę czasu schodzi
> na realokację.


Tak jak w każdym tego typu kontenerze. Poszacuj sobie czas
zamortyzowany. Dla czysto rosnącej tablicy i powiększania x2
wychodzi 3 razy więcej niż wklejenie elementu (dodając element
przydzielasz mu dodatkowe dwa kredyty na jego realokowanie w przyszlosci
i realokowanie elementu z pierwszej połowy tablicy).

Mała cena jak za możliwość nieprzejmowania się rozmiarem;)

pzdr
bartekltg