Egyszer egy Herb Sutter előadást néztem, amikor előadta a Stroustruptól csent random számok beszúrása "rendezett" std::vectorba és std::listbe benchmark példát. És Sutter felteszi a kérdést a közönségnek, hogy nyilván kis elemszám esetén a vektor gyorsabb, na de vajon hány elemnél előzi meg (sebességben) az std::list az std::vector-t? 10? 100? 500?
Ekkor elgondolkodtam, hogy vajon egyszerűen ennyire hülyének nézi a közönségét, vagy ő maga sem sokkal okosabb ennél a szintnél... Nekem teljesen nyilvánvaló volt, hogy az std::list mindig lassabb lesz, std::set-tel kellene próbálkoznia, hogy nagy elemszámra valami gyorsabbat kapjon, mint a vector. Szóval mi volt a válasz, amit Herb Sutter felfedett: Stroustrup megcsinálta a benchmarkot félmillió elemig, és még félmilliónál is gyorsabb volt az std::vector... (What a surprise!)
Visszatérve a hasító táblákra:
Tudhatnád, hogy egy hash table container megírása nem egy bonyolult művelet, és hogy a hash table teljesítménye elsősorban nem is a konténer milyenségétől függ (hogy pl. prím vagy kettőhatvány-e a táblaméret), hanem elsősorban a hasítófüggvénytől, annak jóságától és sebességétől.
Namost, ha user-defined type a kulcs a konténerben, akkor ugyanúgy neked kell a hasítófüggvényt megírni akkor is, ha standard C++ konténert használsz, ha pedig built-in type (integer, string, floating-point), akkor pedig bármikor találsz az interneten azonnal bekopizható hash függvényt, ami ugyanolyan jó (sőt, lehet hogy ugyanaz), mint a C++ standard implementáció.