Understanding HashTables

[DotAliscious]

I've found a surprisingly small amount of information on what exactly the HashTable is in JASS and I have a few questions.

function HandleExample takes nothing returns nothing
    local hashtable t = InitHashtable()
    local unit u = GetTriggerUnit()
    
    // what are parentKey and childKey?
    SaveUnitHandle(t, parentKey, childKey, u)
endfunction

I'm familiar with Java and C++, so if you can explain it in terms of the standard libraries of either of those languages that would be great. At first I was thinking that this was just like a Map<Integer, Handle> but it seems that there are two keys (parentKey and childKey) so I'm not sure how to relate that.

Also, creating local hashtables doesn't seem that useful as you would not have access to them in other scopes. Is it common to use a global hashtable for each spell that needs one? Or would you use a global hashtable that stores your hashtables for each spell?

 

[deathismyfriend]

hashtables are 2d arrays. Think of a hashtable as 2 arrays.
There is a better explanation in my tutorial things a guier should know. Look for tutorials on hashtables there is a link at the bottom of my tutorial for one of the tutorials.

 

[DotAliscious]

I see. So you could use the parentKey to house values for a spell or some other subsystem, and the childKey would the specific key for the value being saved. Is this what is normally done?

 

[Adiktuz]

^ uhm, yes... I believe

 

[Garfield1337]

I see. So you could use the parentKey to house values for a spell or some other subsystem, and the childKey would the specific key for the value being saved. Is this what is normally done?

Yes, but instead of doing that yourself, there's a library that does that for you: http://www.hiveworkshop.com/forums/jass-resources-412/snippet-new-table-188084/
Because you can store virtually as much data as you want in a hashtable (hastable indices can go to high numbers), there's no need to use more than 1 per map. There's also a limit of 256 hashtables you can initialize per game.
The Table library creates 1 hashtable and uses advantages of 2 keys to split it into multiple tables.

To use Table library, you basically create an instance of Table wherever you need to store data (spells, systems and whatnot) and store data in that instance. (All of the data is actually stored in that 1 hashtable.) You'd also probably want to have a global variable within scope for every table instance so that you can refer to it and save/load data anytime.

There's also a demo in the Table thread for how to use it.

 

[Imp Midna]

Using one hashtable for everything seems like a bad idea to me. Wouldn't one try to avoid hash collisions if somehow possible? 256 tables is more than enough to give every system in extensive need of a hashtable its own one, with probably even enough remaining so that every spell could have its own table (as spells rarely need them anyways).

 

[Adiktuz]

well, using a single hash might not always be possible...

but as much as you can, we really suggest using just one hash... so that you don't create more objects unnecessarily...

Wouldn't one try to avoid hash collisions if somehow possible?

Using the linked resource above doesn't really cause hash collisions so no problem with that

as spells rarely need them anyways.

Actually, I've seen quite a number of spells that uses hash... especially when they cannot use indexing or use indexing without unit indexer libraries...

 

[deathismyfriend]

Actually, I've seen quite a number of spells that uses hash... especially when they cannot use indexing or use indexing without unit indexer libraries...

You can make any spell with indexing you don't really need hash but it is sometimes a lot easier to make spells with hash rather than indexed arrays or unit indexer with arrays.

 

[Adiktuz]

Theoretically, you cannot due to the index limit
Practically, yes as you won't even possibly reach 10% of the limit

anyway, yeah hash is easier to use as you don't need to create a lot of variables manually...

Also, creating local hashtables doesn't seem that useful as you would not have access to them in other scopes. Is it common to use a global hashtable for each spell that needs one? Or would you use a global hashtable that stores your hashtables for each spell?

What do you mean by local hashtable?

anyway, most spell data that you save into hashtables are normally local to that spell so there's no real need to make them global anyways...

 

[deathismyfriend]

Theoretically, you cannot due to the index limit
Practically, yes as you won't even possibly reach 10% of the limit

anyway, yeah hash is easier to use as you don't need to create a lot of variables manually...

pretty much ya. However i do use indexed arrays for my spells as two extra integers 2 keep a counter on when to do things is not a big deal to me. Especially considering how much slower hashtables are than arrayed variables.

 

[Adiktuz]

yeah... and if it's looping through a list, index is better...

 

[deathismyfriend]

yeah... and if it's looping through a list, index is better...

ya that is why i do spells primarily with indexed arrays.

 

[Garfield1337]

Using the linked resource above doesn't really cause hash collisions so no problem with that

A hashtable doesn't really take up memory space for all the indices given, it maps the keys to a smaller number of indices so it may happen that 2 entries have same indices. When loading data, hashtable determines which one you're looking for among the ones stored within given indices, however, this results in hashtables being slower if stored data indices collide. Having more hashtables greatly reduces the chance of this happening.

 

[chobibo]

Garfield is right.

HashTable [hash(iValA)][hash(iValB)]
not
HashTable [iValA][iValB]

 

[FUJI]

but is it they're both slower??? because hash is needed to be loading the values BUT they're not needed to be recycled just flushing the childhashtables and done, In the indexed arrays are slow too because you needed to recycle them and hard to read (.

 

[deathismyfriend]

indexed array if done correctly is not hard to read.

hashtables are a lot slower than indexed arrays.
hashtable lookup is faster. loading and saving is a lot slower tho.

 

[FUJI]

indexed array if done correctly is not hard to read.

hashtables are a lot slower than indexed arrays.
hashtable lookup is faster. loading and saving is a lot slower tho.

but is there a bad bug or way when creating spell in hashtable??? If there is... Pls let me know )

 

[Adiktuz]

Well, one bad way is if you are too stupid and used the same keys for something...

 

[FUJI]

Well, one bad way is if you are too stupid and used the same keys for something...

Hmmmm...... That's why It collides the key and causing the game to crash??

 

[Adiktuz]

It won't crash right away but it will give you the wrong value for one of the spells using the key... it will only crash if you save different types into the keys

Like

Spell1 - Target is saved into HASH1, parent key = SPELL, child key = TARGET
Spell2 - Target is saved into HASH1, parent key = SPELL, child key = TARGET

Cast Spell1 then Spell2 -> now the target for spell2 will be the one saved

Spell1 - Target is saved into HASH1, parent key = SPELL, child key = TARGET
Spell2 - Damage is saved into HASH1, parent key = SPELL, child key = TARGET

Cast Spell1 then Spell2 -> now the value for HASH1[SPELL][TARGET] is the damage, so if you try to do a load unit for Spell1, it will return a real value rather than a unit, so it will probably crash

but the possibility of the crash requires you to be more stupid than the required stupidity for the override...

So as long as you're careful enough, it won't happen... + as long as you are not using TOO MUCH values that you're actually having conflicting keys already even if you used different keys (as mentioned in earlier posts as I recall)...

 

[FUJI]

This map is crashed during the two spell.

It won't crash right away but it will give you the wrong value for one of the spells using the key... it will only crash if you save different types into the keys

Like

Spell1 - Target is saved into HASH1, parent key = SPELL, child key = TARGET
Spell2 - Target is saved into HASH1, parent key = SPELL, child key = TARGET

Cast Spell1 then Spell2 -> now the target for spell2 will be the one saved

Spell1 - Target is saved into HASH1, parent key = SPELL, child key = TARGET
Spell2 - Damage is saved into HASH1, parent key = SPELL, child key = TARGET

Cast Spell1 then Spell2 -> now the value for HASH1[SPELL][TARGET] is the damage, so if you try to do a load unit for Spell1, it will return a real value rather than a unit, so it will probably crash

but the possibility of the crash requires you to be more stupid than the required stupidity for the override...

So as long as you're careful enough, it won't happen... + as long as you are not using TOO MUCH values that you're actually having conflicting keys already even if you used different keys (as mentioned in earlier posts as I recall)...

So I have one map in here and it is not mine, I downloaded this map somewhere in this hive. Test the map and try to cast electric vortex and ball lightning and see what happens.. The map is already attach

 

[Garfield1337]

Indexing isn't a great way of doing things in GUI. The speed difference between indexing and hashtables is negligible, you're never really going to notice any difference. Unless you need something to be really efficient, like some complicated systems that run most of the time, using hashtables is better.

In indexing, you need to create so many variables and the code ends up longer because of some extra parts indexing uses which ruins readability. Having so many variables is a mess to work with and is supposedly slower (iirc, more variables slows down reading/writing to them).

GUI also obviously doesn't concentrate on speed, so if anything, you'd want your code to be readable and easily editable. If you want speed, use vJASS or Wurst where things like indexing is automatically done and the ugly code that repeats for every spell is hidden from you so you write only what the spell/system actually uses.

 

[FUJI]

Indexing isn't a great way of doing things in GUI. The speed difference between indexing and hashtables is negligible, you're never really going to notice any difference. Unless you need something to be really efficient, like some complicated systems that run most of the time, using hashtables is better.

In indexing, you need to create so many variables and the code ends up longer because of some extra parts indexing uses which ruins readability. Having so many variables is a mess to work with and is supposedly slower (iirc, more variables slows down reading/writing to them).

GUI also obviously doesn't concentrate on speed, so if anything, you'd want your code to be readable and easily editable. If you want speed, use vJASS or Wurst where things like indexing is automatically done and the ugly code that repeats for every spell is hidden from you so you write only what the spell/system actually uses.

^ Agree with you. That's why I'm using hashtable for readability and it is more safety than indexed arrays because in the hashtable you will just save the duration, level, the caster or the target and it is all done by Flushing child hashtables. Unlike Index needed to be recycle, creating sooooo many array variables, and hard readability and it is sensitive in MUI.