Single Hashtable Limits

[Zunariel]

I know that the amount of Hashtable per Map is limited to ~255

but where are the limits of a single hashtable? For my spellsystem I am using a single spell system and it is quite easy, the keys are

Key (Spellname)+Rownumber (indicating the row) into Key (Heroname) in SpellHash

For example I save the min damage of the spell in

"100" in Key "Stormbolt6" into Key in "Mountain King" in Spell Hash.

Now I am creating the fourth hero of my campaign, but I get the feeling that somehow the spell hash doesnt save values anymore.

I am probably at 80 spells x 30 values, so do you think there is now a limit? It sounds unlikely to me because in Sechiron Rises I have probably saved over 300 items with ~20 values in a single hash and everything worked just fine.

 

[DracoL1ch]

2^32 values per 2^32 keys (unlimited)

 

[Ardenian]

After Dr Super Good, one hashtable should not contain more than 200k entries.

 

[Wietlol]

A hashtable can store data on 2 integers between Integer.MIN and Integer.MAX (2^31*-1 and 2^31-1)
That doesnt mean that the total amount of stored values are 2^32^2 though.

You can see it as simple arrays and the hashes are modulo'ed by 8192 so they fit in the array. (As an example, I dont know the exact numbers and storage mechanics.)
So after storing a lot of data in one hashtable, the chance of a data collision increases.
The computation time also increases slightly the more data is in the hashtable but that is negligible.

It is better to have 255 hashtables with all 100 values than 1 hashtable with 25500 values.

 

[Zunariel]

Interesting. Yeah thanks In the meantime I've found out that the error was somewhere else (I forgot to run the trigger which saves the data ;D). But thanks guys, all that is really interesting and good to know.

 

[DracoL1ch]

A hashtable can store data on 2 integers between Integer.MIN and Integer.MAX (2^31*-1 and 2^31-1)
That doesnt mean that the total amount of stored values are 2^32^2 though.

You can see it as simple arrays and the hashes are modulo'ed by 8192 so they fit in the array. (As an example, I dont know the exact numbers and storage mechanics.)
So after storing a lot of data in one hashtable, the chance of a data collision increases.
The computation time also increases slightly the more data is in the hashtable but that is negligible.

It is better to have 255 hashtables with all 100 values than 1 hashtable with 25500 values.

numbers = amount of saved integer values

Gen code

	local integer i=FKJNSKNJGNDGK
	local integer k=0
	local integer z=50+i
	loop
		set k=0
		loop
			call SaveInteger(HY,i,k+100,k)
			call SaveInteger(HY,i,k,1)
			set k=k+1
			exitwhen k>80
		endloop
		set i=i+1
		exitwhen i>z
	endloop
	set FKJNSKNJGNDGK=i
	call BJDebugMsg(I2S(i*80))

it's already 1.2kk values, and reading of 0,0 cell takes 6 mcs, readin of random cell in the GetRandomInt (0,maxKey) and GetRandomInt(0,maxChild) takes 5 mcs (since hashtable's offset already found in the last op and no need to re-search)

degradation isn't big if it ever exists. no reason to make restriction on yourself.

technically speaking, every array is a small hashtable with limited size and a singe parentKey

and there are KEYS inside NewGenEditor, which allows you to remove chance of collisions whatsoever

ed:

ok, there are degradation. It started from 2.5kk values for me, my fps halved at this point (30-32)
but that happened while there are dozen other timers, triggers and inner work happened as well (it's normal dota with all custom triggers and shit). So, unless you gonna store 3kk+ values, and you know how to handle with FlushchildHashtable, you'll be fine with a single hash

 

[Wietlol]

I recommended the 255 hashtables not because of the efficiency.
I said that difference is negligible.

What is more dangerous is data collision.

 

[Arad MNK]

Do not store many things into a hashtable... store many things into many hashtables

 

[Bribe]

In working with early versions of Retro, I stored hundreds of thousands of values in consecutive indices and recalled them; there never were any displacements. That was before I realized FlushChildHashtable existed. It's a safe bet that the WC3 engine handles hashtable collision with critical safeguards in place.