W dniu 09.10.2010 21:57, Mariusz Marszałkowski pisze:
> On 9 Paź, 21:35, Michoo<m...@v...pl> wrote:
>> A klasyczne hashtable o rozmiarze k realizowane funkcją modulo k wymaga
>> obsługi powtarzających się haszy. i te powtarzające się hasze będzie się
>> obługiwać albo w ulog u przy uży7ciu stosu/drzewa (gdzie u to ilość
>> haszy kolidujących) albo w u^2 przy naiwnej implementacji z listą.
>
> No dobra, ale po co brać pod uwagę pesymistyczny przypadek który
> zdarza się tak rzadko, że ciężko policzyć?
Ale to zadanie z książki o teorii algorytmów. Nie podręcznika sprytnego
programisty.

> To się w praktyce dla
> dużych danych nie zdarzy, a dla małych najszybciej zadziała algorytm o
> małym narzucie liniowym.
Dla dużych danych nie możemy mieć za dużego hashtable, bo wylecimy z
cache i wszystko znacznie zwolni. tak więc dla n danych i k kubełków (w
przypadku optymistycznym):
- n/k danych w kubełku
- n/k * ln(n/k) lub n/k * (n/k)^2 czas wstawiania do jednego kubełka
- mamy k kubełków, więc k*(n/k * ln(n/k)) = n * ln(n/k) lub k*(n/k *
(n/k)^2) = n*(n/k)^2 na wstawienie do wszystkich
- tak czy tak wychodzi trochę gorzej niż liniowo, ten sam rząd co dla
sortowania (może mniejsza stała np o 1/2 będzie), ale rząd złożoności
ten sam.

P.S.
Ja bym w c++ użył mapy - bo się najszybciej pisze.
std::map<int,int> count;
count.insert(data.begin(),data.end());
for(auto i=count.begin();i!=count.end();++i)
if(i->second != 1)
std::cout <<i->first<<std::endl;

--
Pozdrawiam
Michoo