Tell me the secret of hash!

[Pinzu]

Can someone please teach me how to use hashtables? I try getting it from tutorials but it just wont come through :<

Currently I have a setup like this:

    set x[i] = GetRectCenterX(gg_rct_House_GC_00)
    set y[i] = GetRectCenterY(gg_rct_House_GC_00)
    set gateT[i] = 'LTe2'
    set gateSize[i] = 0.8
    set gateFace[i] = 0
    set gateLock[i] = TRUE
    set i = i + 1
    set x[i] = GetRectCenterX(gg_rct_House_GC_01)
    set y[i] = GetRectCenterY(gg_rct_House_GC_01)
    set gateT[i] = 'LTe2'
    set gateSize[i] = 0.8
    set gateFace[i] = 180
    set gateLock[i] = TRUE
    set i = i + 1
    // e.t.c. ...

But to get these later I have to loop through all of the say 150 gates each time someone cast a spell ON them, so how would I set this up differntly?

How do I store them in HASH, and how do I get which gate is being targeted without looping trough 150 gates?

 

[Doomlord]

Hashtables are for storing handles, imagine them as a locker hall with each locker identified by 2 value: parent Key and child Key. Your problem doesn't seem to relate to hashtables as all

It would be great if you could elaborate a bit more on your Gate thing so that people may help you.

 

[defskull]

Here's a test map.

 

[Dr Super Good]

A hash is a small identifier (a number) that is used to simplify certain collection operations on complex data structures. The same state of a complex data structure will always produce the same hash when passed to the same hash-algorithm. Hashes are not unique, many states of the complex data structure can produce the same hash. This also means that hashing algorithms are one way, you cannot know the exact state of complex data structure that produced them. The best hashing algorithms produce numbers which have little correlation to their input.

Hashes are useful because they represent what is contained inside a complex data structure and are very small (usually a word for optimum performance). You can test complex data structures for equality by comparing their hashes and only performing absolute equality checks if the hashes match. The lack of correlation of hashes also makes them useful for distributing the complex data structure in a fair way.

Hashtables use hashes to generate an array index to store data at (data not related to the complex data structure that produced the hash). Since the same hash is generated from the same state of complex data structure (usually with linear efficiency based on structure size) you can use this to very efficiently recall the data as very few entries need to be compared. If the hashtable array is large enough you will obtain a complexity of near O(1) for searches (unrelated to the number of elements stored in the hashtable). This is in contrast to linear search (what you are using) that has a complexity related to O(n) so increases complexity linearly with the number of elements stored.

A complex data structure in this meaning is a collection of related data that can be very large in size. A string is a complex data structure as you can have strings of many hundred characters. A C struct is also a complex data structure as there is no limit to how many members it can have defined.

Hashtables do not require hashes. They need data that is represent able as a number. For efficiency that number should result in an index with almost equal probability distribution. This means that nothing stops you using a hashtable as an array, just it might not perform well if done so depending on implementation details.

WarCraft III hashtables follow these principiles but in a strange way. They use to use 2 integers to uniquly identify an item instead of taking a complex data structure and hashing algorthim as proper hashtables should do. The result is they behave exactly like a 2D array where indicies for all integer values are defined. They do not behave properly with hashes made from strings as the nature of hashes means multiple strings produce the same hash which results in a collision.

What is good with them is that you can use the handle id of a handle (from GetHandleId function) as an index. As this value is constant during the life of a handle (eg the same unit will return the same value) it is perfectly suitable as a hashtable mapping. You can thus use hashtables to map a value to a handle.

In your case what you want to do is assign each door a unique array index. This array index is used to store and access data associated with the door from parallel arrays (what you do now). You store this unique index to the door (the door's handle id) using a hashtable (second integer index should be unique but does not matter).

When your ability is cast on the door, you can get the target (what door it is cast on). You then use its handle id in the hashtable to get its corresponding array index. You can then directly access all associated data elements. This removes any need for looping.

 

[Pinzu]

Okey, this is what I made, gonna test it and see what happens...

Atemt

globals
         hashtable  gateHash
           integer  gateKey      
           integer  gateId
           
       force array  gateControler
      player array  gateOwner
      destructable  gateDest
destructable array  gateBloc
        real array  gateFace
        real array  gateSize
     boolean array  gateLock
endglobals

function SaveGateEncapsulation takes nothing returns nothing
    set gateKey = GetHandleId(gateDest)
    call SaveStringBJ(I2S(gateId), 0, gateKey, gateHash) 
    set gateId = gateId + 1
endfunction

function SetupGates takes nothing returns nothing
// Human Gate: LTg1, Elven Gate: LTe2, Gate Blocker: B000,
  local destructable d
  local real array y
  local real array x
  local integer array gateT
  local integer i = 0
  local integer a = 0
  
    // Home Gates
    set x[i] = GetRectCenterX(gg_rct_House_GC_00)
    set y[i] = GetRectCenterY(gg_rct_House_GC_00)
    set gateT[i] = 'LTe2'
    set gateSize[i] = 0.8
    set gateFace[i] = 0
    set gateLock[i] = TRUE
    set i = i + 1
    set x[i] = GetRectCenterX(gg_rct_House_GC_01)
    set y[i] = GetRectCenterY(gg_rct_House_GC_01)
    set gateT[i] = 'LTe2'
    set gateSize[i] = 0.8
    set gateFace[i] = 180
    set gateLock[i] = TRUE
    set i = i + 1
    set x[i] = GetRectCenterX(gg_rct_House_GC_02)
    set y[i] = GetRectCenterY(gg_rct_House_GC_02)
    set gateT[i] = 'LTe2'
    set gateSize[i] = 0.8
    set gateFace[i] = 90
    set gateLock[i] = TRUE
    set i = i + 1
    set x[i] = GetRectCenterX(gg_rct_House_GC_03)
    set y[i] = GetRectCenterY(gg_rct_House_GC_03)
    set gateT[i] = 'LTe2'
    set gateSize[i] = 0.8
    set gateFace[i] = 90
    set gateLock[i] = TRUE
    set i = i + 1
    set x[i] = GetRectCenterX(gg_rct_House_GC_04)
    set y[i] = GetRectCenterY(gg_rct_House_GC_04)
    set gateT[i] = 'LTe2'
    set gateSize[i] = 0.8
    set gateFace[i] = 180
    set gateLock[i] = TRUE
    set i = i + 1
    set x[i] = GetRectCenterX(gg_rct_House_GC_05)
    set y[i] = GetRectCenterY(gg_rct_House_GC_05)
    set gateT[i] = 'LTe2'
    set gateSize[i] = 0.8
    set gateFace[i] = 90
    set gateLock[i] = TRUE
    set i = i + 1
    
    loop
      set gateControler[a] = CreateForce()
      set gateDest = CreateDestructable(gateT[a],x[a],y[a],gateFace[a],gateSize[a],1)
      call SaveGateEncapsulation()
      set d = CreateDestructable('B000',x[a],y[a],gateFace[a],1.0,1)
      set a = a + 1
    exitwhen gateT[a] == null
    endloop
    set d = null
endfunction

 

[gorillabull]

yea but you dont need to use hashtables for this, i think a simpler way to index destructables is to set their life or occulder height rather than saving thier handle then: when you cast the spell you can call

GetDestructableLife

or

 GetDestructableOccluderHeight

and that is going to return an index, indexing them is also easy just set their value to some variable when you create them and then set that variable + 1

 

[defskull]

@Pinzu
Have, uhhh, like test the test map I gave you on post #3 ?

If you have, try to understand the trigger, if you don't understand it even a little bit, just ask questions.

 

[Pinzu]

Edited my post, tired so posted too soon

yea but you dont need to use hashtables for this, i think a simpler way to index destructables is to set their life or occulder height rather than saving thier handle then: when you cast the spell you can call

GetDestructableLife

or

 GetDestructableOccluderHeight

and that is going to return an index, indexing them is also easy just set their value to some variable when you create them and then set that variable + 1

Looks interesting what does "occluderHeight" even do?

Changed your test map to a id instead, but it only returns world edit sadly

• Setup 2
  • Events
    • Map initialization
  • Conditions
  • Actions
    • Custom script: set udg_SG_Hashtable = InitHashtable()
    • -------- ////////// --------
    • -------- GATE A --------
    • Set SG_Gate = Demonic Gate (Horizontal) 0000 <gen>
    • Set SG_GateName = ¨0
    • Set player[0] = Player 1 (Red)
    • Trigger - Run Save <gen> (ignoring conditions)
    • -------- ////////// --------
    • -------- GATE B --------
    • Set SG_Gate = Demonic Gate (Horizontal) 0002 <gen>
    • Set SG_GateName = 1
    • Set player[1] = Player 2 (Blue)
    • Trigger - Run Save <gen> (ignoring conditions)
    • -------- ////////// --------
    • -------- GATE C --------
    • Set SG_Gate = Demonic Gate (Horizontal) 0004 <gen>
    • Set SG_GateName = 2
    • Set player[2] = Player 3 (Teal)
    • Trigger - Run Save <gen> (ignoring conditions)
    • -------- ////////// --------
    • -------- GATE D --------
    • Set SG_Gate = Demonic Gate (Horizontal) 0001 <gen>
    • Set SG_GateName = 3
    • Set player[3] = Player 4 (Purple)
    • Trigger - Run Save <gen> (ignoring conditions)
    • -------- ////////// --------
    • -------- GATE E --------
    • Set SG_Gate = Demonic Gate (Horizontal) 0003 <gen>
    • Set SG_GateName = 4
    • Set player[4] = Player 5 (Yellow)
    • Trigger - Run Save <gen> (ignoring conditions)
    • -------- ////////// --------
    • -------- GATE F --------
    • Set SG_Gate = Demonic Gate (Horizontal) 0005 <gen>
    • Set SG_GateName = 5
    • Set player[5] = Player 6 (Orange)
    • Trigger - Run Save <gen> (ignoring conditions)

• Save
  • Events
  • Conditions
  • Actions
    • Custom script: set udg_SG_Key = GetHandleId(udg_SG_Gate)
    • Hashtable - Save SG_GateName as 0 of SG_Key in SG_Hashtable

• SG Eventtest
  • Events
    • Unit - A unit Starts the effect of an ability
  • Conditions
    • (Ability being cast) Equal to (==) Channel
  • Actions
    • Custom script: set udg_SG_Key = GetHandleId(GetSpellTargetDestructable())
    • Game - Display to (All players) the text: (My name is: + (Load 0 of SG_Key from SG_Hashtable))
    • Game - Display to (All players) the text: (Name of player[(Integer((Load 0 of SG_Key from (Last created hashtable))))])

*edit also you didnt use handle which probably is that id im looking for.

I'm really greatful for all your help! You guys bring a tear drop to my eye.

*Edit 2 ups I used LastCreatedHashtable. Works!

 

[Cokemonkey11]

There's a description here - http://www.hiveworkshop.com/forums/world-editor-help-zone-98/occlusion-height-what-118957/

But generally occluder height is not important in wc3 maps, and in those cases you can use it to store data in the object.

To use hashtables, I think it's important that you understand how they work internally. Take a look at this if you have any spare time -

http://www.inf.ed.ac.uk/teaching/courses/inf2b/algnotes/slides-full04.pdf

 

[Pinzu]

There's a description here - http://www.hiveworkshop.com/forums/world-editor-help-zone-98/occlusion-height-what-118957/

But generally occluder height is not important in wc3 maps, and in those cases you can use it to store data in the object.

To use hashtables, I think it's important that you understand how they work internally. Take a look at this if you have any spare time -

http://www.inf.ed.ac.uk/teaching/courses/inf2b/algnotes/slides-full04.pdf

Haha lots of sparetime. . . Ty for link will deffinitly smash my head against it.

 

[defskull]

Hashtable consists of 2D array.
We have parentKey and childKey.

Now what I did there, is I saved 3 values to a single parentKey.
[0][0] = Name
[0][1] = Hobby
[0][2] = Blood

Notice anything that don't change ?
Yes, the [0] on the left side doesn't change, this means it is a parentKey.
If I change it...

[1][0] = Name
[1][1] = Hobby
[1][2] = Blood

What does this means ?
It means, I have changed my Handle ID to a new object.

It is actually;
[parentKey][childKey]

set udg_parentKey = GetHandleId(GetTriggerUnit())

Now that you have its parentKey, you can access its childKey;
set udg_i = LoadInteger(udg_SG_Hashtable, parentKey, childKey)

You can either set your childKey to be in a string value, or integer value, but mostly, people use integer, because it's faster.

 

[Chaosy]

Think of it as a locked box with a code to open it.
so you set a code and place somethuing within it. That is basicly how it works.

 

[Maker]

Yes, the [0] on the left side doesn't change, this means it is a parentKey.

It is still the parent key in jass syntax, regardless if it changes or not

It means, I have changed my Handle ID to a new object.

Keys aren't necessarily handle ids.

Now that you have its parentKey, you can access its childKey;

You access the data that is stored by using parent- and child key, you don't "access its childKey".

You can either set your childKey to be in a string value, or integer value, but mostly, people use integer, because it's faster.

Keys are always integers.

What you propably mean is one can hash a string, convert it into an integer with StringHash