On 16.09.2015 12:31, M.M. wrote:
> On Wednesday, September 16, 2015 at 11:34:13 AM UTC+2, bartekltg wrote:
>> Dlatego proponowałem (unordered_)set zamiast (...)map.
>> Jest/nie ma w pomocniczym zbiorze.
> To jest najszybsza metoda w praktyce. Czasami możemy trafić na
> dane, dla których funkcja hash da mnóstwo kolizji. Problem
> kolizji trochę rekompensuje odpowiednia implementacja hash-table,
> ponieważ można ją przeglądać tak jak lubi pamięć cache. W
> przypadku RBTree nigdy nie jest przyjaźnie dla cache, ale
> jest gwarancja N*Log(N) dla każdych danych.
>
> Pozdrawiam
>
> P.S.
> Chyba w popularnych bibliotekach nie ma implementacji hash-table
> która jest przyjazna dla pamięci cache, chyba trzeba samemu
> wyrzeźbić. Szczególnie warto samemu, gdy wiemy z góry ile
> będzie danych liczb.

w STD jest metoda łańcuchowa. Kiedyś nawet czyałem, że
za tym, że nie sosją jakiergoś adresowania otwartego
stoi za jakaś idealogia.

Parę razy natknąłem się na googlowe tablice mieszające
https://github.com/sparsehash/sparsehash
Kilka gatnków, do wyboru.

Stare, ale ciekawe porównanie:
http://incise.org/hash-table-benchmarks.html


Za to jakiś czas temu złapałem się na tym, że std:hash na intach
... zwraca argument. Jest różnowartośćiowa, ale dość słabo miesza:(



pzdr
bartekltg