darktrym
Fahnenträger
Ich weiß ja, dass hier noch andere anwesend sind mit Uni/FH Hintergrund bzw. Informatik, deshalb dieses Thema.
Beruflich musste ich ein Dictionary implementieren mit festen und bekannten Schlüsseln für eine Prä 2000 Programmiersprache(). Ich wollte Kollisionen und Sondierungen vermeiden.
Die Programmiersprache hat zwar ein Dictionary ählichen ADT aber mit Suchzeit O(log n), binäre Suche.
Es müssen derzeit 163 Schlüssel aka Spaltenbezeichner über eine Hashfunktion in einem Index für ein Array gewandelt werden.
Das funktioniert zwar jetzt, aber ich habe fast einen Tag gebraucht um die Hashfunktion zu designen. Sollte nun weitere Schlüssel hinzukommen, möchte ich vermeiden nochmal so viel Zeit da reinzustecken zu müssen. Gib's Ideen bzw. Dokumente wie man das optimieren kann?
Mein Ansatz derzeit:
Eine Hashfunktion(CRC32), wo nach der letzten Runde die Länge noch verrechnet wird.
Die Spaltenbezeichner können aus a..ZA..Z0..9 bestehen.
Ich nehme nur die 6 markantesten Stellen des Schlüssels, fülle auf wenn nötig.
Ergebnis ist dann ein 32Bit Wert, der dann mit AND auf die Größe des Arrays zurechtgestutzt wird.
Unbenutzte Positionen im Array werden markiert, hilft auch um Kollisionen früh zu erkennen.
Derzeit ist mein Array 8KB groß, kollionsfrei, 75x schneller als TStringlist.IndexOf.
Beruflich musste ich ein Dictionary implementieren mit festen und bekannten Schlüsseln für eine Prä 2000 Programmiersprache(). Ich wollte Kollisionen und Sondierungen vermeiden.
Die Programmiersprache hat zwar ein Dictionary ählichen ADT aber mit Suchzeit O(log n), binäre Suche.
Es müssen derzeit 163 Schlüssel aka Spaltenbezeichner über eine Hashfunktion in einem Index für ein Array gewandelt werden.
Das funktioniert zwar jetzt, aber ich habe fast einen Tag gebraucht um die Hashfunktion zu designen. Sollte nun weitere Schlüssel hinzukommen, möchte ich vermeiden nochmal so viel Zeit da reinzustecken zu müssen. Gib's Ideen bzw. Dokumente wie man das optimieren kann?
Mein Ansatz derzeit:
Eine Hashfunktion(CRC32), wo nach der letzten Runde die Länge noch verrechnet wird.
Die Spaltenbezeichner können aus a..ZA..Z0..9 bestehen.
Ich nehme nur die 6 markantesten Stellen des Schlüssels, fülle auf wenn nötig.
Ergebnis ist dann ein 32Bit Wert, der dann mit AND auf die Größe des Arrays zurechtgestutzt wird.
Unbenutzte Positionen im Array werden markiert, hilft auch um Kollisionen früh zu erkennen.
Derzeit ist mein Array 8KB groß, kollionsfrei, 75x schneller als TStringlist.IndexOf.