Hashtable

[Rui]

Does anyone know — or is able to point me to the right tutorial that explains it — what size is the initial size of the array that supports the hashtable and how it grows? Does it have a threshold of 0.75?

I have an array of hashtables and the lot of them are going to be filled up to almost 256 items (not quite, but I know that you shouldn't fill it up completely).

 

[Bannar]

I can not imagen situation where you would need an array of hashtables.
You can have up to 256 hashtables declared in given map, thus such array would start with index 0 -being 1st hashtable and end with 255 -index of last hashtable.

However, I'm not sure if you really need what you ask about. If I haven't understood you correctly - could you elaborate the topic a bit more?

There is a principle that has been made flesh long time ago. It's body was called Table and soul described as "one map, one hashtable". After it's update by Bribe, there is nothing more you would ever need.

In most cases you save/load data via childkey, leaving parentkey with index 0 - usage is lost. Table takes control over those parentkeys, greatly reducing overhead. Whenever you do need to take control over both parent and child keys, use TableArray instead.
You can have up to 2 ^ 31 - 1 Table instances and ~2 ^ 18 TableArray instances declared.

 

[edo494]

if table was intelligent enough to utilize negative parent keys, you could've used up to 2^32 - 1 indexes

TableArray count really depends on the size of TableArrays, if each of your TableArray has only 1 Table instance in them, you can have equal amount of them

 

[Bannar]

~2 ^ 18 TableArrays of size 8192. My mistake not to add important "size" suffix.

 

[Rui]

if table was intelligent enough to utilize negative parent keys,

Hold on... I can't use negative keys? Pheck D;

I'll try to reformulate. In my algorithms and data structures course we learned about Hashmaps through Java's parametric types, I suppose the various load functions just load the entry and interpret it as a specific type?

Anyhow, what we learned was that the underlying data structure was an array. My question is: is it known, when you call InitHashtable(), what is the initial size of the underlying array and how it increases when the threshold is hit?

 

[GhostWolf]

The underlying structure is an array? not only can you not know for certain how the implementation is, well, implemented (which may well change between languages, libraries, etc.), it also wont make sense to have an array.
Either way, without knowing how it is implemented, how would you know its characteristics?

Now, if you think you need multiple hash maps because you are going to have an amazingly large total of 256(!!) items....nope.
Assuming Blizzard's implementation doesn't create collisions on every insert, you will probably be fine also with a million keys.

Finally, why do you even care? is this site back to silly micro optimizations that wont actually affect anything?

 

[Rui]

Huh, I wouldn't know, I'm not into that sorta stuff =P

Someone told me the maximum number of entries you could store in a hashtable was 256 items? It can store a million after all?

 

[Frotty]

Huh, I wouldn't know, I'm not into that sorta stuff =P

Someone told me the maximum number of entries you could store in a hashtable was 256 items? It can store a million after all?

I'm pretty sure that "Someone" ment 256 hashtables in a map, as that is the only limit with that amount.
The single Hashtable can have millions of entries, however it gets drastically slower after a few 10k (water benchmarked this)

 

[Bannar]

Hold on... I can't use negative keys? Pheck D;

Yes, you can. However, Table instances get allocated starting from "less" constant (default 8192) and grows, thus those instances never will be set to negative value.

My question is: is it known, when you call InitHashtable(), what is the initial size of the underlying array and how it increases when the threshold is hit?

You can not compare array with hashmap directly, and unfortunately, we have no access to the underlying object. As such, the correct value of initial size is unknown, yet as Frotty mentioned, after certain amount of keys, its getting slower.
Nonetheless, one can not fully fill the hashtable, no matter how big is your map (ofc if you aren't doin anything silly).

 

[WaterKnight]

255 hashtables, from id 1 to 255. It may make sense to have more hashtables or even an array for burden distribution, special tasks or to have an additional key dimension.

 

[Rui]

Wow, I went to check out Bribe's Table... I really DON'T know vJASS T.T lots of awkward stuff there? private struct $TYPE$s ? What functionality comes with extending array?

Thanks to everyone for the attention! =)

 

[Bannar]

There are plenty of struct tutorials avaible either on hive or the helper. Array Structs.
Bribe's Table uses macros do provide intuitive and convenient syntax regardless of what you are dealing with. Check out demo code and systems description for more information.

Table-usage examples can be found throughout jass section -> most resources use it or have it at least as optional.

Macros allows for easier implementation of struct/module spam required for typecasts/conversions between struct types so our intuitive syntax-goal is achieved
Considering that hashtable supports quite few types, we can also say that those macros greatly improve system's readability and reduce code size on paper (tho compiled size is completely differend). Bribe made it as thin as it gets and with latests updates, more utility has been brought (although it has been done before, yet because of various suggestions API has been changing).