[General] Hashtable

[defskull]

Well, should we create a hashtable for every set of spell, OR use only one hashtable to handle all the data in a given map, perhaps an AoS-style map ?
Which is more efficient

 

[Geries]

My opinion is that to create as much hashtable as needs. Putting hundreds of data in one hashtable and to stay still overwievable is ( almost ) impossible. I think. You know you can create 255 hashtables. Of course it doesn't mean that use one hashtable for storing 10 variable...

More hashtable:
- More memory usage
- More bug free( Less chance to make a mistake eg overwrite a value )
- Less difficult code
Less hashtable
- Less memory usage
- More chance to make mistake
- Extremly difficult code with hundreds of indexing and if-es

 

[Frotty]

You should only use one, or a few hashtables for your map.
If you need to attach more Stuff to same ids and keys or different systems its better to have 2 hashtables, also for better organisation.
For every Spell would be waste, also there is a limit on how many hashtables you can create.
A Hashtable also allocates memory just on its own.

 

[Dr Super Good]

Extensive use of a single hashtable can result in more collisions which will degrade interaction performance.

 

[Bribe]

Extensive use of a single hashtable can result in more collisions which will degrade interaction performance.

- if not managed properly. The Table library I wrote is able to handle massive amounts of sharing without any collisions.

 

[axleion]

Extensive use of a single hashtable can result in more collisions which will degrade interaction performance.

or a better control in coding if managed correctly.

 

[Dr Super Good]

- if not managed properly. The Table library I wrote is able to handle massive amounts of sharing without any collisions.

How do you know?
Did you actually check the bucket arrays inside the memory itself to see that no collisions occured?

 

[Bribe]

I could easily detect collisions with the setup I had in the Retro library. Storing millions of real values throughout the game, then firing the coordinate tracebacks - if there were collisions, the coordinates would certainly have been displaced, but they never were.

The only things that can really cause problems within hashtables are StringHashes. There are a lot of collisions there.

 

[Dr Super Good]

Storing millions of real values throughout the game, then firing the coordinate tracebacks - if there were collisions, the coordinates would certainly have been displaced, but they never were.

And this has anything to do with hashtable collision handling?

Due to the finite size of the backing bucket arrays inside a hashtable, storing large numbers of values will result in eventually 2 items being placed at the same bucket. Inorder to still store the value without data curroption, the hashtable eithor starts a linked list for that bucket (infinite capacity) or finds the nearest free bucket and places in that (finite capacity of as many buckets the array has). In eithor case, it has to fall back to a slower algorthim (usually O(n) where n are the number of collisions that happened at that bucket) to search through the collisions. As a result, the more collisions that occur, the slower the hashtable runs when finding a piece of data but the data found will never be curropted (as bucket collisions should never damage data).

I do not know how hashtables work in WC3 due to the high level nature of the language. They eithor use a pare of hashes to map values to a single bucket array or use nested bucket arrays (a bucket array of bucket arrays) to provide better performance for large data quantities. In any case they probably use a linked list or dynamic array for collision handling.

 

[Blackgod]

I don't have understood all why you don't add a very simple tutorial map?