W dniu 2013-03-28 19:57, bartekltg pisze:
> 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;)

OK, może za mętnie powiedziałem, trochę rozjaśnię.

Niech naszym bazowym kosztem będzie policzenie hasha,
wstawienie do tablicy i 1/n czasu zalkokowania tej tablicy
(czy tam tablicy list...) dlugosci n.

Koszt zamortyzowany pojedyńczego wstawiania jest
mniejszy niż 3*koszt podstawowy (będzie gdzieś pomiedzy x2 i x3).

Z grubsza tak samo jak w wektorze.

pzdr
bartekltg