Hashtable Maximum?

[Somebassoon]

So I've been thinking about creating a hashtable which I'd use to save all of a units stats (which cannnot directly be gotten) at game start so I can get them later, however I thought about organizing them a little better and essentially using larger numbers in the hashtables

TLDR is there any difference between saving something in a hashtable as 10000 of temp_integer, compared to saving it as 10 of temp_integer?

 

[DracoL1ch]

nothing special you should be aware of

 

[Chaosy]

Speed is the difference. The more you store in a hashtable the slower it becomes.
Or so I've read at least.

 

[Dr Super Good]

TLDR is there any difference between saving something in a hashtable as 10000 of temp_integer, compared to saving it as 10 of temp_integer?

There is a marginal performance increase due to reduction in collisions in the underlying bucket arrays. If the bucket array size was either dynamic or customizable this would not be a problem (feature request?).

Do note there is a maximum hashtable limit of 256 (or was it 255?). Hashtables also cannot be fully destroyed once created so dynamic hashtable creation must be implemented carefully so as to not run into the limit.

 

[WereElf]

Yet if you want to have more than 255 hashtable, you could use some system like this:

library TableSpecial

  globals
  private hashtable T1 = InitHashtable()
  private hashtable T2 = InitHashtable()
  private constant string EMPTY = ""
  endglobals

  function CreateTableSpecial takes integer k1, integer k2 returns nothing
  local integer i = LoadInteger(T2, 0, 1)
  local integer c
  if k1 >= 0 and not HaveSavedInteger(T2, k1 + 1, k2) then
  if i == 0 then
  set i = LoadInteger(T2, 0, 0)
  call SaveInteger(T2, k1 + 1, k2, i)
  call SaveInteger(T2, 0, 0, i + 1)
  else
  set c = LoadInteger(T2, 0, i + 1)
  call RemoveSavedInteger(T2, 0, i + 1)
  call SaveInteger(T2, 0, 1, i - 1)
  call SaveInteger(T2, k1 + 1, k2, c)
  endif
  endif
  endfunction

  function DestroyTableSpecial takes integer k1, integer k2 returns nothing
  local integer i = LoadInteger(T2, 0, 1) + 1
  local integer c = LoadInteger(T2, k1 + 1, k2)
  if k1 >= 0 and HaveSavedInteger(T2, k1 + 1, k2) then
  call RemoveSavedInteger(T2, k1 + 1, k2)
  call FlushChildHashtable(T1, c)
  call SaveInteger(T2, 0, i + 1, c)
  set c = LoadInteger(T2, 0, 0)
  if c == i then
  call FlushChildHashtable(T2, 0)
  else
  call SaveInteger(T2, 0, 1, i)
  endif
  endif
  endfunction
  
  function FlushChildHashtableSpecial takes integer k1, integer k2 returns nothing
  local integer k4
  if HaveSavedInteger(T2, k1 + 1, k2) then
  set k4 = LoadInteger(T2, k1 + 1, k2)
  call FlushChildHashtable(T1, k4)
  endif
  endfunction

//! textmacro HasSavedNRemoveSaved takes NAME
  function HaveSaved$NAME$Special takes integer k1, integer k2, integer k3 returns boolean
  local integer k4
  if HaveSavedInteger(T2, k1 + 1, k2) then
  set k4 = LoadInteger(T2, k1 + 1, k2)
  return HaveSaved$NAME$(T1, k4, k3)
  endif
  return false
  endfunction

  function RemoveSaved$NAME$Special takes integer k1, integer k2, integer k3 returns nothing
  local integer k4
  if HaveSavedInteger(T2, k1 + 1, k2) then
  set k4 = LoadInteger(T2, k1 + 1, k2)
  call RemoveSaved$NAME$(T1, k4, k3)
  endif
  endfunction
//! endtextmacro

//! runtextmacro HasSavedNRemoveSaved("Integer")
//! runtextmacro HasSavedNRemoveSaved("Real")
//! runtextmacro HasSavedNRemoveSaved("Handle")
//! runtextmacro HasSavedNRemoveSaved("Boolean")
//! runtextmacro HasSavedNRemoveSaved("String")

//! textmacro SaveNLoad takes NAME, TYPE, HANDLE, VAL
  function Save$NAME$$HANDLE$Special takes integer k1, integer k2, integer k3, $TYPE$ val returns nothing
  local integer k4
  if HaveSavedInteger(T2, k1 + 1, k2) then
  set k4 = LoadInteger(T2, k1 + 1, k2)
  call Save$NAME$$HANDLE$(T1, k4, k3, val)
  endif
  endfunction
  
  function Load$NAME$$HANDLE$Special takes integer k1, integer k2, integer k3 returns $TYPE$
      local integer k4
      if HaveSavedInteger(T2, k1 + 1, k2) then
          set k4 = LoadInteger(T2, k1 + 1, k2)
          return Load$NAME$$HANDLE$(T1, k4, k3)
      endif
      return $VAL$
  endfunction
//! endtextmacro

//! runtextmacro SaveNLoad("Boolean","boolean","","false")
//! runtextmacro SaveNLoad("Str","string","","EMPTY")
//! runtextmacro SaveNLoad("Real","real","","0.00")
//! runtextmacro SaveNLoad("Integer","integer","","0")
//! runtextmacro SaveNLoad("Player","player","Handle","null")
//! runtextmacro SaveNLoad("Widget","widget","Handle","null")
//! runtextmacro SaveNLoad("Destructable","destructable","Handle","null")
//! runtextmacro SaveNLoad("Item","item","Handle","null")
//! runtextmacro SaveNLoad("Unit","unit","Handle","null")
//! runtextmacro SaveNLoad("Ability","ability","Handle","null")
//! runtextmacro SaveNLoad("Timer","timer","Handle","null")
//! runtextmacro SaveNLoad("Trigger","trigger","Handle","null")
//! runtextmacro SaveNLoad("TriggerCondition","triggercondition","Handle","null")
//! runtextmacro SaveNLoad("TriggerAction","triggeraction","Handle","null")
//! runtextmacro SaveNLoad("TriggerEvent","event","Handle","null")
//! runtextmacro SaveNLoad("Force","force","Handle","null")
//! runtextmacro SaveNLoad("Group","group","Handle","null")
//! runtextmacro SaveNLoad("Location","location","Handle","null")
//! runtextmacro SaveNLoad("Rect","rect","Handle","null")
//! runtextmacro SaveNLoad("BooleanExpr","boolexpr","Handle","null")
//! runtextmacro SaveNLoad("Sound","sound","Handle","null")
//! runtextmacro SaveNLoad("Effect","effect","Handle","null")
//! runtextmacro SaveNLoad("UnitPool","unitpool","Handle","null")
//! runtextmacro SaveNLoad("ItemPool","itempool","Handle","null")
//! runtextmacro SaveNLoad("Quest","quest","Handle","null")
//! runtextmacro SaveNLoad("QuestItem","questitem","Handle","null")
//! runtextmacro SaveNLoad("DefeatCondition","defeatcondition","Handle","null")
//! runtextmacro SaveNLoad("TimerDialog","timerdialog","Handle","null")
//! runtextmacro SaveNLoad("Leaderboard","leaderboard","Handle","null")
//! runtextmacro SaveNLoad("Multiboard","multiboard","Handle","null")
//! runtextmacro SaveNLoad("MultiboardItem","multiboarditem","Handle","null")
//! runtextmacro SaveNLoad("Trackable","trackable","Handle","null")
//! runtextmacro SaveNLoad("Dialog","dialog","Handle","null")
//! runtextmacro SaveNLoad("Button","button","Handle","null")
//! runtextmacro SaveNLoad("TextTag","texttag","Handle","null")
//! runtextmacro SaveNLoad("Lightning","lightning","Handle","null")
//! runtextmacro SaveNLoad("Image","image","Handle","null")
//! runtextmacro SaveNLoad("Ubersplat","ubersplat","Handle","null")
//! runtextmacro SaveNLoad("Region","region","Handle","null")
//! runtextmacro SaveNLoad("FogState","fogstate","Handle","null")
//! runtextmacro SaveNLoad("FogModifier","fogmodifier","Handle","null")
//! runtextmacro SaveNLoad("Hashtable","hashtable","Handle","null")

endlibrary

This system uses 2 hashtables to simulate a hashtable with 3 keys. You could use the 1-st key as "hashtable 1, 2, 3... etc" and use the other 2 keys the normal way.

And as for your question - nope it doesn't matter if you save stuff into 10-th key or into the 10000000-th key

 

[Rui]

Wow, hashtable has a 256 maximum? Really? I knew it had a limit, but I always assumed it was much larger.

Hashtables also cannot be fully destroyed once created

Waat how so

 

[Chaosy]

I think it's 255.
But even so, you probably wont use that many of them.

 

[KILLCIDE]

Do note there is a maximum hashtable limit of 256 (or was it 255?).

I think it's 255.

The hashtable maximum is 255. To be frank, if your map is even coming close to that number, you are definitely doing something wrong.

 

[Rui]

Okay, but what about hashtables not being fully destroyable?

 

[DracoL1ch]

why would you need to destroy it? since index key limit is 2^31 you can use it as virutally endless array without any fears.

 

[PurgeandFire]

Okay, but what about hashtables not being fully destroyable?

You can destroy them with FlushParentHashtable.

But as Draco said, most maps really don't have to worry about it.

 

[Dr Super Good]

Okay, but what about hashtables not being fully destroyable?

Once one is created, it cannot be destroyed in a way which frees it from the global hashtable limit. This means that creating a new Hashtable will work exactly 255 (or 256, depending on bounds) times before it returns null or something invalid.

You can destroy them withFlushParentHashtable.

This should just return it to initial state, not destroy it. This difference is important because dynamically created hashtables might be used to combat hashtable scaling problems in some data management structures.

 

[DracoL1ch]

This should just return it to initial state, not destroy it. This difference is important because dynamically created hashtables might be used to combat hashtable scaling problems in some data management structures.

as somebody told me before, if you gonna use local hashtables, you have big problems with programming in JASS as is

 

[PurgeandFire]

@Dr Super Good Are you sure about that? iirc if you call FlushParentHashtable, you can continually create more and more hashtables. You just can't have 256 simulatenous hashtables.

As we all know by now, what we think things "should" do and what they actually do don't always match.

 

[WereElf]

After using FlushParentHashtable - the hashtable becomes unusable, so you need to create a new one. I had some weird bug until I found that out
Anyways... you could easily check if you can't have more than 255(6) hashtables in total OR only simulatenous by doing:

local integer i = 0
loop
    exitwhen i > 300
    set udg_Table = InitHashtable()
    call FlushParentHashtable(udg_Table)
    set i = i + 1
endloop
set udg_Table = InitHashtable()
call SaveInteger(udg_Table, 0, 0, 14)
call BJDebugMsg(I2S(LoadInteger(udg_Table, 0, 0)))

 

[Wietlol]

why would you need to destroy it? since index key limit is 2^31 you can use it as virutally endless array without any fears.

You mean 2^32^2 integers, 2^32^2 reals, 2^32^2 strings, 2^32^2 booleans and 2^32^2 handles per hashtable.
One is enough (unless you want to use the same keys over and over again).

 

[DracoL1ch]

You mean 2^32^2 integers, 2^32^2 reals, 2^32^2 strings, 2^32^2 booleans and 2^32^2 handles per hashtable.
One is enough (unless you want to use the same keys over and over again).

key is signed and yet restricted by normal limits of 0x7FFFFFFF

 

[Wietlol]

Not according to my tests.

 

[DracoL1ch]

hows that? you sure that values stroed in keys bigger than 2^31-1 weren't synonym for negative modulo?

 

[Wietlol]

I am sure that 2^-31 and 2^31-1 worked fine.

 

[Deleted member 219079]

You can use negative indexes

 

[Rui]

Okay, my bad, I misunderstood. I thought we were saying there was a maximum of 256 entries per hashtable.

There's a maximum of 255 hashtables and 2^-31 to 2^31 possible indexes/entries (wish I had known earlier that negative indexes worked too q-q).

 

[WaterKnight]

concerning destruction: If it's not allowed to destroy them/it does not become free for another hashtable, just clear it and put it in some allocation recycler.

It can make sense to use a lot of hashtables. For example to divide the strain.

Even if a hashtable can store 2^32^2 entries per type, it does not mean that one hashtable can/should cover all tasks. For example imagine you want to save a 3d field, mapping values to R^3. While you may not have the need to assign all the values, the domain of definition is prone to explode.

 

[Wietlol]

"For example to divide the strain."

Can we kill the guy who invented Table?

 

[Dr Super Good]

If one could declare the size of bucket array for a hashtable then there would be less of a need to "divide the strain".