C# BCL Hashtable implementatie

[SideShow]

Hallo

Ik probeer wat fundamentele zaken over datastructuren bij te leren.

Ik ben al enkele dagen bezig met de hashtable, lezen en proberen.
En soms voel ik me zo dom. Een voorbeeld: de hashtable implementatie werkt met primes, want die zijn (blijkbaar) performanter te combineren met een modulo bewerking... hmmm ik ben opgeleid als informaticus (as in: het informatiseren), en niet als wiskundige/computertechnicus. Maar interessant is het wel.

Goed. Mijn huidige aanpak.

Ik heb een NoobHashtable-class gemaakt, met daarin een array, een this[x] methode die intern een Add() en een Get() aanroept en dat is het zo wat voorlopig.

Ik heb gelezen dat je enkele technieken hebt om collisions op te lossen, waarvan ik enkel rehashing (=double hashing) verder wil uitdokteren daar deze mij het interessants lijkt en deze dus ook in de .Net BCL implementatie zit.

Mijn Add() methode, steekt een value op de gepaste index (=hash(key)) van mijn array. Bij een collision ga ik gewoon enkele keren proberen te "double hashen" totdat er een indexnummer tevoorschijnkomt die niet bezet is. Als dat ook niet lukt, ga ik mijn array expanden om vervolgens alle keys hun hashes te herberekenen, om daarna nog eens te proberen de Add() te vervolledigen.

Nu, dit is zowat de meest basis redenering denk ik. En het werkt wel een beetje.
Maar, ik begrijp eigenlijk geen snars van wat er nu PRECIES in de System.Collections.Hashtable gebeurt.

Ten eerste snap ik de wiskunde niet achter die standaard hash functie. Waarom nu net die? Waarom bit shiften met 5? Enzoverder... (Ik snap natuurlijk de modulo wél)
Ik snap hun seed en incr variabelen niet, evenmin hun ding met de InitHash().
Ik weet niet waarom ze in hun "Entry" een hash_coll bijhouden. Ik vermoed dat ze dit gebruiken voor performantie of bij het rehashen bij een expand van de array.
Verder ben ik ook niet helemaal zeker over de private vars count, occupancy (wat het verschil ?) en loadsize en loadfactor. Bedoelen ze niet "actualLoadFactor" en "optimalLoadfactor"?
Ook zitten de te goochelen met variabelen alla num1, num2, num3, index2, ....

Ik word er helemaal gek van. Het enige wat ik vond van enig nut: MSDN: Part 2: The Queue, Stack, and Hashtable

Maar zoals reeds gezegd, kan ik mijn brein niet om die hashfunctie krijgen.
Ik wil absoluut verder met dit verhaal, maar heb de neiging van hier en daar een missing link te hebben.

Hulp is nuttig in dit geval!

Ik wil hierna verder met binary tree, bst, b-tree, indexes, disk implementaties, vul het rijtje aan, ...
Het zal iig een harde leerschool worden, gezien mijn struggles met iets relatief eenvoudig als hasing : (
Voor wie mijn huidige test wil zien: https://github.com/Userna...Hashtables/MyHashtable.cs
Deze werkt wel niet meer momenteel, de hash functie klopt niet alsook het offset probeersel.

[Soultaker]

Misschien handing om de hashfunctie waar je 't over hebt te linken?

In z'n algemeenheid worden hashfuncties voor dit soort doeleinden vooral ontworpen om heel snel te berekenen te zijn. Verder moet zo'n functie een beetje uniform zijn (op z'n minst voor “typische” invoer) en een beetje goed gedistribueerd over het bereik van de functie. Als 't daaraan voldoet is 't al snel goed genoeg.

[pedorus]

Heb je nu de source bekeken of niet? Ik kan me herinneren dat er vrij uitgebreide comments instonden: Davio in "De Devschuur Coffee Corner - Iteratie 2"

[SideShow]

Natuurlijk, ik heb de source voor me staan, anders weet ik toch niet te vertellen over de privates die men gebruikt?
Ik gebruik dotPeek van JetBrains.

*edit: ah, en dus mis ik zo de comments lees ik net
*edit: heh, dat zijn heel wat comments ... hopelijk kan ik daar morgen verder mee :]

[ Voor 32% gewijzigd door SideShow op 11-10-2012 23:08 ]

[RobIII]

SideShow schreef op donderdag 11 oktober 2012 @ 22:55:
Ik gebruik dotPeek van JetBrains.

*edit: ah, en dus mis ik zo de comments lees ik net

I.p.v. dat je reflection/disassembly gebruikt: http://referencesource.microsoft.com/ (how-to voor VS integrate of gewoon compleet downloaden)

---

Als je download gaar is of lijkt te zijn: zorg dat 't bestand een .msi extensie heeft (bij mij kreeg 't een .aspx extensie ). Het specifieke bestand dat je zoekt (hashtable.cs) vind je ook hier.

[ Voor 55% gewijzigd door RobIII op 11-10-2012 23:30 ]

[HMS]

Er is genoeg literatuur te vinden over hash tables in het algemeen, (bijna?) elke universitaire informatica opleiding biedt wel een 'Algoritmen en Data structuren' vak aan (of iets van die strekking).

Google heeft hier genoeg info over lijkt mij: https://www.google.nl/sea...&sourceid=chrome&ie=UTF-8

Als je een bepaalde implementatie probeert te doorgronden, tja daar zouden nog wel eens ongedocumenteerde 'hacks' / optimalisaties in kunnen zitten die niet 1,2,3 duidelijk zijn.

~edit: Daarnaast lijkt het mij nuttiger om te weten wat de sterke en zwakke punten van elke datastructuur zijn, zodat je de een bewuste keuze kan maken voor bijv. een Double-Linked List ipv. een ArrayList.

[ Voor 15% gewijzigd door HMS op 12-10-2012 19:19 ]