hash-table in pure AutoIt

[AspirinJunkie]

We use hash tables quite often in AutoIt. Be it the Scripting.Dictionary object or now the built-in AutoIt maps.
But using something is still a difference to understanding how these data structures work internally.

To make this more understandable for me I thought: What could be more obvious than implementing my own hash table in AutoIt?
The result is this UDF.
So if you want to understand for yourself how hash tables work exactly, you can have a close look at them in familiar AutoIt code.

For productive purposes the UDF is of course rather not intended, because the alternatives Scripting.Dictionary and AutoIt-Maps offer more.
Only from a very large number of elements (~ 1,000,000 elements) this UDF could be faster than the AutoIt maps.

How to use the hash table?:
example #1:

#include "hashtable.au3"
#include "Array.au3"

Global $aTable = _hashtable_Create()

_hashtable_Add($aTable, "banana", "the value of banana")
_hashtable_Add($aTable, "apple", "the value of apple")
_hashtable_Add($aTable, "apricot", "the value of apricot")
_hashtable_Add($aTable, "orange", "the value of orange")

; remove element:
_hashtable_Remove($aTable, "apple")

; get value with key:
$value = _hashtable_Get($aTable, "apricot")
MsgBox(0, "value for: apricot", $value)

; get the Keys as an array
$aKeys = _hashtable_getKeys($aTable)
_ArrayDisplay($aKeys, "The keys of the hash-table", "", 64)

; get the values as an array
$aValues = _hashtable_getValues($aTable)
_ArrayDisplay($aValues, "The values of the hash-table", "", 64)

example #2:

#include "hashtable.au3"
#include "Array.au3"

Global $aTable = _hashtable_Create()

For $i = 1 To 10000
    _hashtable_Add($aTable, "element " & Random(1, 1000, 1), "test-string " & $i)
Next

; get the Keys as an array
$aKeys = _hashtable_getKeys($aTable)

; get the values as an array
$aValues = _hashtable_getValues($aTable)

; get all key-value pairs
$aKeyValues = _hashtable_getKeyValues($aTable)
_ArrayDisplay($aKeyValues)

 

hashtable.au3

[genius257]

Very nice! 😃

What reference(s) did you use when creating this (just curious).

If this thread is with the intent to understand hashmap/hashtable implementations, here is one i ported from Java 8 for fun: https://github.com/genius257/au3-hashmap/tree/main

If my link does not belong in this thread, let me know and I'll edit it out

[AspirinJunkie]

In fact, there was no direct reference.
Primarily, the UDF is actually built from scratch with the help of some educational presentations just to achieve the learning effect.
Only the hash function (djb2) I got by research for a suitable function.

The real reason for this UDF are my performance tests for the new datatype Map in AutoIt.
I wanted to understand the obtained results and why they behave in such a way especially with large element sets.
For this I had to understand more what was going on under the hood.
 

19 minutes ago, genius257 said:

If my link does not belong in this thread, let me know and I'll edit it out

No, please don't. Leave it in.
It's not about a concrete implementation or a productive use, but to make others understand what happens internally in a hash table.
It makes sense to compare several implementations.

What I like in your code is that the hash function depends on the data type. In my case, one is simply used for everything (which I thought made sense, since only integers or strings should be used as keys anyway).

Edited March 29, 2023 by AspirinJunkie