jass实现HashMap，标题要长啊长啊长～～～～～～～～～

此为何处

（为什么我的jass没有高亮显示）
HasnMap 键值对应，用处不多说了远不止于替代缓存，这里实现的是handle键对应handle值，有其他需要的话自行修改代码。
由于使用数组存放数据，最大数量是有限制的，一般几千的数据量，但效率绝对能保证，平均搜索次数不会超过2次。
原则上HashMap初始化后不要自行修改里面的变量
这里提供了5个方法
hashMapInit ( integer l ,integer hl )
HashMap初始化，可以在地图初始化时调用此方法。参数： 0<hl<h<=8192
比如：hashMapInit ( 8000 ,6000) 此时 该HashMap最大可能的存储量为8000 ，至少能放下8000-6000=2000的数据（这种情况一般不会发生）。hl越接近l 参数搜索速度越快，一般达到50%速度变化不大了。
get(handle key)
根据 key 返回对应的的一个handle
put(handle key,handle value)
j将key和value存入HashMap,如果HashMap存放不下则返回false 否则true
remove(handle key)
根据 key 从HashMap中删除记录
removeAll( )
删除所有记录
附件中有个测试地图，该地图每0.05秒产生1个步兵，5秒后杀死，用hashMap关联Timer和Unit

代码：

[codes=jass]
globals
integer udg_HashMap_LENGTH
integer udg_HashMap_HEADLENGTH
integer array udg_HashMap_key
integer array udg_HashMap_value
integer array udg_HashMap_next
integer array udg_HashMap_previous
boolean array udg_HashMap_hasValue
endglobals
function hashMapInit takes integer len,integer headlen returns nothing
        local integer i=0
  
if len < 2 or len >8192 then
  set len=8192
endif
if headlen < 1 or headlen >= len then
  set headlen =len/2
endif
  
        set udg_HashMap_LENGTH = len
        set udg_HashMap_HEADLENGTH = headlen
        set udg_HashMap_index = HashMap_HEADLENGTH
loop
exitwhen i >= udg_HashMap_LENGTH
         set udg_HashMap_next = -1
                set udg_HashMap_previous = -1
  set i=i+1
endloop
set i=0
loop
exitwhen i >= udg_HashMap_LENGTH
         set udg_HashMap_hasValue =FALSE
  set i=i+1
endloop
endfunction
function I2H takes integer int returns handle
      return int
      return null
endfunction
function H2I takes handle han returns integer
      return han
      return 0
endfunction
function getHashCode takes integer key returns integer
        return ModuloInteger(key, udg_HashMap_HEADLENGTH)
endfunction
function get takes handle hkey returns handle  
        local integer key =H2I(hkey)
local integer hashCode = getHashCode(key)
local integer index=0
if (udg_HashMap_hasValue[hashCode]) then
  set index=hashCode
  loop
  exitwhen index<0
                exitwhen udg_HashMap_key[index]==key
   set index=udg_HashMap_next[index]
  endloop
  if (index<0) then
   return null
  endif
  return I2H(udg_HashMap_value[index])
endif
return null
endfunction
                     
function put takes handle hkey,handle hvalue returns boolean
        local integer key= H2I(hkey)
local integer hashCode=getHashCode(key)
local integer index=0
        local integer value=H2I(hvalue)
if (udg_HashMap_hasValue[hashCode]) then
  set index=hashCode
  loop
  exitwhen index<0
                exitwhen udg_HashMap_key[index]==key
   set index=udg_HashMap_next[index]
  endloop
  if (index<0) then
   if (udg_HashMap_index>=udg_HashMap_LENGTH) then
    return false
   endif
                        set udg_HashMap_previous[udg_HashMap_next[hashCode]]=udg_HashMap_index
   set udg_HashMap_key[udg_HashMap_index]=udg_HashMap_key[hashCode]
   set udg_HashMap_value[udg_HashMap_index]=udg_HashMap_value[hashCode]
   set udg_HashMap_next[udg_HashMap_index]=udg_HashMap_next[hashCode]
   set udg_HashMap_previous[udg_HashMap_index]=hashCode
   set udg_HashMap_key[hashCode]=key
   set udg_HashMap_value[hashCode]=value
   set udg_HashMap_next[hashCode]=udg_HashMap_index
   set udg_HashMap_index=udg_HashMap_index+1
   return true
  endif
  set udg_HashMap_value[index]=value
  return true
endif   
set udg_HashMap_key[hashCode]=key
set udg_HashMap_value[hashCode]=value
set udg_HashMap_hasValue[hashCode]=true
set udg_HashMap_next[hashCode]=-1
return true
endfunction
function remove takes handle hkey returns nothing
local integer key = H2I(hkey)
local integer hashCode = getHashCode(key)  
local integer index=0
local integer next=0
if (udg_HashMap_hasValue[hashCode]) then
  set index=hashCode
  loop
  exitwhen index<0
  exitwhen udg_HashMap_key[index]==key
   set index=udg_HashMap_next[index]
  endloop
  if (index<0) then
   return
  endif
  if (udg_HashMap_next[index]<0) then
   if (index < udg_HashMap_HEADLENGTH) then
       set udg_HashMap_hasValue[hashCode]=false
       return
   endif
   set udg_HashMap_index=udg_HashMap_index-1
   set udg_HashMap_next[udg_HashMap_previous[index]]=-1
   set udg_HashMap_value[index]=udg_HashMap_value[udg_HashMap_index]
   set udg_HashMap_key[index]=udg_HashMap_key[udg_HashMap_index]
   set udg_HashMap_next[index]=udg_HashMap_next[udg_HashMap_index]
   set udg_HashMap_previous[index]=udg_HashMap_previous[udg_HashMap_index]
   set udg_HashMap_next[udg_HashMap_index]=-1
   set udg_HashMap_previous[udg_HashMap_index]=-1

   if (udg_HashMap_previous[index]>=0) then
    set udg_HashMap_next[udg_HashMap_previous[index]]=index
   endif     
  else
   
   set next=udg_HashMap_next[index]
   set udg_HashMap_value[index]=udg_HashMap_value[next]
   set udg_HashMap_key[index]=udg_HashMap_key[next]
   set udg_HashMap_previous[index]=udg_HashMap_previous[next]
   set udg_HashMap_next[index]=udg_HashMap_next[next]
   set udg_HashMap_index=udg_HashMap_index-1
   set udg_HashMap_value[next]=udg_HashMap_value[udg_HashMap_index]
   set udg_HashMap_key[next]=udg_HashMap_key[udg_HashMap_index]
   set udg_HashMap_next[next]=udg_HashMap_next[udg_HashMap_index]
   set udg_HashMap_previous[next]=udg_HashMap_previous[udg_HashMap_index]
   set udg_HashMap_next[udg_HashMap_index]=-1
   set udg_HashMap_previous[udg_HashMap_index]=-1
   if (udg_HashMap_previous[next]>=0) then
    set udg_HashMap_next[udg_HashMap_previous[next]]=next
   endif
  endif
endif   
  
endfunction
function removeAll takes nothing returns nothing
    local integer i=0
    loop
    exitwhen i >= udg_HashMap_HEADLENGTH
set udg_HashMap_hasValue=false
    set i=i+1
    endloop
endfunction

[/codes]

凌神の君

好像有人发过类似的
附件名是hasnmap=,=

此为何处

写之前论坛搜了下没hashmap这关键字
那个附件里的h估计刚剃了个头

cccty1l

你搜 Hash 吧，我有三个演示，其中钩肥昨天刚更新了下。

此为何处

hash不等于hashmap
hashmap首先是个map
发前我看过你的利用hash存储的东西，不完善

cccty1l

愿闻其详

此为何处

其实你的完成了一半，搜索很重要的一部分确实也是Hash。
我这边的散列很简单，直接取余。但不管我们怎么hash，我们存储的数组下标是13位的也就是8192，而integet是32位的，怎么hash都是将一个大范围的散列成小范围的，必然导致，有2个不同的integer   散列成2个相同的hashCode。
我看过你的代码，这种情况你直接返回一个失败，不做处理。假如直接用这个来做hashMap那么，很有可能碰到这种情况，你往map里面放东西，才放了一条他就返回一个false说不能放了。

cccty1l

[codes=jass]globals
integer I
handle H
integer array hashi
endglobals
function hash takes integer I,handle H,boolean b returns integer
local integer ha=I-I/8191*8191
local integer hb=I-I/8179*8179+1
local integer n=0
local integer val
if(b)then
      set val=0
else
      set val=I
endif
loop
      exitwhen(hashi[ha]==val)or(n>499)
      set ha=ha+hb
      set n=n+1
      if(ha>=8191)then
            set ha=ha-8191
      endif
endloop
if(n>499)then
      return -1
else
      if(b)then
            set hashi[ha]=I
      endif
endif
return ha
endfunction[/codes]

我不清楚你看到了那个，现在就上面这个例子来说。Hash到一个相同的地址在所难免，但是上面的代码中会将第一次得到的值再次加hb来获取下一个地址。你也知道Hash表的效率，我把它限制在了循环500次，在这个范围内一般是可以查询到一个存储地址的吧。

而且它还有一个好处是函数很简单，你可以在地图中使用很多这个函数，分别存储不同类型的数据，没多一个数组，就会多出很多存储空间的。

此为何处

好吧，我没仔细看，我承认我画蛇添足了
纯hash就可以了，被占了继续寻址。我还加了个链表。
不过要封装成一个Map,类型只能固定了

zhuzeitou

hashmap，hmmm………………
我数据结构米有学好~~

代码高亮的话，[codes]改成[codes=jass]吧

cccty1l

嗯，单单就链表来说也可以做一个系统的，前几天 冰块 的一个帖子里面讨论了关于计时器的数组存储系统，利用了计时器创建的时候handle是连续的这一特点做了个系统。我修改了下，保证了高效率和修正了潜在的一些Bug，使用了链表的原理。
[codes=jass]globals
integer I
integer Tm
integer Timer_F
integer array Timer_Data
integer Timer_maxN=-1
endglobals
//! define Timer_N 511
function Timer_get takes nothing returns integer
if(Timer_maxN<Timer_N)then
    set Timer_maxN=Timer_maxN+1
    return Timer_Data[Timer_maxN]
else
    return -1
endif
endfunction

//! define Timer_id(t) Timer_getid(0,t)
function Timer_getid takes integer I,timer Tm returns integer
return I-Timer_F
endfunction

function Timer_des takes integer id returns nothing
local timer Tm
local integer I=Timer_F+id
call PauseTimer(Tm)
set Timer_Data[Timer_maxN]=id
if Timer_maxN>=0 then
    set Timer_maxN=Timer_maxN-1
endif
set I=0
endfunction

function Timer_cre takes nothing returns nothing
local timer array t
local integer n=1
local integer bugs=-1
local integer id
local integer I
local timer Tm=CreateTimer()
local integer fid=I
loop
    set Tm=CreateTimer()
    set id=I-fid
    if(id>0 and id<8191)then
        set Timer_Data[n]=id
        set n=n+1
    else
        set bugs=bugs+1
        set t[bugs]=Tm
    endif
    exitwhen n>=Timer_N
endloop
loop
    exitwhen bugs<=-1
    call DestoryTimer(t[bugs])
    set t[bugs]=null
    set bugs=bugs-1
endloop
set Timer_F=fid
set I=0
endfunction[/codes]

hunluan89

额  我记得数组内存地址都是连续的吧 这个不就是跟动态结构最大的不同之一吗 暴雪怕不够用所以限定死了 8192不是吗 我是这样认为的

刚说错了不是下标

kook

引用第10楼cccty1l于2009-01-15 16:43发表的  :
嗯，单单就链表来说也可以做一个系统的，前几天 冰块 的一个帖子里面讨论了关于计时器的数组存储系统，利用了计时器创建的时候handle是连续的这一特点做了个系统。我修改了下，保证了高效率和修正了潜在的一些Bug，使用了链表的原理。
[codes=jass]globals
integer I
integer Tm
integer Timer_F
.......

这不是某人抛弃的data system么。。

cccty1l

啊，已经被抛弃了么？&#160; 我只是在前几天在冰块那个帖子里面才知道的。。。

为什么抛弃呢？我看不错啊。

嗯，不过不管怎么说，这个系统虽然快捷，但是比起Hash来还是很有局限性的，只是可惜貌似actboy168没有要推广它的意向。

cccty1l

嗯，我搜索了下，是画中人的http://www.islga.org/bbs/read.php?tid=8439《我的个人函数集》，发表于2007-11-29。

2L有DataSystem，其中library TimerSys应该就是Kook大所说的东西了。
原理就是利用顺次生成的点的Handle值是连续的这一特性，画中人的演示中，生成点然后删除之，因为记录该点的变量没有set null，所以Handle值得以保留，同时，用以记录该Handle值的数组的下脚标等于Handle值减去head的大小。

接下来，在需要一个计时器的时候，先分配一个下脚标（这个下脚标的分配只需一步，也就是用了链表），然后将对应的数组set null，空出了handle值，然后生成计时器，这样计时器的handle与刚才的释放的handle是相同的。在之后的动作中获取到计时器后，用计时器的handle减去head，就得到了它对应的下脚标，也就是得到了它绑定的数据。

再下来，计时器不在需要的时候，销毁它，依然不将保存它的数组set null，也就是继续留下了这个handle值，以后会回到第二步。

画中人的TriggerSys也是同样的道理。嗯，当然，应该说是基本上是这个道理，大家可以点上面的链接复习下，看看我说的对不对。

确实很强大，不知道为什么抛弃掉了。嗯，我现在也有几个问题想问一下。
第一，连续产生的Location是否其handle值一定是连续的（当然，是在地图刚刚开始的时候创建的）？
第二，因为数组指向了点的地址，那么在删除点以后没有set null是否节省了资源，内存占用是否可以减少呢？或者在一开始就创建计时器又如何呢？
第三，能否一定保证在将数组set null之后紧接着创建的计时器的handle值就一定是刚才保留的handle值呢？
第四，这个方法画中人只用于了计时器与函数，那么它是否有更多的范围？

嗯，再膜拜下画中人，呵呵。

kook

之所以抛弃是因为跑去玩dota了..

amp34

事实上，好像以前测试的时候，WC3理论上触发器的执行是按队列形式顺序执行的。
但是还是会在某些情况下遇到“线程不同步”的问题。虽然WC3是灭有“线程”的，但是执行的过程中会出现这样的情况。
而且JASS不提供所谓的“锁”来对这些东西进行处理。所以看似完美的实现。会在实际运用中出现莫明奇妙的问题。
这就素那堆东西真正被抛弃的原因。嗯嗯。

cccty1l

嗯，早上我做了下试验。下面的东西都是玩家摁Esc触发。每次间隔大概一秒。
一
[codes=jass]function aaa takes nothing returns boolean
local timer array h
local integer n=0
loop
    set h[n]=CreateTimer()
    call DestroyTimer(h[n])
    set h[n]=null
    set n=n+1
    exitwhen n>3000
endloop
return false
endfunction[/codes]
内存变化为
92,104（初始） 93,424  93,452   93,456   93,884  93,896   93,884   93,884  93,884  93,896
这是在排泄良好的情况下。

二
[codes=jass]globals
timer array h
endglobals
function aaa takes nothing returns boolean
local integer n=0
loop
    set h[n]=CreateTimer()
    call DestroyTimer(h[n])
    set n=n+1
    exitwhen n>3000
endloop
return false
endfunction[/codes]
内存变化为
92,100（初始） 93,416  93,568  93,684  93,772  94,320  94,508  94,592  94,700  94,788  94,876  94,972
貌似这样会有泄露？它不是自己会回收内存的吗？
再一次测试
92,080（初始） 93,400  93,936  94,056  94,152  94,252  94,440  94,536  94,620  94,720  94,820  94.908

三
[codes=jass]globals
timer array h
endglobals
function aaa takes nothing returns boolean
local integer n=0
loop
    set h[n]=null
    set h[n]=CreateTimer()
    call DestroyTimer(h[n])
    set n=n+1
    exitwhen n>3000
endloop
return false
endfunction[/codes]
内存变化为（这个应该就和DataSystem同理了，我们先不说Handle的变化，单看内存）
92,112（初始） 93,880  93,976  94,088  94,184  94,284  94,460  94,556  94,664  94,752  94,856  94,952

四
[codes=jass]globals
timer array h
endglobals
function aaa takes nothing returns boolean
local integer n=0
loop
    set h[n]=CreateTimer()
    call DestroyTimer(h[n])
    set h[n]=null
    set n=n+1
    exitwhen n>3000
endloop
return false
endfunction[/codes]
内存变化为
92,104（初始） 93,432  93,448  93.872  93,964  93,864  93,864  93,864  93,864 ...

好了。以上是关于内存方面的，看试验二应该知道全局变量也要set null，而三说明什么，这样做也同样会有泄露存在。试验四排泄良好。

14:19
嗯，下午接着做了些试验。

五
[codes=jass]globals
timer array nnn
integer I
timer Tm
endglobals
function aaa takes nothing returns boolean
local integer n=0
local integer I
local timer Tm
loop
    set nnn[n]=null
    set nnn[n]=CreateTimer()
    call DestroyTimer(nnn[n])
    set n=n+1
    exitwhen n>3000
endloop
set n=GetRandomInt(0,3000)
set Tm=nnn[n]
Bug(I-n)
Bug(n)
set I=0
return false
endfunction[/codes]

这样就可以查看DataSystem分配handle的情况了，由上试验三直接修改过来的。运行后屏幕上显示1048683和随机的n，这说明下脚标的获取是正确的。不过，泄露依然在，依然在。

那接下来看看泄露是怎么产生的。
六（1）
[codes=jass]globals
timer array nnn
integer I
timer Tm
endglobals
function aaa takes nothing returns boolean
local integer n=0
loop
    set nnn[n]=null
    set nnn[n]=CreateTimer()
    call DestroyTimer(nnn[n])
    set nnn[n]=null
    set nnn[n]=CreateTimer()
    call DestroyTimer(nnn[n])
    set n=n+1
    exitwhen n>3000
endloop
return false
endfunction[/codes]

内存变化为
92,080（初始） 94,792  94,956  95,048  95,576  95,776  95,860  95,968  96,056  96,156  96,240  96,340

六（2）
[codes=jass]globals
timer array nnn
integer I
timer Tm
endglobals
function aaa takes nothing returns boolean
local integer n=0
loop
    set nnn[n]=null
    set nnn[n]=CreateTimer()
    call DestroyTimer(nnn[n])
    set nnn[n]=CreateTimer()
    call DestroyTimer(nnn[n])
    set n=n+1
    exitwhen n>3000
endloop
return false
endfunction[/codes]

内存变化为
92,136（初始） 94,836  94,972  95,096  95,224  95,428  95,960  96,056  96,144  96,244  96,340  96,436

嗯，就目前来看呢，我们用最后占用的内存减去第二个数值，然后除以10来看下平均每3000个变量会泄露多少。
试验二，(94,972-93,416)/10=155.6
        (94,908-93,400)/10=150.8
试验三，(94,952-93,880)/10=107.2
试验六（1）(96,340-94,792)/10=154.8
试验六（2）(96,436-94,836)/10=160.0
其中三的结果是最小的，我又重新测了下（嗯，因为删了一些地图上的东西，初始占用内存变小了点）
        (92,240-90,672)/10=156.8  （这个测试期间内存跳了下，大概多了400）
        (92.148-90,864)/10=128.4
可以认为除了三，它们是相等的。
然后看，第二个数值减去初始的内存是
一，(93,424-92,104)=1,320
二，(93,416-92,100)=1,316
    (93,400-92,080)=1,320
三，(93.888-92,112)=1,776（Fk，这组数可能根本就是错的）
四，(93,432-92,104)=1,328
五，哎，跟三一样的代码，可惜没测内存...
六，(94,792-92,080)/2=1,356
    (94,826-92,136)/2=1,345
这个...我不知道怎么解释这一组数，哎...

那，现在我的猜想是
1，变量在指向一个已经删除了的项时，不set null会占用对应的handle。（哦，这不是猜想，这是DataSystem的基础）
2，在另外一个函数里面再set null的话，虽然handle会释放，但是依然会泄露，只是小了些（嗯，我不清楚，因为貌似三组的数据错了，但是如果只看趋势的话，它确实是泄露了）。
3，在同一个函数内，无论set null或者指向另外一个项，都会自动释放。

现在来验证下吧，预测下面的代码会造成之前两倍的泄露。嗯嗯。
六（3）
[codes=jass]globals
timer array nnn
timer array mmm
endglobals
function aaa takes nothing returns boolean
local integer n=0
loop
    set nnn[n]=CreateTimer()
    call DestroyTimer(nnn[n])
    set mmm[n]=CreateTimer()
    call DestroyTimer(mmm[n])
    set n=n+1
    exitwhen n>3000
endloop
return false
endfunction[/codes]
内存变化为
89,428（初始） 92,200  92,432(跳了...92,848)  93,136  93,316  93,504  93,700  93,896  94,080  94,276  94,464  94,648

(94,648-92,200)/10=244.8
(92,200-89,428)/2=1,386

而下面这个应该是没有泄露的。
六（4）
[codes=jass]globals
timer array nnn
endglobals
function aaa takes nothing returns boolean
local integer n=0
loop
    set nnn[n]=CreateTimer()
    call DestroyTimer(nnn[n])
    set nnn[n]=CreateTimer()
    call DestroyTimer(nnn[n])
    set nnn[n]=CreateTimer()
    call DestroyTimer(nnn[n])
    set nnn[n]=null
    set n=n+1
    exitwhen n>3000
endloop
return false
endfunction[/codes]
内存变化为
89,420（初始） 93,332  93,380  93,376  93,368(又跳...93,820)  93.816  93,804  93,816  93,820  93.820  93,820  93,808
我觉得应该忽略掉中间忽然增大的400K，我不清楚我那里出错了，但是应当是没泄露的。
(93,332-89,420)/3=1,304


嗯，说了这么一大堆，偏离正题太远啦。
结论就是DataSystem应当是可用的，话说amp34大大说的我没看懂...但是泄露是确确实实存在的，所以大家以后在使用数组记录东西的时候，删除它的时候就set null吧，别偷懒，要不然的话就使用整数数组来记录好了。

嗯，还有，我在10L有一个仿DataSystem的代码，虽然我还没有使用过它。但是基本上看不出泄露的问题，而且内存占用方面也没有大问题的，因为看上面的数据，3000个计时器也就是1,300K左右的内存吧。但是因为计时器不是删除的，所以它的使用面窄了，因为触发是不可以删除事件的，没办法重复利用了。

好了，就这么多。

cccty1l

唉 对上楼的一点修正，我后来才发现原来基本上每组的数据都有大概400K的增加，不知道魔兽自己搞什么了。
然后我把跳了400K的数据舍去，分开数据成两段，然后看结果
二    108   118
    108
三    107
六（1）    128    109
六（2）    118    95
六（3） 116    101

嗯，怎么说呢，应该说在另外的函数里面再set null一个指向空handle的变量，是没有用的，也就是说，嗯，还是Ls的结论，全局数组的话，还是跟局域变量一样，set null吧。

马甲终结者

事实上我在使用全局变量代替局部变量的时候除了简化部分代码之外还是会导致一些奇怪BUG。
似乎触发器不是单纯的队列执行哦。

当然，可能是地图过大导致的某些地方失误。

不过从哪以后我总是把handle型的全局变量也set null了。