一种新的存储结构和HASH改进算法及HandleTable运用

血戮魔动冰

嗯……实在是做地图做的不行了……回来写精华帖了……
（BOSD的系统……太难做了……死了好多脑细胞……幸好还剩下些写精华帖）

弄了3个内容，可以联系在一起，就在一个贴里发了~
1.新的存储结构：点链表、点数组
2.Hash拉链讲解和拉链Hash改进算法：拉链的取中法
3.HandleTable：新的存储系统的向往+基本使用方法

嗯……基本都是存储数据这一方面的……算是有联系的吧。

感谢疯人、cccty1。
疯人让我萌发了关于使用handle来存储数据的原始想法。
cccty1把他的拉链Hash表代码发了上来，并附了一些注释（但只有极少对我有用）。最后我在深夜用了1小时，对着他的代码学会了拉链Hash法。
感谢两人~

当然还有你的阅读~

（貌似我的“但是”、“那么”、“如果”等等……用得很多……大家不用介意，我语文不好……）

就这样，正文开始吧：

//==================================

血戮魔动冰

1楼：【点】风格的存储结构
话说某天……和疯人聊QQ（透露个小秘密，我QQ才刚注册几天~）…………他在跟我讲他关于怎样拓展timer的数据含义的想法（在T中，只用很少的J部分）。如果把一个handle地址的意义比作0.25，那么timer就只有0.25，而location就有2.25（x,y,handle）。他在想，如果能让timer也向location一样拥有2.25的数据意义呢？
他是这样想的：地图初始化时，一个timer创建完后，就创建一个location。这样在获得timer时，直接把Handle+1，就可以得到2个数据了………………
当然，某些人，一看就说：用TimerDataSystem！！
也许你没发现（在T中，只用很少的J部分）这一部分。
（好吧这是题外话）

详细的对话内容我已经忘却了，如今这些珍贵的对话资料已经遗失在茫茫网络中了。但是我受他的启发，居然发现可以在魔兽中实现【链表】、【另一种更方便的局部数组传递】、【超越8192的伪数组】了……………………

后来我又想了很多，将这个东西发掘了一下，成果就发一下吧~~

不过~大家要记住是疯人启发我的，不要忘记他哦~~

我讲的顺序是（好假）：
1.【超越8192的伪数组】
2.【链表】
3.【另一种更方便的局部数组传递】

1.【超越8192的伪数组】

我在想，一个timer只能配一个location，只能有2个有意义的数据，如果能多几个就好了。当时我第一想的是链表，但是，后来我又想到一种更好、更快捷、更省事的办法，而且直接脱离了数组，同样也没有了8192的限制。不过虽然脱离了8192的限制，但是效率降得可不是一星半点……

我的想法是，如果需要更多的数据，那么在初始化时直接增加location的数量就好了。比如一个timer创建后，配10个location，这样的话，就可以有20个数据了。而要获得这些location，只要将timer的handle再加上你要获得的location的位移下标，就可以得到对应的location。再GetLocationX/Y就可以得到真正的数据了。
但是，这虽然能突破8192的限制。却也有两个缺点：
1.效率绝对比全局变量低（这是必然的，GetLocation+GetLocationX/Y怎么看都不能比全局变量数组快）。
2.这必须要在初始化时运行。由于HandleTable的特点使得我们不能在初始化之后再次重新创建location和timer，因为这时你不能保证timer的handle，一定和location连在一起。

（PS：使用Location来存储handle_address应该没有问题，我试过用990000,990000来测试Location，很惊讶的没有崩溃，我继续用GetLocationZ来测试，只是返回0而已……）

代码：
[codes=jass]function H2I takes handle h returns integer
return h
return 0
endfunction

function I2Loc takes integer i returns location
return i
return null
endfunction

function Init takes integer timer_number, integer loc_number returns nothing
local integer i = 0
local integer j = 0
loop
exitwhen i >= timer_number
call CreateTimer()
set j = 0
loop
exitwhen j >= loc_number
call Location( 0.0, 0.0 )
set j = j + 1
endloop
set i = i + 1
endloop
endfunction
//建议timer_number * loc_number不要太大，否则可能有危险。魔兽一个触发器运行的代码字符是有限制的，除非用等待……

function GetHAL takes integer handle_address, integer where returns location
return I2Loc( handle_address + where )
endfunction[/codes]

2.【链表】

是这样的……
好吧~疯人给我记录了~~（太神奇了~当然也有可能我不会看QQ通话记录的缘故…………）：

血戮魔动冰16:02:33
1.timer绑定指定location。location包含一个location和一个数据，然后，再获得下一个location的location下一个location的location…………而每个location都包含一个数据………………

好吧………………

好吧~~链表~这又是个貌似很陌生的东东~于是解释一下（高人就不要怪我啦）：
迄今为止，在魔兽中，是没有能实现链表的。只能用数组里的一些指针来做静态链表，但大多数还是基于数组本身的存储表示。数组优点是：
1.无需为元素间的逻辑位置关系增加额外的存储空间，省了很多内存
2.可以方便的用下标来获得对应的元素，无需做任何逻辑运算。
3.相对于魔兽内部的现有的存储结构而言，它是物理层面上最快的存储结构
但是其缺点是：
1.受限于最高限制8192
2.对于某些要求在struct中实现数组的人来说，必须使用2维数组来解决。而且由于struct内一种元素要求的数量。导致整个struct的数量上限下降到8192/最大的某种元素要求的数量
当然了，这还是因为魔兽自身的数组就是个Table，为空的元素自动不为其非配空间所致，要不然大家才不会这么不要命的用数组呢~~（一句话里居然有4个不……我的语文真差…………）

再来看链表：
链表，对元素使用链接的形式进行集合。
基本有几种之分：
单链表：每个结点都有一个指向它的下一结点的指针next，可以通过此结点的next来获得下一结点。尾结点next为空。
循环列表：与单链表相似，只不过尾结点next为头结点，这样其实就没有头尾之分了。
双向列表：与循环列表相似，只不过每个结点都增加了一个指向上一节点的指针before，头结点before指向尾结点。
它的优点是：
1.相对于数组，数组在传递时需要很多资源（魔兽的数组根本没法传递……），而链表，只要传递一个头结点的指针（循环和双向只要任意一个结点就可以了），就可以依次获得整个链表了。
也就是说，他的灵活性是比数组要高得多的。
缺点是：
1.相对于数组，他需要一个额外的数据域来存储下一个节点的地址，所以在存储的空间上比数组要多一点。
2.在获得指定结点时，需要不断地迭代地寻找指定的结点。在最坏的情况下，它的开销是O(n)，n是整个链表的结点个数。
3.由于链表无法直接在魔兽里实现，所以效率要差一点点

那么我们来看一些关于链表的实际应用：
比如：我需要给timer绑定一组种类相同但值不同的数据，而这一组数据可能有1-150个。而且同一时间的timer会有几百个，数据是顺序存入/读取的。如果你想用struct+成员数组来实现，你会发现就算是挤满了8192有些情况就会超出。所以数组及其派生的所有如HashTable什么的绝对是第一时间排除（如果一个存储结构在实际的问题应用时会发生数据无效的情况，那么对于这个问题，这个存储结构就算是废了）。那么我们想，魔兽中，除了数组以外，就只有GameCache和我现在讲的链表了。那么此时怎么办呢？如果用GameCache的话，"Data"+1-150的话，先不说string的使用，光是效率就是非常低的。那链表呢？它能不能担任这个重任呢？
首先，我们确定他是顺序存入/读取的，那么如果是链表的存入/读取，那么链表的结构上的读取/存入的劣势就被消除了（这只是设定而已，假一点不要怪我）。然后，用这个肯定不会产生string。但是会使用handle，所以需要remove他们。这基本与Flush的开销基本一样。
最后，我们来分析一下GameCache和location（这是用location来测试，其他handle的存储的开销基本上就跟location的开销差不多）在物理方面的效率吧。
首先我们可以肯定，location是在内存层面进行的操作（要不是，我找玻璃渣理论去……），而GameCache是在外存的层面进行的操作，可以想见，除非location的存储/读入有专门的很费事的算法，否则，location的效率是绝对由优于GameCache。接下来分析location到底有没有费事的算法。
首先location的数据存储函数是Get/SetLocationX/Y，如果变成C++，那么绝对不会有什么麻烦的算法：
[codes=C++]void/double location::Get/SetLocationX/Y ( double the_x/y/ )
{
return x/y;
/
x/y = the_x/y;
}[/codes]
自然暴雪也不会比这更复杂些（没准会有地图坐标Z高度检测什么的）。而GameCache，就算他没有关于字符串的运算，光是它在外存（嗯……真正的物理地址应该在硬盘上）这一点硬伤上，location就绝对是优于GameCache的，但是事实呢？

为了测试location和GameCache以及全局变量（但是很遗憾的是我用newgen貌似有问题，无法支持globals，其实是我找不到没有中文路径的地方啦……其实是懒而已………………），我用newgen的japi中的StopWatch（据说比timer精确……）测试了一下，结果如下（方面并不全，只测试了一个location的存储/读取的情况，主要原因是location-linkedlist它的查找是个线性一次函数，不好测试，最多也就是个O(n)的开销）（全部是测试同一location/missionkey-key的数据，每次都重复100次）（我没有对代码测试过两次，所以这些数据是不太准确的，但它能说明一些很显而易见的问题）：
取出数据方面：
循环本身开销：1.780
location：2.528 与循环本身开销的差：0.748
GameCache：3.939 与循环本身开销的差：2.159
location与GameCache效率比：3：1

存储数据方面：
循环本身开销：1.780
location：3.513 与循环本身开销的差：1.733
GameCache：4.754 与循环本身开销的差：2.974
location与GameCache效率比：1.7：1

通过这组测试数据，我们可以得知，空白location的效率，是绝对优于gamecache的。而且还没有了string过量使用的困扰。
（一个小小的不幸的事实被我言中了：location果然需要）
那既然我们对比了gamecache，那么我们能对比一下globals和location的效率吗？
很遗憾……不能……但是我可以明确的告诉你们……不管是存储还是取出数据方面，globals都是优于location。而且在存储数据方面……是绝对的优于location。

而且，由于点链表它的特殊结构，读取数据时，必须遍历此数据前面的所有结点，所以效率会随着结点的多少而不断递增。最大开销为O(n)。数组是直接通过index来直接在内存中找到数据地址，GameCache经过老狼测试，它的效率非常平稳，而location-linkedlist一个得到指定位置的函数都需要一个loop循环。
[jass]globals
location LinkedList_Find_Return = null
endglobals

constant function I2Loc takes integer i returns location
return i
return null
endfunction

function LinkedList_Find takes location head, integer index returns location
local integer i = 0
set LinkedList_Find_Return = head
//如果用local location temp的话，则返回时不能清空变量，所以我用了全局变量
loop
exitwhen i >= index
set LinkedList_Find_Return = I2Loc( R2I( GetLocationX( LinkedList_Find_Return ) ) )
//当index大于链表长度时，最后的location的x必定为0
//而I2Loc则得到null，GetLocationX( null )得到0
//如此循环直到i==index，此时location为null
//所以这样写是没有什么问题的
set i = i + 1
endloop
return LinkedList_Find_Return
endfunction[/jass]
所以基本上，当链表长度>10（我估计）时，效率就可能连GameCache都不如了。

你们会说：这个臭链表，搞那么复杂，怎么效率这么让人恶心，还不如用GameCache都比这好！

但是，链表的真正价值不在于此。
一般来说，GameCache和数组在存储方面是基本不能互相包含的（总觉得话说不明白……）。比如在GameCache里，你想存储一个数组，那怎么办呢？
[jass]call StoreXXXX( <gc>, <missionkey>, <key> + I2S( <x~y> ), <values> )
//……
GetStoredXXXX( <gc>, <missionkey>, <key> + I2S( <x~y> ) )[/jass]
不得不说，这样的效率是差到了极点的……
而存储一个index是可以的……
但是一个数组呢？
怎么把一个数组塞进GameCache里？
这在编辑方面就是无解的……

你能在数组里用GameCache吗？
[jass]globals
gamecache array GCs
endglobals

function GetGC takes integer index returns gamecache
if index > 256 then
return null
else
return GCs[index]
endif
endfunction[/jass]
这是不可能的，魔兽最多支持256个GameCache（如果我没记错的话），这基本上是使用不了的。

也就是说，数组存不了GameCache，GameCache存不了数组。
这两种存储结构不能合二为一，取长补短，这是我们WEer一直解决不了的难题。

但是链表作为一个存储结构，它能不能与数组、GameCache叠加、为这俩主流存储结构补短呢？
答案是可以的，而且非常有用~~

先说linkedlist+gamecache。
如上文所说，gamecache想要存储一个数组的数据，效率非常低。
linkedlist能不能帮他把效率提一提呢？
很简单，将数组的数据存进链表里，gamecache只存储一个头结点，读取时，按照结点顺序依次读取就可以了。
[jass]globals
gamecache GC
endglobals

function H2I takes handle h returns integer
return h
return 0
endfunction

function I2Loc takes integer i returns location
return i
return null
endfunction

function Init takes nothing returns nothing
//init GC
endfunction

function Store takes nothing returns nothing
local integer array Set//一个数组的数据
local integer len//数组长度
local integer i = len
local location loc = null
loop
exitwhen i < 0
set loc = Location( H2I( loc ), Set )
set i = i - 1
endloop
call StoreInteger( GC, <mission key>, Set, H2I( loc ) )
call StoreInteger( GC, <mission key>, Len, len )
//......
endfunction

function Restore takes nothing returns nothing
local integer array Set
local integer len = GetStoredInteger( GC, <mission key>, "Len" )
local location loc = I2Loc( GetStoredInteger( GC, <mission key>, "Set" ) )
local integer i = 0
loop
exitwhen i >= len
set Set = R2I( GetLocationY( loc ) )
set loc = I2Loc( R2I( GetLocationX( loc ) ) )
set i = i + 1
endloop
//......
endfunction[/jass]
这样，GameCache的效率不高的特点就被掩盖了过去。他的效率会提升1.5-3倍。
而且，这样还避免了string的产生，可以说是全方面的优化。
基本上，没有增加什么代码的难度，一般会jass的WEer基本很快就能上手。

再来看location和array的组合。
介于array本身的限制，标准魔兽风格的array是不能被包含在其他存储结构里的。
所以我们只能将location包含在array里。

数组有4种用法，一种指针，一种Hash，一种struct，一种DataSystem（与GameCache结合）。
对于指针和struct，我们可以用location避免其内置数组占用过多index的情况。
比如我们的一个timer绑定一个8元素的数组。但是这让我们很不爽，为什么呢？
因为我们需要将每个绑定单元的间隔变为8。而由于魔兽数组的8192限制，我们就只能有1024个绑定单元了。
一下少了7000个绑定单元……这太坑人了……
那么我们只要用location改进一下就可以。
将数组变为链表。我们只用头结点就可以得到整个链表。这样，我们只要在单元里用一个location变量就可以代表数组了。
这样，理论上，所有绑定单元的数组都可以变为链表来存储。这样，我们的绑定单元的最大数量就可以不受内部数组的限制了。
[jass]globals
constant integer Min_Number = A000
integer maxN = 1
integer p = 0
integer array Set
location array SetInSet
endglobals

function H2I takes handle h returns integer
return h
return 0
endfunction

function I2Loc takes integer i returns location
return i
return null
endfunction

function GetNumber takes location head returns integer
local integer index = p
if index == 0 then
set index = maxN
if index > 8191 then
return 0
endif
set maxN = index + 1
else
set p = Set[index]
endif
set SetInSet[index] = head
return index
endfunction

function FlushNumber takes integer index returns nothing
local location loc = SetInSet[index]
local location next = null
set Set[index] = p
set p = index
loop
set next = I2Loc( R2I( GetLocationX( loc ) ) )
exitwhen next == null
call RemoveLocation( loc )
set loc = next
endloop
set loc = null
set next = null
endfunction[/jass]
DataSystem因为用GameCache，所以就不说了（太方便了），对应的数组的可以看上面指针和struct的优化。

接下来我们说Hash。
现在我们使用Hash有大体两种处理溢出的方法。
第一种是传统的Hash。
分有：
1.+-1
2.+-n^2(n++)
3.ReHash()
第二种是传统Hash怎么也比不了的拉链Hash（强烈推荐！！！！！！可以看cccty1的《还是说数组存储系统》、《还是说数组存储系统续》都是非常好的Hash的贴，当然我在写此贴时，《续》还没看完，估计会有拉链Hash的详讲……但是我在家里没法上网，所以看不了……只好看他的拉链Hash以前的简略的帖子……幸好cccty1是个好人，还写点注释……）
传统的Hash在我的《数据结构：由浅入深谈Hash表 及 数组存储系统》中有提到……
但是我很可恶的略去了ReHash的介绍及效率。
你可以看回帖，有人指明《算法导论》提到ReHash是在+-1,+-n^2(n++)，ReHash中平均搜索效率最高的方法。
好，题外话结束。
Hash表已经为我们提供了用数组很好的代替GameCache的算法。但是还是有一个硬伤那就是魔兽jass最大数组尺寸8192的限制。如果能突破这个限制，那么GameCache肯定会成为历史。但是事实不是这样的（要不然现在我们哪会用Hash啊！直接用指针就好了）。
那么我们现在可以利用location不受8192的影响这一特性，为Hash补短。
我们知道，现在拉链Hash是查找效率最高的Hash法。他的最大开销是O(n)，n=求模后与查找的index（已求模）相同的但原始数据不同的元素个数。
如果我们要用location代替array，那么我们必须在算法上至少与拉链Hash一样才行。
我是这样想的。
N个全局变量数组（N=一个元素单位里有的数据个数）存储头结点。
当取余后得到index，就将数据插入得到的index的链表（头结点）里。
查找时，按顺序查找即可。
这样，此算法的开销就与拉链Hash一样了（能不一样吗？数学模型都是一样的……）。
但是不同就在于，这个方法，他没有理论上的数量限定。而拉链Hash的所有元素单位的个数只能限定在8192之内。所以，这样的话，这种存储结构就基本可以替代GameCache了。他可以完全为这个地图里的所有需要绑定数据的有价值的Handle绑定数据。
示例为方便采用了location。但是你在使用时绝对不会用location，而是能够放更多的数据进去的Handle。
也就是说，示例是一个什么也做不了的东西。但是你可以看出这个方法的模型。
[jass]globals
location array Hash_Set
location temp_Location
endglobals

function H2I takes handle h returns integer
return h
return 0
endfunction

function I2Loc takes integer i returns location
return i
return null
endfunction

function Hash_Create takes integer value returns location
local integer index = value - value / 8191 * 8191
local location loc = Hash_Set[index]
set Hash_Set[index] = Location( H2I( Hash_Set[index] ), value )
if loc == null then
call MoveLocation( Hash_Set[index], H2I( Hash_Set[index] ), value )
//构造循环链表
endif
set loc = null
return Hash_Set[index]
endfunction

function Hash_Get takes integer value returns location
local integer index = value - value / 8191 * 8191
local location loc = Hash_Set[value]
loop
exitwhen loc == null
if GetLocationY( loc ) == value then
set temp_Location = loc
set loc = null
return temp_Location
endif
set loc = I2Loc( R2I( GetLocationX( loc ) ) )
endloop
endfunction

function Hash_Destroy takes location loc returns nothing
local location next = I2Loc( R2I( GetLocationX( loc ) ) )
local location before = next
local integer hi = H2I( loc )
loop
exitwhen GetLocationX( before ) == hi
set before = I2Loc( R2I( GetLocationX( before ) ) )
endloop
call MoveLocation( before, H2I( next ), GetLocationY( before ) )
call RemoveLocation( loc )
set next = null
set before = null
endfunction[/jass]
（演示中采取了单循环链表，你可以把它弄成双链表，这样Destroy会更快一些）

3.【另一种更方便的局部数组传递】
很简单的东西，就是把链表当成数组在函数间传递，与location+GameCache较相像。
[jass]function H2I takes handle h returns integer
return h
return 0
endfunction

function I2Loc takes integer i returns location
return i
return null
endfunction

function AFunciton takes location loc, ... returns ...
local location array Set
local integer len = 0
set Set[len] = loc
loop
exitwhen Set[len] == null
set Set[len+1] = I2Loc( GetLocationX( Set[len] ) )
set len = len + 1
endloop
//...
endfunction

function BFunction takes ... returns ...
local location array Set
local integer len = ...
local integer i = len - 2
set Set[len-1] = Location( 0.0, ... )
loop
exitwhen i < 0
set Set = Location( H2I( Set[i+1] ), ... )
set i = i - 1
endloop
//...
call AFunction( Set[0], ... )
endfunction[/jass]
我也不太知道这会有什么用。但是疯人说，好像可以在T的方面有作用……（我真是个不折不扣的j啊，都是T的了，还用j写……）
恩就发一下了。

（提醒：这里的链表、数组是专指魔兽里的链表、数组。如果你用别的语言编程，如C++，你会发现别的编程语言的数组、链表和魔兽的数组、链表是有差别的，差别大到你会彻底改变自己对链表和数组的看法及评价）



//==================================

血戮魔动冰

2楼：Hash拉链讲解和拉链Hash改进算法：拉链的取中法

嗯……这个方面应该是cccty1和某一大群人专精的，但是我这人就是喜欢什么都搞。所以，大家就凑合看看吧~~
（写这个主要原因是，在论坛貌似没有写拉链Hash的帖子，可能他的《还是说数组存储系统续》中介绍了方法，但是在他那个贴之前，也就是我写此贴之前，还没有人在GA介绍过拉链Hash）
拉链Hash，它的名称就基本代表了它的算法。
就是在数组里不断地把链子拉来拉去。其实就是几个链表而已。
我只介绍双链表Hash。
双链表，就是双向链表，每个单元结点都有两个域：before和next。分别存储前一个结点的index，和后一个结点的index。以及一个域：原始参数域。链表里存储着所有取余后得到同样结果的原始数据的结点的index。其他的结果则用另外的链表。每个0-8191的单元里，有一个结点（不一定就是这个单元的专门所属的链表中的一个），有一个指向专属链表（就是上面说的链表）的表头。插入时，插入在链表的表头处。在搜索时，从此单元的表头域得到表头，再顺次遍历链表比对原始参数就可以了。这样，一个拉链Hash就解决了。
一般来说，分配结点的index是用vj中的struct的方法解决的（因为比较简单）。
代码：
[jass]globals
integer Hash_MaxNumber = 1
integer Hash_StackTop = 0
integer array Hash_Head
integer array Hash_Before
integer array Hash_Next
integer array Hash_TheValue
endglobals

function Hash_Create takes integer value returns integer
local integer index = value - value / 8191 * 8191
local integer new_index = Hash_StackTop
local integer temp = 0
if new_index != 0 then
set Hash_StackTop = Hash_Next[new_index]
else
set new_index = Hash_MaxNumber
if Hash_MaxNumber > 8191 then
return 0
endif
set Hash_MaxNumber = new_index + 1
endif
set temp = Hash_Head[index]
set Hash_Head[index] = new_index
set index = temp
if index != 0 then
set Hash_Before[index] = new_index
endif
set Hash_Next[new_index] = index
set Hash_TheValue[new_index] = value
return new_index
endfunction

function Hash_Get takes integer value returns integer
local integer index = Hash_Head[ value - value / 8191 * 8191 ]
loop
exitwhen index == 0
if Hash_TheValue[index] == value then
return index
endif
set index = Hash_Next[index]
endloop
return 0
endfunction

function Hash_Destroy takes integer index returns nothing
local integer before = Hash_Before[index]
local integer next = Hash_Next[index]
local integer value = Hash_TheValue[index]
if before == 0 then
set value = value - value / 8191 * 8191
set Hash_Head[value] = next
else
set Hash_Before[index] = 0
set Hash_Next[before] = next
endif
if next != 0 then
set Hash_Before[next] = before
endif
set Hash_TheValue[index] = 0
set Hash_Next[index] = Hash_StackTop
set Hash_StackTop = index
endfunction[/jass]
Hash_Next在结点无用时，用作struct的链式栈。
函数讲解：
Hash_Create中：value就是原始参数。index是取余后的index，new_index是新的节点的index。temp用作临时的交换变量用。
第一个if中的所有代码全部是vj的struct所需。
[jass] set temp = Hash_Head[index]
set Hash_Head[index] = new_index
set index = temp
if index != 0 then
set Hash_Before[index] = new_index
endif
set Hash_Next[new_index] = index
set Hash_TheValue[new_index] = value[/jass]
这些就是在链表的链表头的插入及新节点的设置。
Hash_Get：很好看懂，就是获得表头后顺序在链表内查找而已。
Hash_Destroy：
[jass] set Hash_Next[index] = Hash_StackTop
set Hash_StackTop = index[/jass]
这是用来实现struct的代码。
[jass] if before == 0 then
set value = value - value / 8191 * 8191
set Hash_Head[value] = next
else
set Hash_Before[index] = 0
set Hash_Next[before] = next
endif
if next != 0 then
set Hash_Before[next] = before
endif
set Hash_TheValue[index] = 0[/jass]
before==0，就是结点前面没有节点，也就是表头的位置。此时需要将表头重新设为next。
如果before!=0，就是在表中，或表尾的位置。此时需要清除域，并链将before与next连接，补完链表。
然后是next的连接。最后是清空（Hash_Next不用清空是因为struct要用到）。

2009.4.7 16：58我看到了cccty1的《续》，应该算是将得较清晰的，大家可以看他的，当然我和他的一块看也可以。

后来，我在散步时，想了一下Hash拉链的Hash。它的平均搜索长度是n/2。n=与搜索的原始数据取余后得到相同结果的数量是一样的。但是我仍不满足，能不能在优化一下呢？
于是我想了想。
我采用的方法是取中法，就是直接对比【已排序的链表】的中点，然后如果要搜索的原始数据>此节点的原始数据那么再对比以【此次前端节为起点、此节点为终点的链表段】的中点（我们简称他为此节点的前一中点），如果要搜索的原始数据<此节点的原始数据对比以【此次前端节为起点、此节点为终点的链表段】的中点（我们简称他为此节点的后一中点）。如果=直接返回就可以。
这样不断循环，直到找到对应结点。
当然还有一些最后比对时的措施（比如一段的长度是0什么的）。

大家可能看不明白，看一个图就可以：
表头 表尾
（这是一个有顺序的链表，如果是普通的拉链Hash，则有可能是32145什么的）
1 2 3 4 5
(----->| )
表头的中点指向链表的中点
( |<-)(->| )
链表的中点指向2,4即1-3的中点和3-5的中点。

比如我们要查找4。
那么首先我们得到表头，并得到链表的中点：3。
接下来我们将4与3比对，发现4>3。
那么我们按上面所说的规律查找，得到3的后一中点：4
比对，发现4=4，返回结果。
这样，我们只比对了2次，而拉链Hash则需要比对4次。

当然，这样对于拉链Hash的效率比对是不公平的。
拉链Hash他的效率是一个线性函数O(n)，我们就用平均的搜索长度来表示：i=n/2（i即平均查找次数）。
取中法的效率该怎么算呢？
我们会发现，对于每一个结点，取中法都是不断取中再比对的。那么我们可以粗略的表示成2^i=n（i即平均查找次数）。
因为这是取中法平均到达每一个节点的查找长度。
但是事实上会略微小于这个表达式（因为链表中的所有【中点】都是比另一些结点要更早一些被比对）。
准确的表达式我是写不出来的（我还上中学呢……）。
而且这个取中法是不会因为被查找的节点在链表中的位置而发生太大的改变，这也是我非常喜欢这个方法的原因。

接下来，我们要求出这两个表达式的相等结果，以便我们发现这两个方法哪个更高效。
我们将i=n/2带入2^i=n中
得到2^(n/2) = n
这个式子的结果，我不会求（无数的西红柿向我飞来，把我砸个满面通红）。

然后我发现，将n=2，4带入此式后，得到的i是一样的。
而将8带入此式后，拉链Hash的i=4，取中法的i=3。

继而将1024（2^10）带入此式后，得拉链Hash的i=512，取中法的i=10。
所以当n>4时，理论上取中法的效率是大于拉链Hash的效率，而且随着n的增大，优势也越来越多。
但n<4时，拉链Hash和取中法不相上下。

时间效率分析完后，我们再分析一下空间效率。对比Hash，我们可以直接发现，多了两个数组。一般来说，空间是不被现在的程序员所很不重视的。

其实，我这吹得这么NB，其实我的取中法是有重大缺陷的。
一般来说，创建和删除的运行次数<获得index的运行次数。所以我们直接将更新链表中点的工作放在创建和删除函数里就可以。

问题就在这里，先不说，看我的取中法的代码吧：
[jass]globals
integer Hash_MaxNumber = 1
integer Hash_StackTop = 0
integer array Hash_Head
integer array Hash_Before
integer array Hash_Next
integer array Hash_TheValue

integer array Hash_BeforeMiddle
integer array Hash_NextMiddle

constant integer Hash_MinMiddleNumber = 4

//从大到小

endglobals

function Hash_Create takes integer value returns integer
local integer index = value - value / 8191 * 8191
local integer new_index = Hash_StackTop
local integer temp = 0

local integer array LinkedList
local integer len = 1
local integer new_loc = 0
local integer i = 0
local integer array StackLeft
local integer array StackRight
local integer array StackMiddle
local integer left = 0
local integer right = 0
local integer middle = 0
local integer nextleft = 0
local integer nextright = 0
local integer top = 0

if new_index != 0 then
set Hash_StackTop = Hash_Next[new_index]
else
set new_index = Hash_MaxNumber
if Hash_MaxNumber > 8191 then
return 0
endif
set Hash_MaxNumber = new_index + 1
endif

set LinkedList[0] = Hash_Head[index]
loop
if Hash_TheValue[LinkedList[len-1]] > value then
set new_loc = len - 1
endif
set LinkedList[len] = Hash_Next[LinkedList[len-1]]
exitwhen LinkedList[len] == 0
set len = len + 1
endloop

if new_loc == 0 then
set temp = Hash_Head[index]
set Hash_Head[index] = new_index
set index = temp
else
set index = LinkedList[new_loc+1]
set Hash_Next[LinkedList[new_loc]] = new_index
endif
if index != 0 then
set Hash_Before[index] = new_index
endif
set Hash_Next[new_index] = index
set Hash_TheValue[new_index] = value

set i = len - 1
loop
exitwhen i <= new_loc
set LinkedList = LinkedList[i-1]
set i = i - 1
endloop
set LinkedList[new_loc] = new_index
set len = len + 1

set StackLeft[0] = 0
set StackRight[0] = len - 1
set StackMiddle[0] = ( len - 1 ) / 2
set Hash_NextMiddle[LinkedList[0]] = LinkedList[StackMiddle[0]]
loop
exitwhen top < 0
if StackRight[top] - StackLeft[top] < Hash_MinMiddleNumber then
set StackRight[top] = 0
set StackLeft[top] = 0
set StackMiddle[top] = 0
set Hash_BeforeMiddle[LinkedList[middle]] = 0
set Hash_NextMiddle[LinkedList[middle]] = 0
set top = top - 1
else
set left = StackLeft[top]
set right = StackRight[top]
set middle = StackMiddle[top]
set nextleft = ( left + middle ) / 2
set nextright = ( right + middle ) / 2
set Hash_BeforeMiddle[LinkedList[middle]] = LinkedList[nextleft]
set Hash_NextMiddle[LinkedList[middle]] = LinkedList[nextright]
//set StackLeft[top] = left
set StackRight[top] = middle
set StackMiddle[top] = nextleft
set top = top + 1
set StackLeft[top] = middle
set StackRight[top] = right
set StackMiddle[top] = nextright
endif
endloop

return new_index
endfunction

function Hash_Get takes integer value returns integer
local integer index = Hash_Head[ value - value / 8191 * 8191 ]
local integer before = index
local integer middle = Hash_NextMiddle[index]
local boolean IsFromLeft = true
loop
exitwhen middle == 0
set before = middle
if Hash_TheValue[middle] > value then
set IsFromLeft = false
set middle = Hash_BeforeMiddle[middle]
elseif Hash_TheValue[middle] < value then
set IsFromLeft = true
set middle = Hash_NextMiddle[middle]
else
return middle
endif
endloop
set index = before
if IsFromLeft then
loop
if Hash_TheValue[index] == value then
return index
endif
set index = Hash_Next[index]
endloop
else
loop
if Hash_TheValue[index] == value then
return index
endif
set index = Hash_Before[index]
endloop
endif
return 0
endfunction

function Hash_Destroy takes integer index returns nothing
local integer before = Hash_Before[index]
local integer next = Hash_Next[index]
local integer value = Hash_TheValue[index]

local integer array LinkedList
local integer len = 1
local integer array StackLeft
local integer array StackRight
local integer array StackMiddle
local integer left = 0
local integer right = 0
local integer middle = 0
local integer nextleft = 0
local integer nextright = 0
local integer top = 0

if before == 0 then
set value = value - value / 8191 * 8191
set Hash_Head[value] = next
else
set Hash_Before[index] = 0
set Hash_Next[before] = next
endif
if next != 0 then
set Hash_Before[next] = before
endif
set Hash_TheValue[index] = 0
set Hash_BeforeMiddle[index] = 0
set Hash_NextMiddle[index] = 0
set Hash_Next[index] = Hash_StackTop
set Hash_StackTop = index

set LinkedList[0] = Hash_Head[index]
loop
set LinkedList[len] = Hash_Next[LinkedList[len-1]]
exitwhen LinkedList[len] == 0
set len = len + 1
endloop

set StackLeft[0] = 0
set StackRight[0] = len - 1
set StackMiddle[0] = ( len - 1 ) / 2
loop
exitwhen top < 0
if StackRight[top] - StackLeft[top] < Hash_MinMiddleNumber then
set StackRight[top] = 0
set StackLeft[top] = 0
set StackMiddle[top] = 0
set top = top - 1
else
set left = StackLeft[top]
set right = StackRight[top]
set middle = StackMiddle[top]
set nextleft = ( left + middle ) / 2
set nextright = ( right + middle ) / 2
set Hash_BeforeMiddle[LinkedList[middle]] = LinkedList[nextleft]
set Hash_NextMiddle[LinkedList[middle]] = LinkedList[nextright]
//set StackLeft[top] = left
set StackRight[top] = middle
set StackMiddle[top] = nextleft
set top = top + 1
set StackLeft[top] = middle
set StackRight[top] = right
set StackMiddle[top] = nextright
endif
endloop

endfunction[/jass]

因为n<=4时，拉链和取中法效率一样，所以我们在获得到1-3的区间后，直接顺序查找就可以。
我说的重大效率缺陷就在他的创建和删除的效率上。
创建相对于拉链Hash，增加了一个插入算法：
[jass] set i = len - 1
loop
exitwhen i <= new_loc
set LinkedList = LinkedList[i-1]
set i = i - 1
endloop
set LinkedList[new_loc] = new_index
set len = len + 1[/jass]
他的查找长度是i，而且这个i=原先拉链Hash查找这个原始数据的次数。
平均也是n/2。
后面的栈（你可以看做递归）查找，就是n/4的长度。
这样创建就增加了3/4*n的查找长度。
删除增加了n/4的长度。
这样，创建+删除就直接增加了n的长度。
还有，创建和删除都需要一个遍历全部链表的loop
那还要加2n。
共3n
如果实际情况中这个原始数据没有使用一次GET就删除了，那么我们就亏大发了。还不如用原版的拉链Hash呢。
怎么让创建和删除的效率再高一点呢？

//========================

我想了2个办法。
1.插入排序与遍历合并
很简单，就是把插入排序和遍历合并，这样创建的长度就是1.25n了。
Create合并后的代码：
[jass]function Hash_Create takes integer value returns integer
local integer index = value - value / 8191 * 8191
local integer new_index = Hash_StackTop
local integer temp = 0

local integer array LinkedList
local integer len = 1
local integer new_loc = 0
local integer i = 0
local integer array StackLeft
local integer array StackRight
local integer array StackMiddle
local integer left = 0
local integer right = 0
local integer middle = 0
local integer nextleft = 0
local integer nextright = 0
local integer top = 0

if new_index != 0 then
set Hash_StackTop = Hash_Next[new_index]
else
set new_index = Hash_MaxNumber
if Hash_MaxNumber > 8191 then
return 0
endif
set Hash_MaxNumber = new_index + 1
endif

set LinkedList[0] = Hash_Head[index]
loop
set LinkedList[len] = Hash_Next[LinkedList[len-1]]
exitwhen LinkedList[len] == 0
if Hash_TheValue[LinkedList[len-1]] <= value then
set len = len + 1
set LinkedList[len] = LinkedList[len-1]
set LinkedList[len-1] = new_index
endif
set len = len + 1
endloop

if new_loc == 0 then
set temp = Hash_Head[index]
set Hash_Head[index] = new_index
set index = temp
else
set index = LinkedList[new_loc+1]
set Hash_Next[LinkedList[new_loc]] = new_index
endif
if index != 0 then
set Hash_Before[index] = new_index
endif
set Hash_Next[new_index] = index
set Hash_TheValue[new_index] = value

set StackLeft[0] = 0
set StackRight[0] = len - 1
set StackMiddle[0] = ( len - 1 ) / 2
set Hash_NextMiddle[LinkedList[0]] = LinkedList[StackMiddle[0]]
loop
exitwhen top < 0
if StackRight[top] - StackLeft[top] < Hash_MinMiddleNumber then
set StackRight[top] = 0
set StackLeft[top] = 0
set StackMiddle[top] = 0
set Hash_BeforeMiddle[LinkedList[middle]] = 0
set Hash_NextMiddle[LinkedList[middle]] = 0
set top = top - 1
else
set left = StackLeft[top]
set right = StackRight[top]
set middle = StackMiddle[top]
set nextleft = ( left + middle ) / 2
set nextright = ( right + middle ) / 2
set Hash_BeforeMiddle[LinkedList[middle]] = LinkedList[nextleft]
set Hash_NextMiddle[LinkedList[middle]] = LinkedList[nextright]
//set StackLeft[top] = left
set StackRight[top] = middle
set StackMiddle[top] = nextleft
set top = top + 1
set StackLeft[top] = middle
set StackRight[top] = right
set StackMiddle[top] = nextright
endif
endloop

return new_index
endfunction[/jass]
2.因为这个Hash表其实就是需要创建和删除时使用取中的更新。那么我们不妨将它更新的次数降低，比如每有4个结点加入/取出，才运行更新的代码。这样Destroy的效率会大大增加。
destroy的就直接变为拉链Hash的效率了
除了Get都写了新代码：
[jass]globals
integer Hash_MaxNumber = 1
integer Hash_StackTop = 0
integer array Hash_Head
integer array Hash_Before
integer array Hash_Next
integer array Hash_TheValue

integer array Hash_BeforeMiddle
integer array Hash_NextMiddle

constant integer Hash_MinMiddleNumber = 4

//从大到小

integer array Hash_Change

endglobals

function Hash_Create takes integer value returns integer
local integer index = value - value / 8191 * 8191
local integer new_index = Hash_StackTop
local integer temp = 0

local integer array LinkedList
local integer len = 1
local integer new_loc = 0
local integer i = 0
local integer array StackLeft
local integer array StackRight
local integer array StackMiddle
local integer left = 0
local integer right = 0
local integer middle = 0
local integer nextleft = 0
local integer nextright = 0
local integer top = 0

local integer change = Hash_Change[Hash_Head[index]]

if new_index != 0 then
set Hash_StackTop = Hash_Next[new_index]
else
set new_index = Hash_MaxNumber
if Hash_MaxNumber > 8191 then
return 0
endif
set Hash_MaxNumber = new_index + 1
endif

set LinkedList[0] = Hash_Head[index]
loop
set LinkedList[len] = Hash_Next[LinkedList[len-1]]
exitwhen LinkedList[len] == 0
if Hash_TheValue[LinkedList[len-1]] <= value then
set len = len + 1
set LinkedList[len] = LinkedList[len-1]
set LinkedList[len-1] = new_index
endif
set len = len + 1
endloop

if new_loc == 0 then
set temp = Hash_Head[index]
set Hash_Head[index] = new_index
set index = temp
set Hash_Change[new_index] = change
else
set index = LinkedList[new_loc+1]
set Hash_Next[LinkedList[new_loc]] = new_index
endif
if index != 0 then
set Hash_Before[index] = new_index
endif
set Hash_Next[new_index] = index
set Hash_TheValue[new_index] = value

if change >= Hash_MinMiddleNumber then
//{
set Hash_Change[Hash_Head[value - value / 8191 * 8191]] = 0
set StackLeft[0] = 0
set StackRight[0] = len - 1
set StackMiddle[0] = ( len - 1 ) / 2
set Hash_NextMiddle[LinkedList[0]] = LinkedList[StackMiddle[0]]
loop
exitwhen top < 0
if StackRight[top] - StackLeft[top] < Hash_MinMiddleNumber then
set StackRight[top] = 0
set StackLeft[top] = 0
set StackMiddle[top] = 0
set Hash_BeforeMiddle[LinkedList[middle]] = 0
set Hash_NextMiddle[LinkedList[middle]] = 0
set top = top - 1
else
set left = StackLeft[top]
set right = StackRight[top]
set middle = StackMiddle[top]
set nextleft = ( left + middle ) / 2
set nextright = ( right + middle ) / 2
set Hash_BeforeMiddle[LinkedList[middle]] = LinkedList[nextleft]
set Hash_NextMiddle[LinkedList[middle]] = LinkedList[nextright]
//set StackLeft[top] = left
set StackRight[top] = middle
set StackMiddle[top] = nextleft
set top = top + 1
set StackLeft[top] = middle
set StackRight[top] = right
set StackMiddle[top] = nextright
endif
endloop
//}
else
set Hash_Change[Hash_Head[value - value / 8191 * 8191]] = change + 1
endif

return new_index
endfunction

function Hash_Destroy takes integer index returns nothing
local integer before = Hash_Before[index]
local integer next = Hash_Next[index]
local integer value = Hash_TheValue[index]

local integer array LinkedList
local integer len = 1
local integer array StackLeft
local integer array StackRight
local integer array StackMiddle
local integer left = 0
local integer right = 0
local integer middle = 0
local integer nextleft = 0
local integer nextright = 0
local integer top = 0

local integer change = Hash_Change[Hash_Head[index]]

if before == 0 then
set value = value - value / 8191 * 8191
set Hash_Head[value] = next
else
set Hash_Before[index] = 0
set Hash_Next[before] = next
endif
if next != 0 then
set Hash_Before[next] = before
endif
set Hash_TheValue[index] = 0
set Hash_BeforeMiddle[index] = 0
set Hash_NextMiddle[index] = 0
set Hash_Next[index] = Hash_StackTop
set Hash_StackTop = index

if change >= Hash_MinMiddleNumber then
//{
set Hash_Change[Hash_Head[value - value / 8191 * 8191]] = 0
set LinkedList[0] = Hash_Head[index]
loop
set LinkedList[len] = Hash_Next[LinkedList[len-1]]
exitwhen LinkedList[len] == 0
set len = len + 1
endloop

set StackLeft[0] = 0
set StackRight[0] = len - 1
set StackMiddle[0] = ( len - 1 ) / 2
loop
exitwhen top < 0
if StackRight[top] - StackLeft[top] < Hash_MinMiddleNumber then
set StackRight[top] = 0
set StackLeft[top] = 0
set StackMiddle[top] = 0
set top = top - 1
else
set left = StackLeft[top]
set right = StackRight[top]
set middle = StackMiddle[top]
set nextleft = ( left + middle ) / 2
set nextright = ( right + middle ) / 2
set Hash_BeforeMiddle[LinkedList[middle]] = LinkedList[nextleft]
set Hash_NextMiddle[LinkedList[middle]] = LinkedList[nextright]
//set StackLeft[top] = left
set StackRight[top] = middle
set StackMiddle[top] = nextleft
set top = top + 1
set StackLeft[top] = middle
set StackRight[top] = right
set StackMiddle[top] = nextright
endif
endloop
//}
else
set Hash_Change[Hash_Head[value - value / 8191 * 8191]] = change + 1
endif

endfunction[/jass]

这两个办法，其实都是治标不治本的方法，取中Hash真正的恶心的地方在于，他需要遍历整个链表。

其实大家可以发现……这貌似就像一个二叉树一样……
创建/删除函数都是构建二叉树的过程……
而GEt就是通过二叉树查找的过程。

（其实我后来看《数据结构》时发现……我这只不过是把Hash表和【跳表】结合了而已……）

也就是说，如果不能解决这个问题，那么取中Hash的Create和Destroy的效率将是取中的一大硬伤。
//========================
好了2009 4 8快9点了。也该睡了。明天继续吧。

血戮魔动冰

明天来到了~~

好吧……我终于想到了区中Hash的改进再改进算法……

我是这样想，如果我们在创建和删除时，直接获得需要的是中点的节点（数目是n/4+1，头尾各一），再从这里区中就好了。

那么我们直接按照每4个一个地跳过获得链表，就完全可以了。
这样，我们还需要一个数组来存储此节点的下个隔了4个结点的结点……
一个End，存储尾结点……
……不得不说，这是牺牲了精准度而开发的一种恶心的算法，但是在n较大时非常有效。


啊啊啊啊啊啊啊嘎嘎嘎嘎嘎嘎嘎嘎嘎嘎！！！

（旁白：血戮魔动冰犯神经病了~）

好了……只是想抱怨一下而已……周末脑子进水了，用了：周五的下午+周六一天+周日上午+周日0.5个下午，才写出了应该无Bug的算法……于是，我强烈建议大家不要自己写这个算法……你会非常痛苦的……我的Hash.w3x用了23条call BJDebugMsg()……啊啊……痛苦…………~~~~(>_<)~~~~
我的脑细胞啊…………

大家先看代码……我先发会疯再说……
[jass]globals
integer Hash_MaxNumber = 1
integer Hash_StackTop = 0
integer array Hash_Head
integer array Hash_Before
integer array Hash_Next
integer array Hash_TheValue

integer array Hash_BeforeMiddle
integer array Hash_NextMiddle

constant integer Hash_MinMiddleNumber = 4

//从大到小

integer array Hash_NextLLMiddle
//integer array Hash_BeforeLLMiddle

integer array Hash_End
integer array Hash_AddCount

endglobals

function Hash_Create takes integer value returns integer
local integer index = value - value / 8191 * 8191
local integer head = Hash_Head[index]
local integer new_index = Hash_StackTop
local integer temp = 0

local integer array LinkedList
local integer len = 1
local integer new_loc = 0
local integer i = 0
local integer array StackLeft
local integer array StackRight
local integer array StackMiddle
local integer left = 0
local integer right = 0
local integer middle = 0
local integer nextleft = 0
local integer nextright = 0
local integer top = 0

local boolean find = false
local integer count = 0

if new_index != 0 then
set Hash_StackTop = Hash_Next[new_index]
else
set new_index = Hash_MaxNumber
if Hash_MaxNumber > 8191 then
return 0
endif
set Hash_MaxNumber = new_index + 1
endif

set LinkedList[0] = head
loop
set temp = LinkedList[len-1]
if not find then
if Hash_TheValue[temp] <= value then
set new_loc = temp
loop
exitwhen new_loc == 0 or Hash_TheValue[new_loc] > value
set new_loc = Hash_Before[new_loc]
endloop
if new_loc != 0 then//不在队首
//new_loc = new_before
//set find = true
if Hash_Next[new_loc] != 0 then
set Hash_Before[Hash_Next[new_loc]] = new_index
endif
set Hash_Next[new_index] = Hash_Next[new_loc]
set Hash_Before[new_index] = new_loc
set Hash_Next[new_loc] = new_index
if new_loc == Hash_End[index] then
set Hash_End[index] = new_index
endif
else
//set Hash_NextLLMiddle[new_index] = Hash_Before[Hash_NextLLMiddle[head]]
set LinkedList[0] = new_index
set Hash_Before[new_index] = 0
set Hash_Next[new_index] = head
if head != 0 then
set Hash_NextMiddle[new_index] = Hash_NextMiddle[head]
set Hash_Before[head] = new_index
else
set Hash_NextMiddle[new_index] = 0
endif
set Hash_Head[index] = new_index
if Hash_End[index] == 0 then
set Hash_End[index] = new_index
endif
endif
set find = true
if temp != 0 then
set Hash_NextLLMiddle[Hash_Before[temp]] = Hash_NextLLMiddle[temp]
set Hash_NextLLMiddle[LinkedList[len-2]] = Hash_Before[temp]
set Hash_NextLLMiddle[temp] = 0
set temp = Hash_Before[temp]
set LinkedList[len-1] = temp
endif
set Hash_TheValue[new_index] = value
endif
else
if temp != 0 then
set Hash_NextLLMiddle[Hash_Before[temp]] = Hash_NextLLMiddle[temp]
set Hash_NextLLMiddle[LinkedList[len-2]] = Hash_Before[temp]
set Hash_NextLLMiddle[temp] = 0
set temp = Hash_Before[temp]
set LinkedList[len-1] = temp
endif
endif
set LinkedList[len] = Hash_NextLLMiddle[temp]
exitwhen LinkedList[len] == 0
set len = len + 1
endloop

set len = len - 1
set Hash_AddCount[index] = Hash_AddCount[index] + 1
if Hash_AddCount[index] >= Hash_MinMiddleNumber then
set Hash_AddCount[index] = 0
if LinkedList[len] != Hash_End[index] then
set Hash_NextLLMiddle[LinkedList[len]] = Hash_End[index]
set Hash_NextLLMiddle[Hash_End[index]] = 0
endif
set len = len + 1
set LinkedList[len] = Hash_End[index]
endif
if LinkedList[len] != Hash_End[index] then
set len = len + 1
set LinkedList[len] = Hash_End[index]
endif

set StackLeft[0] = 0
set StackRight[0] = len
set StackMiddle[0] = len / 2
set Hash_NextMiddle[LinkedList[0]] = LinkedList[StackMiddle[0]]
loop
exitwhen top < 0
if StackRight[top] - StackLeft[top] < 2 then
set StackRight[top] = 0
set StackLeft[top] = 0
set StackMiddle[top] = 0
set Hash_BeforeMiddle[LinkedList[middle]] = 0
set Hash_NextMiddle[LinkedList[middle]] = 0
set top = top - 1
else
set left = StackLeft[top]
set right = StackRight[top]
set middle = StackMiddle[top]
set nextleft = ( left + middle ) / 2
set nextright = ( right + middle ) / 2
set Hash_BeforeMiddle[LinkedList[middle]] = LinkedList[nextleft]
set Hash_NextMiddle[LinkedList[middle]] = LinkedList[nextright]
//set StackLeft[top] = left
set StackRight[top] = middle
set StackMiddle[top] = nextleft
set top = top + 1
set StackLeft[top] = middle
set StackRight[top] = right
set StackMiddle[top] = nextright
endif
endloop

return new_index
endfunction

function Hash_Get takes integer value returns integer
local integer index = Hash_Head[ value - value / 8191 * 8191 ]
local integer before = index
local integer middle = Hash_NextMiddle[index]
local boolean IsFromLeft = true
loop
exitwhen middle == 0
set before = middle
if Hash_TheValue[middle] > value then
set IsFromLeft = true
set middle = Hash_NextMiddle[middle]
elseif Hash_TheValue[middle] < value then
set IsFromLeft = false
set middle = Hash_BeforeMiddle[middle]
else
return middle
endif
endloop
set index = before
if IsFromLeft then
loop
exitwhen index == 0
if Hash_TheValue[index] == value then
return index
endif
set index = Hash_Next[index]
endloop
else
loop
exitwhen index == 0
if Hash_TheValue[index] == value then
return index
endif
set index = Hash_Before[index]
endloop
endif
return 0
endfunction

function Hash_Destroy takes integer index returns nothing
local integer before = Hash_Before[index]
local integer next = Hash_Next[index]
local integer value = Hash_TheValue[index]
local integer from = value - value / 8191 * 8191

local integer array LinkedList
local integer len = 1
local integer array StackLeft
local integer array StackRight
local integer array StackMiddle
local integer left = 0
local integer right = 0
local integer middle = 0
local integer nextleft = 0
local integer nextright = 0
local integer top = 0

local boolean find = false
local integer temp = 0

if before == 0 then
set Hash_Head[from] = next
set Hash_NextMiddle[next] = Hash_NextMiddle[index]
else
set Hash_Before[index] = 0
set Hash_Next[before] = next
endif
if next != 0 then
set Hash_Before[next] = before
//set Hash_Next[index] = 0
else
set Hash_End[from] = before
endif
set Hash_TheValue[index] = 0
set Hash_BeforeMiddle[index] = 0
set Hash_NextMiddle[index] = 0
set Hash_Next[index] = Hash_StackTop
set Hash_StackTop = index

set LinkedList[0] = Hash_Head[index]
loop
set temp = LinkedList[len-1]
if not find then
if Hash_TheValue[LinkedList[len-1]] <= value then
set find = true
set Hash_NextLLMiddle[Hash_Next[temp]] = Hash_NextLLMiddle[temp]
set Hash_NextLLMiddle[LinkedList[len-2]] = Hash_Next[temp]
set temp = Hash_Next[temp]
set LinkedList[len-1] = temp
endif
else
set Hash_NextLLMiddle[Hash_Next[temp]] = Hash_NextLLMiddle[temp]
set Hash_NextLLMiddle[LinkedList[len-2]] = Hash_Next[temp]
set temp = Hash_Next[temp]
set LinkedList[len-1] = temp
endif
set LinkedList[len] = Hash_NextLLMiddle[LinkedList[len-1]]
exitwhen LinkedList[len] == 0
set len = len + 1
endloop

set Hash_AddCount[from] = Hash_AddCount[from] - 1
if Hash_AddCount[from] < 0 then
set Hash_AddCount[from] = Hash_AddCount[from] + Hash_MinMiddleNumber
set Hash_NextLLMiddle[LinkedList[len-1]] = 0
endif

set StackLeft[0] = 0
set StackRight[0] = len
set StackMiddle[0] = len / 2
loop
exitwhen top < 0
if StackRight[top] - StackLeft[top] < 2 then
set StackRight[top] = 0
set StackLeft[top] = 0
set StackMiddle[top] = 0
set top = top - 1
else
set left = StackLeft[top]
set right = StackRight[top]
set middle = StackMiddle[top]
set nextleft = ( left + middle ) / 2
set nextright = ( right + middle ) / 2
set Hash_BeforeMiddle[LinkedList[middle]] = LinkedList[nextleft]
set Hash_NextMiddle[LinkedList[middle]] = LinkedList[nextright]
//set StackLeft[top] = left
set StackRight[top] = middle
set StackMiddle[top] = nextleft
set top = top + 1
set StackLeft[top] = middle
set StackRight[top] = right
set StackMiddle[top] = nextright
endif
endloop

endfunction[/jass]

好了，我恢复正常了。不过我的取中法的优化就先告一段落吧……
这种方法的效率：
Create：n/2
（插入+得到跳表的跳点的开销：n/4，更新跳表的开销：n/4）
Destroy：n/2
（插入+得到跳表的跳点的开销：n/4，更新跳表的开销：n/4）
Get：2^i=n i+-(1~2)
这么说不科学，但是可以肯定的是Get的效率变得不太稳定了。

其实我还是在想……如果前面的Create和Destroy变成一个插入二叉树的过程就好了。不过这样的话，它的效率虽说相对于拉链Hash有提升，但是却变得很不稳定。所以我不建议使用这种方法。

由于实在是太累（身心疲惫），cccty1l（或者别的什么人）……就帮忙把这个查找的东东写一下吧……虽然不是很好的朋友~

最后，我们来分析这个取中法的实用性吧~

首先，我们说，取中法和拉链hash的临界点是n=4。所以，当n<=4时，拉链Hash是优于取中法的（效率上其实只是差一点点而已，但真正的差距在于代码的难度上）。那么取中法的真正优势就在于当n>4时，而且随着2的阶数的增长，效率差就会飞涨~~

所以，我们只要分析了这个n=4的关键点，我们就能发现这个取中法到底实不实用。
如果n=4，那么我们说，最大的HandleAddress（我们简称他为MaxHA）-最小的HandleAddress（MinHA）的结果/8191=4。
也就是说，这张地图里至少有8191*4=32764个。如果会用的话，一张地图里像什么树木等等的永久性，无用的Handle是不在其中的。那么我们说，32764，基本上一个地图里有这个数字的Handle……那还是图吗？
当然……如果真有那样的图……建议可以用取中法（好吧……咱不能再装了，就叫跳表法吧）的。
所以，得出结论：
跳表法，是基本无用的~~啦啦啦~~
（有西红柿*32764扔向了我）

好吧……其实跳表法主要是在n较小时，没有发挥它应有的优势罢了~剩下的其实还说的过去……不过确实比拉链hash要差一点……

最后（真囧，我都用了几个【最后】了？……算了，语文不是帖子纠结的地方……大家无视即可……），我把自己写跳跃跳表法中的一些技术难点（算是技术指导吧）讲一下，大家自己写的时候要注意啊~以及关于使用二叉树插入法的Hash的一些大体想法及情况（代码就不写了，太累了）。

技术难点1：跳跃跳表法的数据域
这个算是比较简单的，我的跳表中加入了End、Hash_NextLLMiddle、Count这三个域，大家其实可以参考一下。
End和Count属于一个链表的成员。
End指向链表尾（这个很好实现）
Count用来计数，表示当前链表插入了几个节点，当Count达到4时（即需要为链表新建一个LLMiddle的时候），我们新建一个LLMiddle，将原先的链表的最后一个LLMiddle的下一个LLMiddle指向End，End的下一个LLMiddle指向0
LLMiddle，属于每个中点（其实是近似的中点），记录下一个隔了4的结点。

一个链表的所有LLMiddle组成跳表（此时并不是完美的跳表，而是最尾部的间隔较少的跳表，不过这样一样能起到提高效率的作用）的节点。并用栈（Stack）构建新的跳表。

技术难点2：新数据的插入。
对于一个新数据，我们要把它插入到链表中，其实直接先顺序对比中点，在找到应对应的中点后，再在这个中点的范围内，寻找真正应该插入的地方。在新数据插入后，我们需要将这个新数据以后的所有旧的中点全部向前移一位（旧的中点的前一点变为中点），这样才能保持链表与跳表的整齐。并且还要在每插入/移除4个结点时，整理最后的跳跃结点。

技术难点3：链表的大小顺序
这是影响这个问题的关键：
[jass] if Hash_TheValue[temp] <= value then
set new_loc = temp
loop
exitwhen new_loc == 0 or Hash_TheValue[new_loc] > value
set new_loc = Hash_Before[new_loc]
endloop[/jass]
如果temp=0，那么Hash_TheValue[temp]就很可能=0。此时如果用从小到大的顺序排结点，那就惨了。
但其实这是没关系的，你只要加一条temp!=0就可以啦~

技术难点4：构建跳表结点的规则
这回
[jass]if StackRight[top] - StackLeft[top] < 2 then[/jass]
差可不是一个变量了，变为一个常数2了。因为Left、Right是已加入到跳表中的结点，所以此时结点间距（Right-Left-1）为1才可以不再分了。

应该就这么多了……
（事先警告：请一定先理清思路再上机编这个算法，否则你会死的很惨！我是用了一个周末的时间才搞定的，并且为此发了很大脾气……）

关于一些二叉树构建Hash的想法：
（好吧……我又要写成二叉树的教程了……）
二叉树：每个结点有1个左子节点、1个右子节点。每棵树有N个节点。
x
left right
一棵二叉树：
root
k l
e y g
t b
很简略。
二叉搜索树是基于二叉树的动态搜索结构。因输入的元素关键码序列的不同，会有不同形态的二叉搜索树（而且会影响搜索的效率）。

3
2
1

2
1 3

1
2
3

1
3
2

3
1
2

几棵二叉搜索树的例子。

查找时，只要从根节点不断对比【>,<,==】结点的关键码，不断向下迭代就可以。>时，搜索右子节点（或左子节点），<时搜索左子节点（或右子节点），==时返回这个节点。跟跳表差不多。
插入时，查找应插入的位置就可以了。
搜索长度<=二叉搜索树的高度h

嗯……我在前面说过，输入的元素关键码序列会影响到搜索的效率。其中影响效率的，就是根节点，以及有子节点的结点输入顺序。
比如，输入顺序：1234。
1
2
3
4
这样的效率和拉链Hash是一样的。
而输入顺序为：2134时。
2
1 3
4
效率会比上面的快不少。

所以根节点（以及有子节点的结点）的大小是非常关键的。
而要使得二叉搜索树的效率提高，我们可以通过调整各个结点的相对位置来实现。
删除要将断掉的二叉搜索树连起来……

其实最简单的二叉搜索树的效率都要比拉链Hash要好一些（最坏情况与拉链Hash效率一样，最好情况与跳表Hash一样）。

血戮魔动冰

//专门弄一个楼来放图片……防止论坛的codes与图片的Bug~~

举个例子：




//专门弄一个楼来放图片……防止论坛的codes与图片的Bug~~

血戮魔动冰

此时要删去二叉搜索树中的关键码为78的结点。
有两种选择：
1.将此节点中左子节点的关键码最大的结点node（应该是左节点中序遍历的最后一个结点，就是迭代获得结点的右子节点，直到右子节点为空）移到被删除结点的位置。同时将node的左子节点移到node的位置。
2.将此节点中右子节点的关键码最小的结点node（应该是右节点中序遍历的第一个结点，就是迭代获得结点的左子节点，直到左子节点为空）移到被删除结点的位置。同时将node的右子节点移到node的位置。（图中采用的方法）

这样，二叉搜索树的3种基本方法就弄完了……
讲得不太详细……以后专门发个帖讲吧………………

血戮魔动冰

3.HandleTable：新的存储系统的向往+基本使用方法

前面已经说道，location这个handle可以用来存储数据。那我就开始想，如果handle可以用来做存储结构，那么HandleTable是不是也可以借助handle变成一个存储系统呢？

答案当然是可以的。而且由于handle的物理地址全部在内存当中，所以肯定要比GameCache要好上不少。当然一些handle的赋值会伴有特殊的运算，所以要比全局变量数组要慢一些，最大的好处在于，HandleTable可以突破8192的限制。

我想出来的2种用HandleTable做存储系统的方法：

1.构造一个尺寸>8192为len的数组，元素为链表的想法。
想法就是，初始化时连续声明len个location。他们为链表的头结点。
然后，这len个location组成数组，就可以用全局变量数组的方法去得到index等等。
最大的好处是，由于len可以无限增长（理论上），所以指针法是不会有任何问题的。
这样得到index的时间复杂度是O(1)…………比别的算法要好上N倍。
[jass]globals
    integer LocationArray_Len = 0
endglobals

constant function H2I takes handle h returns integer
    return h
    return 0
endfunction

constant function I2List takes integer i returns location
    return i
    return null
endfunction

function Init takes integer len returns nothing
    local integer i = 0
    set LocationArray_Len = len
    loop
        exitwhen i >= len
        call Location( 0.0, 0.0 )
        set i = i + 1
    endloop
endfunction

function GetDataList takes handle h returns location
    return I2List( H2I( h ) - LocationArray_Len )
endfunction[/jass]

这种方法比较奢侈……

2.每出现一个handle，就声明一个链表，这样，每个handle的地址+1就可以得到他专属的链表了。
[jass]constant function H2I takes handle h returns integer
    return h
    return 0
endfunction

constant function I2List takes integer i returns location
    return i
    return null
endfunction

constant function NewHandle takes handle h returns location
    return Location( 0.0, 0.0 )
endfunction

constant function GetList takes handle h returns location
    return I2List( H2I( h ) + 1 )
endfunction

constant function GetNext takes location loc returns location
    return I2List( R2I( GetLocationX( loc ) ) )
endfunction

constant function DestroyList takes handle h returns nothing
    local location before = GetList( h )
    local location now = GetNext( before )
    loop
        set now = GetNext( before )
        call RemoveLocation( before )
        call DestroyList( before )
        exitwhen now == null
        set before = now
    endloop
    set before = null
    set now = null
endfunction[/jass]
当然，这样干是会有风险的，比如最近发现的trigger和event的关系（应该是这名），作者是thewisp1~
其中就提到，某些handletable中的handle可能会预占table中的位置，但可能未捕捉到。

当然，理论上只要每有一个handle（包括链表结点）创建/删除，就有一个链表创建/删除，那么这种方法就是安全高效的。

好啦~写完了啦~~~
总有些虎头蛇尾的感觉呢~~

哎……就先这样吧~~

字符数（包括空格）居然在Word里有50,000了。
最重要的是中文字符居然10,000了~~
不知道GA最长主题帖多少字……
恩恩……期中考试总算考完了呢…………

哎……执行者no.2的装备栏还没弄好……囧了…………

血戮魔动冰

HASH的Debug地图~~

cctvfive

看完了,说说我的看法.
1.总体而言,location链相对于数组的唯一优势是可以突破8192上限.
2.既然你知道数组下标的指针用法,就应该知道,如果不考虑上限的话,实现链表和动态数组根本就没什么难度.
3.本身就有获取点Z坐标的函数....不用加没准
4.你用来推翻数组的理由是同时存储的数据太多,但是,短时间内创建过多的点会卡机.
5.原来我在QQ群里说二叉树可以用来改进拉链哈希法的时候真的没想到过你会来个纯粹的二叉树..没有了数组的支持,纯粹的遍历,效率可想而知...

aeris

补充几点看法：

1.location需要同步，多人环境下无论是效率还是灵活性（比如能否配合LocaPlayer）既比不上数组又比不上GameCache
2.简单二叉树在实际应用中效果不够好（最坏情况下，会退化成链表），通常平衡树系列的AVL树、红黑树（特别是这个）才有比较好的效果
3.to LS的：二叉树的查找本身并不是很慢，期望值为O(log n)。只有在最坏情况下会退化成线性表。
4. 像红黑树这种数据结构，和哈希表相比，其最大的优势在于其自动维护数据的有序性。可以做到插入的是乱序的数据，取出来就是自动排序的（STL中的set就是例子），而哈希表中元素的排列的顺序是没有实际价值的。

cctvfive

嗯,我说二叉树效率低(介于log2(n)与n之间)是跟数组相比的,相比链表,显然是有优势的.

觉得Jass里的数据存储,发展到hash和DataSystem之后,再往下走,意义不大了.虽然我也做了些无用功..

louter

认同ls，一张地图若同时有datasys和hash绝对已经够用，我一直觉得这两者互相弥补了对方的缺点，效率和实用性都很强。

白银の式神

其实一般war3的图中的数据量还没有必要要动用平衡树罢...

緋桜

用着DataSystem都觉得卡的路过...

疯人￠衰人

……
只能这样了……

果然发展到了不可控制的地步……
实际上Location链表只是一瞬间的想法……
我也仅仅是拿它当做学习J的一个实例……
通过编写它来学J
不过我很成功的把血戮同学拉下水……
结果……
我还是罪魁祸首啊……

………………………………

恩，实际上关于Location的这种应用
很早就有人提到过
不过我是后来才发现的帖子……
location魔法。location是比GameCache更牛逼的存在
实际上，我自己编东西的时候
基本上是不考虑效率问题的
（一直都在弄T，想考虑也考虑不了）
基本上很多时候我都是拿效率换效果的
毕竟很多时候只是个演示，不必考虑实际应用的问题

…………………………………………

另一种更方便的局部数组传递
这个项目里血戮说我会在T中使用
我只能说这是谣言
实际上我的目的很简单
就是在函数间传递局域数组
（这个在某些极端情况下是需要的，比如我要返回多个内容）
虽然有很多方法可以解决这个问题
不过我不知道
只好自己想了这个办法
恩，我现在就有个想做的东西就需要传递不确定数量参数
具体……
也许我做不出来
恩，这个东西也不复杂，就是：
如果我们可以在地图上放置某个类型的单位
放置时必须满足：
在以要放置的点为圆心，半径为某个固定常数的圆范围内有已放置的这个类型的单位
当然，第一个放置的单位不需要这样
那么，当一个单位被放置，如何确定所有已经放置的单位是否组成了一个或多个封闭图形
（当两个单位间的距离小于判断范围的半径时，算两点式相连的）
有怎样按顺序（沿图形的边）记录下对应的单位
然后判断任意一个点是否在这个封闭的图形的内部（图形有可能是凹多边形）

哎哎……
上边就是一个自我为难……

基本上来说，用Location的效率不是很高的
如果10个Location拉链的效率就低于GAMECACHE
那么我只能说
这个系统的应用价值不是很高
实际上我自己已经用这个原理编了一个存储系统
一个数组变量系统
不过如果要实现超过8192的话
在拉链中查找超过10个点是必须的
（数组变量系统的话，比较少些单个存入和读取，平均每位数要读5个点（如果链表是10个为上限的话））
（存储系统是单向链表，可以说绑定在Timer上多少个变量，就要多少个）
恩，基本上就是这样

哦，数组变量系统已经发过了
那么一会把存储系统发上来吧

恩，就这样了……

louter

疯人兄知道小学的奥赛题目么，一笔画就是……这跟你所说的东西是一样的。其实当点多了以后有些问题是无解的，比如那个什么七桥问题。

不过如果善用region单元的话倒是可以处理一些非凹边形的问题。

以上为本人见解。

疯人￠衰人

引用第15楼louter于2009-04-28 21:09发表的  :
疯人兄知道小学的奥赛题目么，一笔画就是……这跟你所说的东西是一样的。其实当点多了以后有些问题是无解的，比如那个什么七桥问题。

不过如果善用region单元的话倒是可以处理一些非凹边形的问题。

以上为本人见解。

是可以多个头连的
只要释放技能的范围内有已放置的单位就可以
当然，被放置的单位是一直存在的
（直到组成闭合的图形）
每次放置都会检查是否有闭合图形
那么，也就是说：

我用点组成一个平面内的线段集合
这些线段至少有一段是与其他线段相连的（公用端点）
这些线段有个最大长度
新的线段是通过放置点来产生的
新放置的点需要与平面内其他已经放置的点组成至少一个小于最大长度的线段
当放置点后
如果平面内的所有线段（小于最大长度的）能够组成一个封闭图形
那么找出这个图型的顶点（按照边的顺序）
如果组成的图形是多个
那么找到最大的一个（多个组合起来的也算是一个封闭图形）
然后找到一种方法，能够判断任意点是否在这个封闭图形内部

以上为这个问题的几何说法

weberkx3

index 是 H2I 除 8191 取餘數之後的東西，只有8191的機率衝突

Hash_Head[index]
雙鍊(或稱多鍊)結構分支給每個Hash_Head的小鍊平均長度只有1
除非讓小鍊平均長度超過4，才讓二叉樹搜尋法有明顯的效能差異

這需要8191x4以上的數組佔用量........



地圖超過1000個Unit就已經很卡了
想佔用8191x4以上的數組，魔獸本身早就跑不動了

更不用說是創Location來做相關運\算
效能考量，已經完全抹殺「突破8191上限」的優點

直接模擬突破8191上限的函數(參考VJ)，搭配DataSystem或新一代的Struct+HASH，相信效能會好得多


研究是好事，但我認為效能考量應該擺在最優先的位置，否則再強大的系統，跑不動也是空

疯人￠衰人

应该是效果优先吧
在能够实现效果的前提下
才考虑能效的问题吧

weberkx3

突破8191的數據系統，若不計效能的話GC就能簡單的做出來
舊時代的GC威能大家應該很清楚，而且GC不慢，每秒讀寫一萬次以上才會Delay

倒是location儲存系統，每秒的極限是幾次，比GC快多少，相信很多人都希望能做個測試


效率並不是看loop能跑多少次
而是看連續跑N次之後，A函數Delay多久，B函數Delay多久

HASH的loop次數通常輸給GC
但連續運\作數萬次卻不會造成Delay
所以在不同類型的函數比較中，測試loop次數沒有意義

另外HASH+Struct的雙鍊、多鍊系統是目前最快，功能最強大的數據系統
稍微改造一下也可以支援超過8191函數的

模擬二維陣列也相當簡單
比起繞一大圈用location+線的遍歷去做，純HASH快多了

別忘了我們拋棄GC研發HASH就是為了［效能］

若沒有［效能］，乾脆回去用GC比較實際