Hoe gaat het met het maken van een hashmap in c vanaf nul als aanwezig is in C++ STL?
Welke parameters zouden in overweging worden genomen en hoe zou u de hashmap testen? Zoals in, wat zou de benchmarktestcases zijn die u zou rennen voordat u zou kunnen zeggen dat uw HASHMAP is voltooid?
Antwoord 1, Autoriteit 100%
Nou, als je de basisprincipes achter hen kent, zou het niet te moeilijk moeten zijn.
Maak over het algemeen een array met de naam “emmers” die de sleutel en waarde bevatten, met een optionele aanwijzer om een gekoppelde lijst te maken.
Wanneer u met een toets de Hash-tabel opent, verwerkt u de sleutel met een aangepaste hash-functie die een geheel getal zal retourneren. U neemt vervolgens de modulus van het resultaat en dat is de locatie van uw array-index of “emmer”. Dan controleer je de niet-verwijderde sleutel met de opgeslagen sleutel, en als het overeenkomt, vond je de juiste plek.
Anders heb je een ‘botsing’ gehad en moet je door de gekoppelde lijst kruipen en de sleutels vergelijken tot je overeenkomt. (Opmerking Sommige implementaties gebruiken een binaire boom in plaats van gekoppelde lijst voor botsingen).
Bekijk deze snelle hash tabel implementatie:
https://atractiveChaos.wordpress.com/2009/09/29 / khash-h /
Antwoord 2, Autoriteit 8%
De beste aanpak is afhankelijk van de verwachte sleuteldistributie en -nummer
van botsingen. Als er relatief weinig botsingen worden verwacht, het is echt
maakt niet uit welke methode wordt gebruikt. Als veel botsingen zijn
verwacht, wat te gebruiken hangt af van de kosten van rehashing of
Sondes versus het manipuleren van de uitbreidbare emmer data-structuur.
Maar hier is een broncodevoorbeeld van Een Hashmap-implementatie in C
Antwoord 3, autoriteit 5%
Het primaire doel van een hashmap is om een dataset op te slaan en er vrijwel constant tijd op te zoeken met behulp van een unieke sleutel. Er zijn twee veelvoorkomende stijlen van hashmap-implementatie:
- Afzonderlijke ketens: een met een reeks buckets (gekoppelde lijsten)
- Open adressering: een enkele array toegewezen met extra ruimte zodat indexbotsingen kunnen worden opgelost door het item in een aangrenzend slot te plaatsen.
Afzonderlijke ketens hebben de voorkeur als de hashmap een slechte hashfunctie heeft, het niet wenselijk is om vooraf opslag toe te wijzen voor mogelijk ongebruikte slots, of als items een variabele grootte hebben. Dit type hashmap kan relatief efficiënt blijven werken, zelfs wanneer de belastingsfactor groter is dan 1,0. Vanzelfsprekend is er extra geheugen nodig in elk item om gelinkte lijstaanwijzers op te slaan.
Hashmaps die open adressering gebruiken, hebben potentiële prestatievoordelen wanneer de belastingsfactor onder een bepaalde drempel wordt gehouden (in het algemeen ongeveer 0,7) en een redelijk goede hashfunctie wordt gebruikt. Dit komt omdat ze potentiële cache-missers en veel kleine geheugentoewijzingen die zijn gekoppeld aan een gekoppelde lijst voorkomen, en alle bewerkingen uitvoeren in een aaneengesloten, vooraf toegewezen array. Iteratie door alle elementen is ook goedkoper. De vangst is dat hashmaps die open adressering gebruiken, opnieuw moeten worden toegewezen aan een groter formaat en opnieuw moeten worden gehasht om een ideale belastingsfactor te behouden, anders worden ze geconfronteerd met een aanzienlijke prestatievermindering. Het is onmogelijk dat hun belastingsfactor hoger is dan 1,0.
Enkele belangrijke prestatiestatistieken om te evalueren bij het maken van een hashmap zijn:
- Maximale belastingsfactor
- Gemiddeld aantal botsingen bij invoeging
- Verdeling van botsingen: ongelijke verdeling (clustering) kan duiden op een slechte hashfunctie.
- Relatieve tijd voor verschillende bewerkingen: plaatsen, ophalen, verwijderen van bestaande en niet-bestaande items.
Hier is een flexibele hashmap-implementatie die ik heb gemaakt. Ik gebruikte open adressering en lineaire sondering voor het oplossen van botsingen.
https://github.com/DavidLeeds/hashmap
Antwoord 4, autoriteit 2%
Er zijn andere mechanismen om overflow af te handelen dan de simpele gekoppelde lijst met overflow-items die b.v. verspilt veel geheugen.
Welk mechanisme u moet gebruiken, hangt er onder andere van af of u de hash-functie kunt kiezen en mogelijk meer dan één kunt kiezen (om bijvoorbeeld dubbele hashing te implementeren om botsingen af te handelen); als u verwacht vaak items toe te voegen of als de kaart statisch is als deze eenmaal is gevuld; als u van plan bent om items te verwijderen of niet; …
De beste manier om dit te implementeren is om eerst over al deze parameters na te denken en het dan niet zelf te coderen, maar een volwassen bestaande implementatie te kiezen. Google heeft een paar goede implementaties — b.v. http://code.google.com/p/google-sparsehash/