[JASS] Hash tables, collision detection

[Element of Water]

I'm making an item stacking system using hash tables, and I've got everything working except for the hash table collision detection. My formula is ITEM_ID%(modulus)8192. Can anyone tell me how I make it so, if I have one item which has an idea of, say, 300, how I can make it not overwrite an item in my hash table with an id of, say 8492? How do I go about this? I really have no idea...

 

[LeP]

Hash table - Wikipedia, the free encyclopedia

I use linked lists (chaining (not direct, but simmilar)) in my system but i think linear probing is also good in wc3.
e.g.

i=hash(id)
loop
exitwhen ids[i]==0 //or datas[i]==0
    set i=i+1
   //this is kinda unsafe, so check if i>8190 and then start from 0 or return
endloop
set ids[i]=id
set datas[i]=data

 

[Element of Water]

Ah so I need another variable, and when I'm getting the data back out of the array I just check if my id equals the stored id at that index and if it doesn't increase the index?
Thanks, +rep to you.

 

[Captain Griffen]

Hash tables where you never remove them and/or add them all at the start are piss; just modulus and then check until you find the correct id in a checking array/an empty one.

More tricky if you add and remove dynamically.

 

[Element of Water]

Well I don't think I do need to add/remove dynamically for my system, so I'm fine.

 

[Dr Super Good]

Generally for dynamic support, when you remove something from a hash you have to put in its place an "empty but used" kind of thing. Which means that stuff may exist after that index so it has to check but when asigning a new value, it can be treated as empty.

This is atleast what blizzard did with their MPQs.

Basically for collisions, you just have to use a neighboring index. For efficency use the target index + X until X gives a free index. The system will come to a crawl (slowdown) if you start using too many items (too many hash collisions). The system will completly fail if it passes the 8192 limate when trying to add something unless you have some kind of back up system which handles that problem.

 

[Element of Water]

Just a small question:
This linear method I'm using at the moment, suggested by LeP, has to loop through the whole 8192 slots if there isn't a stored value for the item index in question. This means when you pick up an item my system doesn't have to stack up, the whole function takes nearly as long, if not longer than it takes if the system does stack the item...

Is there any way around this? LeP mentioned linked lists - what are they?

 

[Captain Griffen]

Stop searching when you come to an empty index, or when you come to one where the id == that of the ability.

 

[Element of Water]

Oh yeah, good point. Sorry for being stupid :S.