Snippet Rawcode Hashing

[Jesus4Lyf]

Rawcode Hashing​

Requirements:
- Jass NewGen

Code:

globals
    private constant integer HASH_NEXT=53
    private constant integer MAX_HASH_VALUE=8191
    //===================================
    private integer array HashedInt
endglobals

private function Hash takes integer int returns integer
    local integer hash=int-(int/MAX_HASH_VALUE)*MAX_HASH_VALUE
    loop
        exitwhen HashedInt[hash]==int
        if HashedInt[hash]==0 then
            set HashedInt[hash]=int
            return hash
        endif
        set hash=hash+HASH_NEXT
        if hash>=MAX_HASH_VALUE then
            set hash=hash-MAX_HASH_VALUE
        endif
    endloop
    return hash
endfunction

A simple, simple hashing function. Put a (positive) integer in, get an integer out between 0 and 8190. You will be sure to get the same integer each time.

Why this?

• 'AXXX' can't be subtracted from to be within 0-8190, but this allows that to happen (and for attaching).
• 'u000' has the same issue.
• data[GetHandleId(handle)-0x100000] isn't always reliable, and this should be used instead in published systems.

How should one attach to unit types, ability ids or even occasionally handles? Simple. Use simple hashing.

The reason this has been submitted is an increase in people wishing to attach to rawcodes (abil ids and unit/item types - 'xxxx' things, basically) and not knowing how to go about that. This makes it simple. Copy/paste it into your system/scope and away you go. :thup:

Complexity may increase significantly if you exceed around 1000 entries.

So basically, this functions like an indexer for ability ids, unit types, item types, order ids or any other integer type you can think of and want to attach to.

Very efficient.

 

[BlackRose]

    private function DoIt takes nothing returns nothing

I like that function name.

So.... what was the result of
call BJDebugMsg(I2S(dat.orderid))

 

[Jesus4Lyf]

set RawcodeData[int].orderid=5

After that, 5.

The variable name isn't suitable there anymore, but it's just a demo.

 

[kingkingyyk3]

Huh? It can't be done in id-0x100000 ?

 

[uberfoop]

0x100000 is equal to 16^5 or 1,048,576.


Rawcodes, however, are in base 256, and they use ASCII values of characters as the numerals. As such, 0 has a value of 48, and so even '0000' is equal to (48*256^3 + 48*256^2 + 48*256 + 48), or 808,464,432. So basically, not only is 16^5 not going to subtract anything meaningful from these rawcodes to bring them into a 0-2^13 range (as required by wc3 arrays), but also, the range of the rawcodes themselves is far larger than 2^13.



Rawcode values and handle values have very little in common. Except that most people off the street would regard them as 'big' values. But not all big values used in wc3 are lined up such that 'value - offset' works as a perfect hash function.

 

[kingkingyyk3]

lol. I tested "ZZZZ", it is 1515870810.

But... Will it collides?

 

[uberfoop]

But... Will it collides?

I believe the point of the loop within the main method is to run collision checks to avoid collisions.

 

[Jesus4Lyf]

Huh? It can't be done in id-0x100000 ?

That's not reliable anyway. Nothing should ever get approved that uses it. <_<

This is reliable. It does not collide.

>But... Will it collides?
No.

The real question is is it faster than hashtables. (But that is not a question until hashtables exist on a b.net patch...)

 

[Romek]

I doubt this is faster than hashtables. Even so, this can become quite slow if there are collisions.
I think Table is a much better alternative to this (And there are no chances of collisions).

I don't like how you have the struct members at the top of the code, and the user needs to add their own stuff there.
What if you sue this to attach to a units handle id, a unitid and a spellid? Different members + Mess FTL.

Why not make this a module?

 

[Jesus4Lyf]

>I doubt this is faster than hashtables.

To be honest, I'd be somewhat impressed if hashtables were faster. The typical flow in this code is:

// For operator [] takes integer rawcode returns thistype
    local integer hash=rawcode-(rawcode/8191)*8191
    if Rawcode[hash]==rawcode then
    return hash

I'm not sure how fast integer math is in Jass compared to C++. That's all.

>Even so, this can become quite slow if there are collisions.

Nope. It uses a step size when it collides. If you were to start actually filling up maybe 1000 slots, this would get slow. That's not what this was written for.

>What if you use this to attach to a units handle id, a unitid and a spellid? Different members + Mess FTL.

No issues any different to hashtables or Table. <_<

>I don't like how you have the struct members at the top of the code, and the user needs to add their own stuff there.
>Why not make this a module?

Hmm. This is meant to be a copy/paste thing. So you're mapping away, you get to some point where you go... Gee I'd love to permanently associate a small piece of data with that unit type... How can I do that nicely? Ah, I'll just use that Rawcode Hashing method. I read it and it makes sense and I kinda get how it works, I copy paste it in and I'm done.

The core of this is to teach mappers simple hashing. I don't want it to be a module or something because then systems will have to "require" it and stuff, and its stupid.

I wrote this because people are starting to want to attach simple things to unit types and ability ids. Simple solution for a simple issue.

-----

But, two questions:
Should I remove the "free" method and the GetHandleId demonstration?
Should I make this a short tutorial instead of a snippet? I could explain hashing in it and what it does, and how to use the technique, resulting in this simple snippet.

 

[kingkingyyk3]

How about subtracting it with hashed 'AAAA'? It will decrease the value.

 

[Jesus4Lyf]

 

[kingkingyyk3]

globals
    private constant integer STARTING_INDEX = 'AAAA' - ('AAAA' / 8191) * 8191
endglobals

struct RawcodeData extends array // Feel free to rename the struct.
    // Your data to attach to rawcode.
    // Example:
    integer orderid
    // Then you could do set RawcodeData[AbilId].orderid=OrderId("stormbolt")
    // End your data to attach to rawcode.
    
    private static constant integer HASH_NEXT=53
    private integer rawcode
    static method operator [] takes integer rawcode returns thistype
        local thistype hash=thistype((rawcode-(rawcode/8191)*8191)-STARTING_INDEX)
        loop
            exitwhen hash.rawcode==rawcode
            if hash.rawcode==0 then
                set hash.rawcode=rawcode
                return hash
            endif
            set hash=thistype(hash+thistype.HASH_NEXT)
            if integer(hash)>8191 then
                set hash=thistype(hash-8191)
            endif
        endloop
        return hash
    endmethod
    method free takes nothing returns nothing
        set this.rawcode=0
    endmethod
endstruct

 

[Romek]

Why on earth would you do that?
If you're gonna post just for the sake of posting, now's the time to stop.
And if you're clueless about something, don't attempt to correct someone who knows his stuff.

> No issues any different to hashtables or Table. <_<
That gives a nice interface to attach an integer.
This does too, though it's called 'orderid', which is somewhat misleading.
Maybe rename 'orderid' to 'data' or something?

Then you can easily attach structs to rawcodes.

> Should I remove the "free" method and the GetHandleId demonstration?
Why would you do that?

> Should I make this a short tutorial instead of a snippet?
No.

 

[Jesus4Lyf]

:banghead:

local thistype hash=thistype((rawcode-(rawcode/8191)*8191)-STARTING_INDEX)

I hope you realise one day how badly you broke my script for no apparent reason.

>That gives a nice interface to attach an integer.
>This does too, though it's called 'orderid', which is somewhat misleading.
>Maybe rename 'orderid' to 'data' or something?

The idea was you customise this to your purposes. You're actually meant to spam instances of this. Each instance is like a single hashtable.

I suppose I could rename it to data if you really like, but usually you won't actually use a struct here. You usually need like... a trigger or an order id, or a function. Think about what sort of simple things you'd usually need to attach... I could've done this without structs at all, perhaps it would've been better. Just a plain hashing algorithm.

>> Should I remove the "free" method and the GetHandleId demonstration?
>Why would you do that?
This wasn't written for that purpose. I was just showing that you can apply it to anything...

>> Should I make this a short tutorial instead of a snippet?
>No.
'Kay. You sure? <_<

 

[Romek]

> I suppose I could rename it to data if you really like, but usually you won't actually use a struct here.
That'd allow people to just copy this script into their map, and use it from wherever, by attaching structs.

> I could've done this without structs at all, perhaps it would've been better. Just a plain hashing algorithm.
function Hash (integer) -> integer?
Then what'd that integer be used for?
Most likely this:
StructArray[hash] = structinstance

But yeah, go ahead. I'm for this idea.

> This wasn't written for that purpose. I was just showing that you can apply it to anything...
Get rid of it then. I thought that was demonstrating proper usage of this.

> 'Kay. You sure? <_<
...Yeah.

 

[Jesus4Lyf]

Watch out, SOMETHING USEFUL!

globals
    private constant integer HASH_NEXT=53
    private constant integer MAX_HASH_VALUE=8190
    //===================================
    private integer array HashedInt
endglobals

private function Hash takes integer int returns integer
    local integer hash=int+1-(int/MAX_HASH_VALUE)*MAX_HASH_VALUE
    loop
        exitwhen HashedInt[hash]==int
        if HashedInt[hash]==0 then
            set HashedInt[hash]=int
            return hash
        endif
        set hash=hash+HASH_NEXT
        if hash>MAX_HASH_VALUE then
            set hash=hash-MAX_HASH_VALUE
        endif
    endloop
    return hash
endfunction

// Optional
private function HashRelease takes integer int returns nothing
    set HashedInt[int]=0
endfunction

>I thought that was demonstrating proper usage of this.
Well, it kinda was. I mean it's just a hash algorithm. Lol.

I dunno eh. In what form should I post this? This is exactly the same as before. (Although I adjusted it to be between 1 and 8190 instead of from 0, I just like not using 0 because 0 kinda represents null.)

I mean, I could make this a "system" by enclosing that in a library, or keep it snippet-like by just making it that copy/paste thing...

Maybe it looks more useful now, at least. Or more usable, more to the point.

 

[Romek]

This'd be a snippet regardless of which one you use. It's only one function.

Anyway, I prefer the one in post #17.

 

[Strilanc]

- This is going to fail if the rawcode is negative.
- HASH_NEXT doesn't need to be a constant; you only use it once.
- "if integer(hash)>8191 then", should be >=.
- If B collides with A, and you hash A, then hash B, then remove A, then hash B, you will get a second entry for B.

- Jesus4LyF's version is inferior because it makes collisions more likely (because 8190 is not prime).

 

[Jesus4Lyf]

>This is going to fail if the rawcode is negative.
I just modified the notes to include that. This doesn't need to handle negative numbers... (Anyone feel otherwise?)

>HASH_NEXT doesn't need to be a constant; you only use it once.
It's nice to have it in a readily changable place rather that find it in the code. This also allows it to have a name, not just be a random "53" or something for no reason.

>"if integer(hash)>8191 then", should be >=.
As said, I don't believe in returning 0.

>Jesus4LyF's version is inferior because it makes collisions more likely (because 8190 is not prime).
I suppose you're right, actually. Because this was written with rawcodes in mind.

>If B collides with A, and you hash A, then hash B, then remove A, then hash B, you will get a second entry for B.
Frak. I knew I was forgetting something. <_< +rep
I think the best solution traditionally was not to free things. Definitely would be for 90% of uses. <_<
Removed the freeing functionality.

Updated the main script post with a nice, working, 1-8191 no-releasing version of the script. Should be good now.