Ahoi,
Für eine Hausaufgabe musste ich einen Hashtable in Java basteln. Anschließend habe ich mich im Netz umgesehen, ob es eine (primitive, so wie die Hausaufgabe) Umsetzung in AutoIt bereits gibt und musste Feststellen: Einige UDFs sind gefühlte 50 Jahre alt (das muss nichts heißen, ich habe keine davon heruntergeladen und ausprobiert), andere benutzen WindowsCOM (sodass ein eventuell vorhandener Student der genau die Aufgabenstellung aus der Hausaufgabe gelöst haben will nichts aus den UDFs lernen kann). Von daher habe ich (mit etwas künstlerischer Freiheit) eine Version in AutoIt gebastelt.
Verbesserungsvorschläge bzw Bugreports sind natürlich gerne gesehen.
(Ich bin 100%ig sicher, dass es Bugs gibt, ich habe sie nur noch nicht gefunden)
For $i = 1000 To 9000 Step 1000
Test($i)
Next
Func Test($n = 1000)
;~ Local $aTable = HTCreate(0) ; Erstellt den Hashtable mit Initialgröße 0 ( er passt sich dynamisch an die gegebenheiten an )
Local $aTable = HTCreate($n*2) ; Erstellt den Hashtable mit Initialgröße $n*2 sodass er beim Füllen nicht vergrößert werden muss.
ConsoleWrite('Elemente: ' & $n & @CRLF)
Local $t = TimerInit()
For $i = 1 To $n Step 1
HTInsert($aTable, HTElement('key:' & $i, 'data:' & $i ^ 2)) ; Fügt Elemente hinzu
Next
ConsoleWrite('Füllen : ' & StringFormat('%.3f', TimerDiff($t)/$n) & ' ms / Element' & @CRLF)
Local $t, $e, $time = 0
For $i = 1 To $n Step 1
$t = TimerInit()
$e = HTGetElement($aTable, 'key:' & $i)
$time += TimerDiff($t)
If $e[1] <> 'data:' & $i ^ 2 Then Return ConsoleWrite('Error' & $i & @CRLF)
Next
ConsoleWrite('Abfragen: ' & StringFormat('%.3f', $time/$n) & ' ms / Element' & @CRLF & @CRLF)
EndFunc
; Erstellt den Hashtable
Func HTCreate($iSize = 0)
Local $aArray[$iSize + 2] = [$iSize, 0]
; in [0] steht den Kapazität
; in [1] steht die Anzahl Vorhandener Elemente
; in [2] bis [2 + Kapazität] sind die Elemente verteilt.
Return $aArray
EndFunc
; Vergrößert oder Verkleinert den Hashtable je nach Füllstand
Func HTRehash(ByRef $aTable, $bRehash)
Local $aNewTable = HTCreate(Int($aTable[1] * 6 + 1)) ; Füllstand alt: ca 66%, Füllstand neu: ca. 17%
For $i = 2 To UBound($aTable) - 1 Step 1 ; Linear durchgehen.
If IsArray($aTable[$i]) And Not ($aTable[$i])[2] Then HTInsert($aNewTable, $aTable[$i], False)
Next
$aTable = $aNewTable
EndFunc
; Fügt ein Element hinzu
Func HTInsert(ByRef $aTable, $aElement, $bRehash = True)
If $bRehash And ($aTable[1] + 1) > Int($aTable[0]/1.5) Then HTRehash($aTable, $bRehash) ; Füllstand > 66% ? -> Größer machen
Local $iHash = Mod(HTHash($aElement[0], 1), $aTable[0]), $i = 2, $eTmp
While True
$eTmp = $aTable[$iHash + 2]
If IsArray($eTmp) Then
If $eTmp[2] Then ExitLoop
If $eTmp[0] = $aElement[0] Then Return False ; Das gleiche geht nicht 2x
$iHash = Mod(HTHash($aElement[0], $i), $aTable[0])
$i += 1
Else
ExitLoop
EndIf
WEnd
$aTable[1] += 1
$aTable[$iHash + 2] = $aElement
EndFunc
; Markiert ein Element als gelöscht und gibt das gelöschte Element zurück
Func HTDelete(ByRef $aTable, $sKey)
Local $iHash = Mod(HTHash($sKey, 1), $aTable[0]), $i = 2, $aElement
While True
$aElement = $aTable[$iHash + 2]
If IsArray($aElement) Then
If $aElement[0] = $sKey Then
If $aElement[2] = True Then Return False
$aElement[2] = True
$aTable[$iHash + 2] = $aElement
$aTable[1] -= 1
If $aTable[1] <= Int($aTable[0]/15) Then HTRehash($aTable, False) ; Füllstand < 7% ? -> kleiner machen
Return $aElement
EndIf
$iHash = Mod(HTHash($sKey, $i), $aTable[0])
$i += 1
Else
Return False
EndIf
WEnd
EndFunc
; Gibt das Element mit dem Key $sKey zurück
Func HTGetElement(ByRef $aTable, $sKey)
Local $iHash = Mod(HTHash($sKey, 1), $aTable[0]), $i = 2, $aElement
While True
$aElement = $aTable[$iHash + 2]
If IsArray($aElement) Then
If $aElement[0] = $sKey Then Return $aElement
$iHash = Mod(HTHash($sKey, $i), $aTable[0])
$i += 1
Else
Return False
EndIf
WEnd
EndFunc
; Verpackung für das Element
Func HTElement($sKey, $xData) ; [0] - Key, [1] - Daten, [2] - Marker obs gelöscht ist.
Local $aElement = [$sKey, $xData, False]
Return $aElement
EndFunc
; Gibt den Key zurück
Func HTElementGetKey($aElement)
If IsArray($aElement) Then Return $aElement[0]
EndFunc
; Gibt den Inhalt zurück
Func HTElementGetData($aElement)
If IsArray($aElement) Then Return $aElement[1]
Return False
EndFunc
; Hashfunktion: Marke Eigenbau, habe sie kurz mit verschiedenen Keys und "i" laufen lassen und geprüft und es sah ganz okay aus. Wahrscheinlich
Func HTHash($sStr, $i = 1, $nBit = 16) ; ist sie aber im Vergleich zu anderen Hashfunktionen nicht so der Burner. "Schnell" ausrechnen kann sie
If StringLen($sStr) <= 2 Then $sStr &= $i & $sStr ; auch nur AutoIt, weil hier ein pow(double, double) genausolange dauert wie ein int + 1.
Local $bBin = StringToBinary($sStr), $iLen = BinaryLen($bBin), $exp = $i^0.111, $bRet = Int(BinaryMid($bBin, 1, 2))^$exp
If Mod($iLen, 2) Then $bBin &= 'AA' ; 10101010
For $ii = 3 To BinaryLen($bBin) Step 2
$bRet = BitXOR($bRet, Int(Int(BinaryMid($bBin, $ii, 2))^$exp))
Next
Return BitAND($bRet, Int(2^$nBit - 1))
EndFunc
Alles anzeigen
lg
M