[vJASS] StringHashEx guaranteed no-collision string hash

[Waffle]

utility, uses Bribe's Table library.
contains some code by other people.

Main utility. you want to use a string key to index in to a hashtable but the keys used are not known ahead of time. a naive approach might use the StringHash() native to turn the string in to an integer key conveniently, however StringHash is not guaranteed (at least that i know of) to only map 1 string to 1 integer. most usages of StringHash assume that no 2 values returned by StringHash be the same if the given inputs differ.

The StringHashEx function provides a convenient replacement for the StringHash() native with the added guarantee that returned hashes be unique (as long as you call it with no more than 2^32 distinct inputs). this is conventient for ex: creating a reverse lookup table for player names to player_id, mapping chat strings to commands in game, .. places where the amount of text processed is not too large yet a hash collision would have rly bad effects.. (like kicking the wrong player or desyncing for most extreme examples)

pros:

• never collides

cons:

• slower than bare StringHash, makes use of hashtable.

if StringHash(a) == StringHash(b) and a != b /*and this is bad for some reason(hashtable index maybe?)*/ then
   StringHashEx(a) != StringHashEx(b)
endif

library StringHashEx requires Table
    /*********************************************************
     *  
     * API:
     *    
     *    function StringHashEx takes string returns integer
     *        for any string parameter this function is guaranteed to return a distinct integer.
     *
     *
     *********************************************************/

    globals
        private constant integer REHASH = 1222483
        private key tbKey
        private Table t = tbKey //allowed due to the way Table works
    endglobals

    function StringHashEx takes string key returns integer
        local integer sh = StringHash(key)
        loop
            if not t.string.has(sh) then
                set t.string[sh] = key
                exitwhen true
            endif
            exitwhen t.string[sh] == key
            set sh = sh + REHASH
        endloop
        return sh
    endfunction

endlibrary

 

[IcemanBo]

How comes the number 1222483?
Maybe it fits good here Small Code Snippets.

 

[Waffle]

the number (REHASH = 1222483) is basically just a large prime that i seemed to like at the moment of writing it.

no deep thought rly went in to that.

my intuition says that having a prime is good, and having a large number is also good. thus i chose a large prime..

prime avoids silly things like cycling thru a small number of available slots and ignoring available empty slots.
large number hopefully makes it so that it takes fewer tries to find a free slot.

since jass2 hashtables expose a 32 bit key it is really rare in most situtations to have a collision tho, so in practise there are only a few numbers that would be bad (large powers of 2 mainly, since they would cause a small cycle of candidates to be tried in an infinite loop till OPlimit kills the script..)

 

[IcemanBo]

I think when you explain the issue in first place it could be useful (not all will directly understand what you mean why StringHashEx() is needed), and it can be approved.

Please also follow standard procedure (JASS Submission Rules) to link to requirement and list the API function.

edit: Awaiting update for now.