Hashing an Array - Methods?

[spudw2k]

My current idea involves iterating through the array and recalculating the hash based on the previous hash and appending the next element as I go.

#include <Array.au3>
#include <Crypt.au3>
Dim $arr[1][3][2]=[[["All","Your"],["Base","Are"],["Belong","To Us"]]]   ;Declare an Array for Testing
$bin = _HashArray($arr)
ConsoleWrite($bin & @CRLF)

Func _HashArray($arr)
    Dim $enc   
    Global $arrDims[1][2]=[["ElementIdx","ElementCount"]]   ;Create an Array to Track Dimensions and Elements
    For $x = 1 to UBound($arr,0)
        ReDim $arrDims[$x+1][2]
        $arrDims[$x][0]=0
        $arrDims[$x][1]=UBound($arr,$x)
    Next
    Do   ;Loop Through Array Elements
        $var = "$arr"
        For $x = 1 to UBound($arrDims)-1
            $var &= "[" & $arrDims[$x][0] & "]"
        Next
        $enc = _Crypt_HashData($enc & Execute($var),$CALG_MD5)   ;Update Hash
        $arrDims[UBound($arrDims)-1][0] += 1   ;Increment Last Dimension Element
        For $y = UBound($arrDims)-2 To 1 Step -1   ;Increment Dimension Element
            If $arrDims[$y+1][0] = $arrDims[$y+1][1] Then
                $arrDims[$y+1][0]=0
                $arrDims[$y][0]+=1
            EndIf
        Next
    Until $arrDims[1][0]=$arrDims[1][1]
    Return $enc
EndFunc

Sorry the code is confusing. I went off on a tangent to handle multidimensional arrays dynamically.

Does anyone have a recommendation or practice on how to hash an array?

edit: added some comments to the example code

Edited March 30, 2012 by spudw2k

[guinness]

Do you mean Associative Arrays? If I'm wrong then sorry about that.

[spudw2k]

Not exactly. I'd basically like to have a unique value (calculated hash seemed appropriate) generated by an array of data.

[guinness]

OK. Why not use _ArrayUnique or a similar approach and then calculate the hash or vice versa. You'll have to modify it for 2d Arrays, but this isn't a challenge for you.

[spudw2k]

I think array unique filters out duplicates...yes? I want to retain all my array data (which may or may not already be unique).

I guess I was mostly wondering if the way I am doing it is any good or if there is a better way besides my own proprietary take on it.

Edited March 30, 2012 by spudw2k

[guinness]

Sorry spudw2k, seems I'm burnt out for today as I'm not providing correct answers.

Edited March 30, 2012 by guinness

[spudw2k]

Hey no sweat. You could still script circles round me any day.

[guinness]

I doubt it!

[spudw2k]

You're too modest mr. mvp.

[jchd]

Let me offer what comes to my mind but realize I may have got you wrong.

Feed your array to a (modified or not!) version of the code below, optionally removing all formatting and displaying code you don't need. Then hash the resulting string. As long as you don't touch the formatting (or lack thereof) in the dump function, your hash will be reproductible whatever content you have. Well almost, don't forget that objects are opaque so you can't easily hash their "contents".

Debugging usage is ConsoleWrite(_VarDump($MyArray) & @LF).

EDIT: buggy code removed. See correction a few posts below. Sorry for that.

Edited April 2, 2012 by jchd

[spudw2k]

Thanks for the contribution. I can definately understand that there's be a performance issue with calculating a hash once for a long string vs each element in an array. It didn't seem to take too long for my needs though. I thought i'd be a good way to make the hash more complex, but maybe i shouldn't even care.

#include <Array.au3>
#include <Crypt.au3>
Dim $arr[1][3][2]=[[["All","Your"],["Base","Are"],["Belong","To Us"]]]   ;Declare an Array for Testing
$arrStr = _DynArrayToString($arr)
ConsoleWrite($arrStr & @CRLF)
$bin = _Crypt_HashData($arrStr,$CALG_MD5)
ConsoleWrite($bin & @CRLF)

Func _DynArrayToString($arr)
    Dim $str
    Global $arrDims[1][2]=[["ElementIdx","ElementCount"]]   ;Create an Array to Track Dimensions and Elements
    For $x = 1 to UBound($arr,0)
        ReDim $arrDims[$x+1][2]
        $arrDims[$x][0]=0
        $arrDims[$x][1]=UBound($arr,$x)
    Next
    Do   ;Loop Through Array Elements
        $var = ""
        For $x = 1 to UBound($arrDims)-1
            $var &= "[" & $arrDims[$x][0] & "]"
        Next
        $str &= $var & Execute("$arr"&$var)
        $arrDims[UBound($arrDims)-1][0] += 1   ;Increment Last Dimension Element
        For $y = UBound($arrDims)-2 To 1 Step -1   ;Increment Dimension Element
            If $arrDims[$y+1][0] = $arrDims[$y+1][1] Then
                $arrDims[$y+1][0]=0
                $arrDims[$y][0]+=1
            EndIf
        Next
    Until $arrDims[1][0]=$arrDims[1][1]
    Return $str
EndFunc

Edited April 1, 2012 by spudw2k

[jchd]

It isn't only a performance issue. Hashing the type as well makes a difference: any array element whose content was "123" and gets changed to123 won't lead to the same hash if you hash the type along with the value. It may or not impact your use case but in general I thought it would be safer.

[spudw2k]

I guess I missed something. I thought your vardump code ultimately made a giant string of the hash. Perhaps I didn't look at your source thouroughly.

[czardas]

Nice example jchd.

[jchd]

Not at all, it's plain wrong with some types. I'm fighting fixing it (at what I posted was an old and buggy code anyway).

Oh well... Stay tuned.

Here is a corrected version. It's not pretty but should work much better.

Note that the new Null keyword needs the 3.3.9.2 beta.

expandcollapse popup

;
; dump variables
;
; sample data
Local $var = ObjCreate("shell.application")
Local $s = DllStructCreate("dword;byte[3];dword[14]")
DllStructSetData($s, 1, 0xdeadbeef)
DllStructSetData($s, 2, 0x67, 1)
DllStructSetData($s, 2, 0x78, 2)
DllStructSetData($s, 2, 0x89, 3)
DllStructSetData($s, 3, 0x89674523, 14)
Local $ar2[2][3] = [[0,1,2], [3,4,5]]
Local $ar[7] = ["1", 2, Binary("0x12345678"), WinGetHandle("[active]"), $s, _
Binary("0x12349999999999999999999999999999999999988888888888888888888888888888888888888888888888888888888888888888889999995678"), $ar2]
Local $array[16] = ["abc def", 123456789012345, "129", 129, 119.0 + 3 * 3.3333333333333333333333, 129.0000000001, _
1.29e134, Default, 1.0/0.0, Null, $ar, (1 = 1.0), Ptr(-12), Ptr(123456) - Ptr(123444), 0/0, _
"aaaaaaaafvsdnlodvgnlsdvnlovsnlodvsnlosdvnldvndvnlodnldfnoqdfnlodfnoldfnlodvfnlodvfnoldvnlodnlovdnlodvnldvnlvdnlozzzzzzzzz"]
; usage
ConsoleWrite("$var is: " & _VarDump($var) & @LF & @LF)
ConsoleWrite("$array is: " & _VarDump($array) & @LF)

Func _VarDump(ByRef $vVar, $sIndent = '')
Local $ret, $len
    Select
  Case IsDllStruct($vVar)
   $len = DllStructGetSize($vVar)
   Local $bstruct = DllStructCreate("byte[" & $len & "]", DllStructGetPtr($vVar))
   $ret = 'Struct(' & $len & ') @:' & Hex(DllStructGetPtr($vVar)) & ' = '
   If $len <= 32 Then
    Return($ret & DllStructGetData($bstruct, 1))
   Else
    Return($ret & BinaryMid(DllStructGetData($bstruct, 1), 1, 16) & ' ... ' & StringTrimLeft(BinaryMid(DllStructGetData($bstruct, 1), $len - 15, 16), 2))
   EndIf
        Case IsArray($vVar)
   Local $iSubscripts = UBound($vVar, 0)
   Local $sDims = 'Array'
   $iSubscripts -= 1
   For $i = 0 To $iSubscripts
    $sDims &= '[' & UBound($vVar, $i + 1) & ']'
   Next
            Return $sDims & @CRLF & _VarDumpArray($vVar, $sIndent)
        Case IsBinary($vVar)
   $len = BinaryLen($vVar)
   $ret = 'Binary(' & BinaryLen($vVar) & ') = '
   If $len <= 32 Then
    Return($ret & $vVar)
   Else
    Return($ret & BinaryMid($vVar, 1, 16) & ' ... ' & StringTrimLeft(BinaryMid($vVar, $len - 15, 16), 2))
   EndIf
        Case IsBool($vVar)
            Return 'Boolean ' & $vVar
        Case IsFloat($vVar) Or (IsInt($vVar) And VarGetType($vVar) = "Double")
            Return 'Double ' & $vVar
        Case IsHWnd($vVar)
            Return 'HWnd ' & $vVar
        Case IsInt($vVar)
            Return "Integer(" & StringRight(VarGetType($vVar), 2) & ') ' & $vVar
        Case IsKeyword($vVar)
   $ret = 'Keyword '
   If $vVar = Null Then
            Return $ret & 'Null'
  Else
            Return $ret & $vVar
  EndIf
        Case IsPtr($vVar)
            Return 'Pointer @:' & StringTrimLeft($vVar, 2)
        Case IsObj($vVar)
            Return 'Object ' & ObjName($vVar)
        Case IsString($vVar)
   $len = StringLen($vVar)
   $ret = 'String(' & $len & ") '"
   If $len <= 64 Then
    Return $ret & $vVar & "'"
   Else
    Return($ret & StringMid($vVar, 1, 32) & ' ... ' & StringTrimLeft(StringMid($vVar, $len - 31, 32), 2)) & "'"
   EndIf
        Case Else
            Return 'Unknown ' & $vVar
    EndSelect
EndFunc
Func _VarDumpArray(ByRef $aArray, $sIndent = @TAB)
    Local $sDump
    Local $sArrayFetch, $sArrayRead, $bDone
    Local $iSubscripts = UBound($aArray, 0)
    Local $aUBounds[$iSubscripts]
    Local $aCounts[$iSubscripts]
    $iSubscripts -= 1
    For $i = 0 To $iSubscripts
        $aUBounds[$i] = UBound($aArray, $i + 1) - 1
        $aCounts[$i] = 0
    Next
    $sIndent &= @TAB
    While 1
        $bDone = True
        $sArrayFetch = ''
        For $i = 0 To $iSubscripts
            $sArrayFetch &= '[' & $aCounts[$i] & ']'
            If $aCounts[$i] < $aUBounds[$i] Then $bDone = False
        Next
        $sArrayRead = Execute('$aArray' & $sArrayFetch)
        If @error Then
            ExitLoop
        Else
            $sDump &= $sIndent & $sArrayFetch & ' => ' & _VarDump($sArrayRead, $sIndent)
            If Not $bDone Then
                $sDump &= @CRLF
            Else
                Return $sDump
            EndIf
        EndIf
        For $i = $iSubscripts To 0 Step -1
            $aCounts[$i] += 1
            If $aCounts[$i] > $aUBounds[$i] Then
                $aCounts[$i] = 0
            Else
                ExitLoop
            EndIf
        Next
    WEnd
EndFunc

Edited April 2, 2012 by jchd