Struct-sized D4 table

[WaterKnight]

At some points in map coding, I face a situation where I have to assign a value to a combination of more than two struct instances.

var[red][green][donald duck][muzzel] = val

Since the default struct size is 8192=2^13, which is also the limit for arrays, I thought it could make sense to split up a hashtable to match this number. A hashtable has 2^64 slots, so four structs fit in and 2^12=4096 remain (multiplied by the 254 other possible hashtables). This excess space can be used as the attribute indicator, what should be assigned to the struct instance combination. The number is large enough to be used scope-overlapping like the key-function of vJass provides. You may also create a new table everywhere but unless you tailor them precisely, the 255 limit is quite reachable.

In general, it would be nice to know if the performance gain by splitting data on different hashtables compensates for the overhead.

 

[muzzel]

I presume you dont really need that much space but your keys are in big ranges. So the resulting data structure will usually be very sparse. For that purpose i think using an appriate hashing function can be more efficient.
h : (key1, key2, key3, key3) -> integer
Other than with normal indexing the resulting hashs should be very bounded so h should be non-injective. Subsequently collisions are possible and you need to handle them (with linkedlists or with multiple hashing).

Anyway i think u know how hashing works ^_°

 

[Malhorne]

You can allocate more space to a struct :

struct MyStruct [10000]
    //Do some stuff...
endstruct

 

[WaterKnight]

You can allocate more space to a struct :

struct MyStruct [10000]
    //Do some stuff...
endstruct

Yes, but then a single array won't do anymore and the capacity to account for becomes a problem. I am also thinking about language-supported data structures though. Like you can write "var[a][c] = val" and the compiler automatically converts it to a fitting method.

Hashing/looking for collisions sounds expensive. Then you can as well use gamecaches, only that you leak strings en mass there.

 

[Dr Super Good]

A hashtable is called its name for a reason. They are not designed for bulk data storage and suffer from O(n) degradation when used to store large amounts of data. Splitting across multiple hashtables can give a speed advantage in such a case.