Algoritmen I (2009-2010)

reeks 14: hashing

Ontwerp en implementeer een woordenboek als een hashtabel met coalesced chaining (zie theorie), met een cellar (berging) en lazy deletion. Implementeer zowel zoeken, toevoegen als verwijderen.

Maak de gegevensstructuur geparametriseerd, zodat je sleutels van een willekeurig type S kunt afbeelden op waarden van een willekeurig type T. De hashfunctie (die S op unsigned int afbeeldt), wordt als parameter meegegeven.

Test uit met string-sleutels. Zoek een geschikte hashfunctie voor algemeen gebruik.

Hoe kun je controleren of je oplossing performant is? Kun je het aantal conflicten tellen? Meet opzoektijden voor verschillende bezettingsgraden en vergelijk met andere woordenboekstructuren (bv. std::map)