Hashtable function

12-29-2003, 11:37 PM

As many know, you can get a unique integer for abilities, orders, unit types, etc altough this integer is much too large to use as an array index, obviously a hash table is called for. Here is my simple implementation:
Uses two global variables.
HashTableSize - AN integer, should be set to a prime number, say 1009
HashTable - An array of integers, size should be set to HashTableSize

Code:

function Hash takes integer id returns integer
    local integer i = ModuloInteger(id, udg_HashTableSize)
    local integer d = 1
    loop
        exitwhen (udg_HashTable[i] == id)
        if (udg_HashTable[i] == 0) then
            set udg_HashTable[i] = id
        else
            set i = ModuloInteger(i + d*d, udg_HashTableSize)
            set d = d + 1
        endif
    endloop
    return i
endfunction

For those who have not studied hash tables, the basic idea is the function will take unique large numbers (say between 0 and 2 billion) and spit out unique small numbers, say between 0 and 1009 - and it's blazing fast in most cases. Whats more the function will always return the same small number for a given large number (altough not nessecarly between different runs of the map). It should also be obvious that it wont work if there are more than 1009 large unique numbers, which should not be the case for things like hero spells, unit types etc, but is something to be aware of, because as a hash table fulls (to more than about 40%) performance can become quite shocking, therfore a suitably large hash table should be used, and also it would be wise to use differnent tables for different sets of data (ie abilities, unit types), AFAIK the only way to do this in JASS is to manually make multiple copies of the function and tables.

I have on ocassion thought of uses for it too, the primary use is performance optimization, say you have 100 trigger enhanced custom abilities, and want to speed up your triggers. You could create a trigger array, and do something like:

Code:

set AbilityTriggers[Hash('A000')] = TriggerAbilityA000
set AbilityTriggers[Hash('A001')] = TriggerAbilityA001
...
set AbilityTriggers[Hash('A0CW')] = TriggerAbilityA0CW

Then have a single action for when a unit uses an ability:

Code:

call TriggerExecute(AbilityTriggers[ Hash(GetSpellAbilityId()) ])

I would be interested to hear if anyone has ideas to make the hash table better or more useful (I use quadratic chaining, secondary clustering might be a problem) or even just good uses for it. I'll probably upload the function to the repository soon.

01-04-2004, 02:55 PM	#2
silverdrake	wtf

01-04-2004, 05:30 PM	#3
Cacodemon	Grater: May I use your function in my project core? You will be mentioned as its author, of course.