Hashtables

[Tar-Quaeron]

Does anyone know how much RAM a global hashtable takes up? Because if it's an array representing 2.1 billion (about the possible range of an integer) * 2.1 billion handles in a table, that's 4*10^18*4 bytes (because the hashtable would store a pointer to the handle in question, i.e. an integer?), i.e. A million terabytes? Yeah, so I guess there's a hashing function (wikipedia) which, from the value you give to the parent and child key assigns a particular index in the array?

I'm just worried, that as I get all excited about hashtables and start using them a lot, the map will take up a lot of memory while it's running.

 

[kingkingyyk3]

Nope, hashtables are memory leak free.
Example you stored a unit in hashtable, then the unit is removed, hashtable reference no long hold that unit anymore.
Hashtables are nothing wrong, but very useful indeed.

 

[Tar-Quaeron]

Oh okay, yeah, I was wondering that too, if after use you had to be like:
call SaveEffectHandle(bla, bla, bla, null). Still, they take up RAM, just like any other variable. Especially if they're global, that memory is never freed while the map runs. For example a global integer array in JASS would take up 8192 * 4 bytes of RAM, i.e. 32 kb, which is negligible, even on 300 MB of RAM as on my computer. Yeah, I'm worried about hashtables though, because just now as I was running my map, it crashed, and I got the message that there wasn't enough memory to work with. Sure, my computer is old, and there were other programs running. But this has always intrigued me, how do Hashtables work in JASS, or rather in C++ as Blizzard designed it for warcraft 3, as the JASS code is just compiled into already existing C++ right?

 

[the Immortal]

Read on them?

JASS may have nothing to do with Cpp. For example the arrays we use in JASS are indeed dynamic, but they seem not to be as C++'s vectors (did a small test somewhere, gonna find it if u want).

First, hashtables use (Surprise!) a hash function on the keys and then store the results into an array. But then we can have different keys with the same hashed value. The most simple workaround would be to store colliding keys in a data structure like linked list or a BST. Optionally they may get dynamically resized when the load factor becomes too big.

And as I wouldn't expect anything too complicated be built for war3's engine (considering it was N-years-old when hashtables came out), I'd say their implementation is something along these lines.

In short - they (ht) should allocate one (two, three) arrays' space and then extend only by amount proportional to the elements you put inside. Memory outage (i.e. crash) has happened even to an old server machine of ours w/ 6gb RAM while playing War3 with way too much background programs and disabled swapfile.

 

[Bribe]

Hashtables hold 2 ^ 32 values. Integers in JASS, last I read, range from - 2 ^ 31 to 2 ^ 31.

If you need to save a ton of values in hashtables and never deallocate them, you have got to be out of your mind. I built a form of time-machine in JASS using hashtable to simulate a 3-D array, but I also have it erase data older than, say, 20 seconds.

[ljass]call RemoveSavedReal(hashtable, integer, integer)[/ljass]
[ljass]call FlushChildHashtable(hashtable, integer)[/ljass]

 

[Tar-Quaeron]

Yeah, ok, I see. So it's really important, to save memory usage, to call RemoveSavedReal/RemoveSavedHandle/FlushTable after use, else the hashing function will have to call another function which reallocates the data to another index, so as to avoid collision.

@Bribe, in the jass manual, section types it says integers range from -2.147 * 10^9 to 2.147 * 10^9. Float, i.e. real is something like 10^31.

Thx for your answers.

 

[Bribe]

Well, rawcodes produce numbers in the trillions, so you know integers have a huge capacity.

 

[Lyerae]

Integers (in C) are actually rather small, but unsigned integers / (unsigned) longs are pretty big (in terms of the max value), if I remember correctly.

 

[Bribe]

I like that Python 3.0 treats integers and longs the same.

 

[Lyerae]

It's too early to be using 3.0, at least in production environments.