Using large amounts of hashtables

[Molekyle]

I've been using hashtables in my map to make spells MUI. Each spells has it's own hashtable for indexing purposes.

At this point the amount of spells (and thus hashtables) has reached a quite high number.
So I started to wonder:
1) Is there any limit to the amount of hashtables that I can use in my map?
2) Are there any drawbacks linked to the usage of a high number of hashtables?

 

[Binsu]

For the limits this might help you: Hashtable Limits

It said 255 or 257 I think...

 

[Molekyle]

Thank you. I suppose that's a start : )

 

[Binsu]

No problem, bro. Just some search will answer your problem. Cheers!

 

[edo494]

actually using multiple hashtables is a slightly faster then using one hashtable, because as hashtable gets filled, there happenes more and more collisions, so the hashing algorithm has to handle them, decreasing performance. However, there is the drawback of 256 hashtbales limit(I also did some tests, at index 256+ it said that its handle id is 0(dont forget, starting index is 0))

 

[defskull]

You have to be smart in this situation.
As for example, the limit of index per hashtable is 8191, you can use like 100 index per Hashtable, on average, a spell costs like 5 to 7 index, that means you can allocate 14 ~ 20 spells per Hashtable.

 

[Almia]

Actually, If you asked me, 1 hashtable is enough. Hashtables are just a "group of variables". I mean, Isn't 4611686014132420609 space of value per hashtable enough for you?

 

[PurgeandFire]

You have to be smart in this situation.
As for example, the limit of index per hashtable is 8191, you can use like 100 index per Hashtable, on average, a spell costs like 5 to 7 index, that means you can allocate 14 ~ 20 spells per Hashtable.

The index limit is 8191 for arrays, but not for hashtables:

18446744073709551616

possible keys per single hashtable

4703919738795935662080

for 255 hashtables

this is over 4gb (memory size limit for 32bit OS)

But I agree with defskull's statement about limiting the number of hashtables you use. You can often use one hashtable for multiple spells. If you are using keys, just make sure the other key is different. You can also try swapping the parent and child keys if that makes it easier for you.

 

[Spartipilo]

I've always dreamed about a single hashtable for everything If you do smart cleaning and coding you may get away with most of your map stuff with a single Hash.

 

[defskull]

Isn't that what Table did over at the vASS side ?
But then again, its complexity is 1(n) meaning it will be slower with increasing data size.
Yoi gotta be smart though.

 

[PurgeandFire]

Isn't that what Table did over at the vASS side ?
But then again, its complexity is 1(n) meaning it will be slower with increasing data size.
Yoi gotta be smart though.

Yeah, that is what Table did.

It's complexity is O(1) (at least for our purposes). The true algorithm may differ slightly but we at least accept it as O(1).

 

[Maker]

But then again, its complexity is 1(n) meaning it will be slower with increasing data size.

Use the big O notation with complexity. Hashtables have O(1) complexity, but it starts degrading when more data is stored.

However we have to be reasonable when thinking about the degradation. Even if you use a single hashtable for all your spells in your map, there would not be any noticeable (or even easily measurable) performance degradation.

 

[Almia]

Isn't that what Table did over at the vASS side ?
But then again, its complexity is 1(n) meaning it will be slower with increasing data size.
Yoi gotta be smart though.

As of what Purge and Maker, its O(1) not 1(n).

Yeah, Magtheridon96 (as stated in defskull's resource), hashtable search operations becomes more slower when more datas are stored inside it. It would be better if we had a Hashmap which can detect 2 trillions key collisions(just like what Mag showed me about an O(1) hashmap)