|
|
恩~~~怎么说呢~~以前我是很不懂Hash表的，但是，经过2天的看帖，学习（其实主要是从书上看~~），我终于学会如何创建Hash表，并且将它运用到极为有用的方面。
好了不多说，往下看吧~~
1. 为什么要使用Hash表？
为什么讲Hash表，先说为什么使用呢？这是因为，如果你不懂为什么要使用Hash表，那么你会觉得Hash表示是个无用的东西。
为什么要使用Hash表？这是因为我们想为无数Handle类型绑定N个数据。
也许你要说，ReturnBug+GameCache已经足够了，但是，据我所知：
如果用全局变量数组，那么GameCache的存入速度近似与全局变量数组的存入速度的1/2（应该是，我不记得太清楚，但肯定要慢许多），取出速度也会稍慢一些。
而且，ReturnBug+GameCache也会因为大量的Handle地址被转换成string，会造成大量的string“泄露”，很让人恶心。
综上所述，我们可以用【ReturnBug+全局变量数组】替代【ReturnBug+GameCache】。
但是可行性呢？
由于ReturnBug的H2I返回的是一个integer变量，既可以I2S转换成string配合GameCache，也可以用作全局变量数组的下标，进而可以读取全局变量数组中的值，也就是说，这个办法是可行的。
但是稍微有些知识的人都知道，HandleAddress一般都是个7位数字，而且一般是1048XXX开始的。
那么如何才能把这个7位数字转换成小于8192（魔兽规定数组最大尺寸8192个元素）的全局变量数组的下标（index），并且保证不重复性呢？
这就是Hash表的作用。
2. Hash表为何物？
如果元素在存储结构中的位置与元素的关键码之间不存在直接的一一对应关系，那么就可以在元素的位置-元素的关键码之间建立一个常定的对应函数关系Hash()，使得每个关键码与结构中的一个唯一的存储位置相对应：
Address = Hash(key)
在插入时，依此函数计算存储位置并按此位置存放。搜索时也使用此函数查找关键码对应位置。
这种思想构造的表或序列，就叫做Hash表。
一般来说Hash()这个转换函数是一个压缩映像函数。一般关键码会比散列表中的可用位置数要多的多得多（但其中真正用到的关键码）。
所以这就会产生一个问题——冲突
（这一节，你可以适当的想：【元素的关键码】=ReturnBug转换的Address，【存储结构中的位置】=全局变量数组的下标，【散列表中的可用位置】=魔兽规定数组最大元素尺寸的8192）
3. 冲突
冲突就是指：在关键码很多的情况下，为了将所有的关键码全部映射到位置上，那就必然会出现N（N>=2）个关键码，会重复的选取到一个位置上。这将导致数据被覆盖等等恶心的Bug。那么，解决冲突就成了一大问题。
4. 散列函数Hash()
嗯~~就散列函数Hash()来时，一般的有4种方法（除留余数法、数字分析法、平方取中法、折叠法），其中我只介绍其中1种效率最高的方法及其冲突解决方案，以及一种非常简单非常迅速的Hash()，而且也不用担心冲突问题（当然~~有好就有坏~~）
最快的方法：
求底法：
首先我们知道，要绑定数据的是Handle类型。如果我们能事先知道这些Handle的Address的最小取值，那么将其他的Handle的Address-Min_Handle_Address，就等于它的Index了。
嗯~~一个看似完美，其实是极有缺陷的：被绑定Handle中的Max_Handle_Address - Min_Handle_Address < 8192，也就是说，差不多最多能绑定8192个Handle。
实现方法很简单：
[codes=jass]globals
integer Min_Handle_Address = 0
endglobals
function H2I takes handle h returns integer
return h
return 0
endfunction
function Hash_H2I takes handle h returns integer
return H2I( h ) - Min_Handle_Address
endfunction
function Hash_Init takes nothing returns nothing
local location loc = Location( 0.0, 0.0 )
set Min_Handle_Address = H2I( h )
call RemoveLocation( loc )
set loc = null
endfunction[/codes]
在其他所有Handle被创建之前，运行Hash_Init，再用Hash_H2I就可得到Index了。
但是注意，请务必保证Min_Handle_Address <= Any_Handle_Address。否则肯定会出错。
（因为这样Index就小于0了）
还有一个，比如你的地图上有一大堆的树木等等的【不可破坏】的地形装饰物等等的【不会删除的】Handle，那么你可以在创建了这些Handle之后，再运行Hash_Init。这样因为这些静态Handle不会被删除，它们占用的HandleAddress永远都不会被新的Handle所占用，这些新的Handle的Address永远都>Min_Handle_Address，所以不会引起Bug。
好吧~~一般来说，对于大部分的地图，这些已经足够了。
可是如果是RPG地图什么的，那就难办了~~
对此给出指导：
对游戏分章节进行（如《遗失的记忆》），每一章节创建此章节单位/删除上一章节单位等等~~
为了让大家更好地理解，将图奉上：
[upload=1]
好吧，如果你实在是想吃饱了撑的，要不然是真想学，还是地图太大~那你就往下看吧~~
最通用的方法：
5. 除留余数法。
最基础的想法：
如果地址数为number，那么取一个不大于number，但最接近number的质数p作为除数。散列函数为：
Hash(key) = key % p = Address (p<=m)
（%为取模运算）
（特殊要求：p不是接近n的幂）
（n=key的进制（在魔兽中，n=10））
（若p是接近n的幂，n的幂=key的进制的i次方）
（为什么p不是接近n的幂：因为这样会使Address仅是key的最后i位数字，以至于得到的Address分布太集中，导致冲突增多）
例如，有一个关键码100，number=44,则m=43，Hash(key) = key % 43，Hash(100) = 100 % 43 = 14。
（不过，一般来说，我们将m设成8192其实就可以了~~）
（[codes=jass]globals
constant integer const_Max_Array_Number = 8192
endglobals
function H2I takes handle h returns integer
return h
return 0
endfunction
function GetHandleIndex takes handle h returns integer
return ModuloInteger( H2I( h ), const_Max_Array_Number )
endfunction[/codes]）
这个Hash()得到的Index，就是最初步的数组的Index了。
（也就是说你可以用这个Index去数组里找东西了）
但是如果这个Index已被占用，那怎么办呢？
这就是我们接下来，也是这个帖子剩余的全部内容，我们将研究如何让冲突以最好的方式解决~~
6. 除留余数法：如何解决冲突
很简单的，我们很快就会想到，如果发生冲突了，那么，将另外一个地址，给传递过来的key，作为这个key映射的地址。
最简单的方法，就是将初步Index前面的一个地址（或后面的一个地址）（但必须是空的），作为这个key唯一映射的地址。
嗯，这样的话，我们就需要一个包含loop的函数GetNullIndex来向前（后）依次查找一个空的地址，用来插入发生冲突的。
[codes=jass]globals
constant integer const_NullorError_Number = -1
boolean array Hash_NotHaveData
endglobals
function GetNullIndex takes integer first_index returns integer
local integer i = first_index
loop
if i < 0 then
set i = i + const_Max_Array_Number
endif
set i = i - 1//这里是向前查找
//如果是向后查找，则用下面的替换
//if i >= const_Max_Array_Number then
// set i = i - const_Max_Array_Number
//endif
//set i = i + 1
if Hash_NotHaveData then
return i
endif
exitwhen i == first_index
endloop
return const_NullorError_Number
endfunction[/codes]
好，现在在插入的时候的这个Index可以得到了，那么在读取的时候，我们也需要用这个函数来获得真正的Index。
[codes=jass]globals
integer array Hash_Key
endglobals
function FindRightIndex takes integer first_index, integer key returns integer
local integer i = first_index
loop
if i < 0 then
set i = i + const_Max_Array_Number
endif
set i = i - 1//这里是向前查找
//如果是向后查找，则用下面的替换
//if i >= const_Max_Array_Number then
// set i = i - const_Max_Array_Number
//endif
//set i = i + 1
if Hash_Key == key then
return i
endif
exitwhen i == first_index
endloop
return const_NullorError_Number
endfunction[/codes]
由于不管在逻辑上，还是在实际编程中，这两个函数都应该原本为一个函数的。尤其是查找的向前或向后的顺序，必须统一，否则查找的时候那真是【南辕北辙】（真的非常形象），很可能只是在插入的时候向前移了一个，但是你查找时向后查找，只能在遍历了8191个Address后，才能找到正确的Address，但是如果统一，则只用查找一次就可以了（效率比真的很明显啊~~8191倍，爆笑~~(*^__^*) 嘻嘻……），所以合并：
[codes=jass]globals
constant integer const_NullorError_Number = -1
//用来标识空或错误的integer
boolean array Hash_HaveData
integer array Hash_Key
endglobals
function GetRightIndex takes integer first_index, integer key, boolean FindNull returns integer
local integer i = first_index
loop
if i < 0 then
set i = i + const_Max_Array_Number
endif
set i = i - 1//这里是向前查找
//如果是向后查找，则用下面的替换
//if i >= const_Max_Array_Number then
// set i = i - const_Max_Array_Number
//endif
//set i = i + 1
if FindNull then//如果是查找一个为空的
if not Hash_HaveData then//如果没有被占用
return i
endif
else//如果是查找一个key对应的地址的
if Hash_Key == key then//如果是正确的Address
return i
endif
endif
exitwhen i == first_index//如果成立则遍历了整个Hash表
endloop
return const_NullorError_Number
endfunction[/codes]
剩下的就是组建接口函数和初始化了~~
[codes=jass]globals
item array Hash_Items//用来存储一个物品（只是演示而已）
endglobals
function Hash_Data_Init takes nothing returns nothing
local integer i = 0
loop
exitwhen i >= const_Max_ArrayNumber
set Hash_Key = const_NullorError_Number
set i = i + 1
endloop
//初始化所有key
endfunction
function GetFirstIndex takes integer key returns integer
return ModuloInteger( key, const_Max_Array_Number )
endfunction
function Hash_CreateData takes integer key, item it returns nothing
local integer index = GetFirstIndex( key )
if Hash_HaveData[index] then
set index = GetRightIndex( index, key, true )
endif
if index != const_NullorError_Number then
set Hash_HaveData[index] = true
set Hash_Key[index] = key
set Hash_Items[index] = it
endif
endfunction
function Hash_GetIndex takes integer key returns integer
local integer index = GetFirstIndex( key )
if Hash_Key[index] != key then
set index = GetRightIndex( index, key, false )
endif
if index != const_NullorError_Number then
return index
endif
return const_NullorError_Number
endfunction
function Hash_GetItem takes integer key returns item
return Hash_Items[Hash_GetIndex( key )]
endfunction
function Hash_RemoveData takes integer key returns nothing
local integer index = Hash_GetIndex( key )
set Hash_HaveData[index] = false
set Hash_Key[index] = const_NullorError_Number
set Hash_Items[index] = null
endfunction[/codes]
（…………虽然没测试过，但是以上代码应该是可以直接拿到魔兽里去用的~~(*^__^*) 嘻嘻……）
关于线性探查法的效率改进1：其实这个东西还可以再次优化，举个例子，按我们上边的那个算法，如果没有创建则需要遍历整个8192的数组。
而且不管向前/向后遍历，两个有数据的Address，一般来说都是隔着几个空的Address。
那么我们能不能在查找的时候，直接跳过这些空的Address，直接“跳”到我们顺序下一个非空的Address呢？
嗯~~大家自己想一想（我发现自己的帖子总是直接将知识直接灌进大家的脑子里，太不人道了~~所以大家自己先想一想）
克制自己，不要往下看（或往下翻），只有自己想才能真正的将所有的知识消化，这是我的真实经验/感受。
好吧，其实我们只要把所有的非空的Address顺序连成一个环形双向链表，一个Address有3个域：
1.Before：在这个Address前面的最近的非空Address
2.数据域：上面的那些Hash_Key等等
3.Next：在这个Address后面的最近的非空Address
我们查找时，只要顺序向前/向后查找非空的Address就行了。
比如：在数组只有一个时，如果错误的使用函数GetIndex查找一个没有的Key的映射地址，那么按上面的方法：
遍历8192个数组
如果按我们的链表的方法，则是：
查找1个Address就退出了循环
效率比：8192：1~~(*^__^*) 嘻嘻……
嗯~~差不多：
[codes=jass]loop
set i = Hash_Before//or Hash_Next
if Hash_Key == key then
return i
endif
exitwhen i == first_index
endloop[/codes]
剩下的设置比较麻烦，就不写了（下面会有最终版）
这个查找形式上的优化几乎是什么方法都适用，所以请记好~~
关于线性探查法的效率改进2：
线性探查法的冲突是比较可怕的，比如说：
Address=5的地方有了冲突。后面的key就向前占用了Address=4并为空的地方。
然后，如果4的地方来了另一个key，他就会向前占用一个Address=3的地方。
接下来3来了，占用2的地方……
最后就是从4到2的地方的key在查找（读取）时，都会多遍历一个Address。
这与不发生冲突的情况的效率比（从4-2）是2：1效率整整低了一倍。
这种现象我们称其为【堆积】（是不是比较形象~~）
我这里有种可以缓解冲突的方法，但有得必有失，大家看吧：
基本思想就是将每一个插入点之间的距离由0增加，比如会隔3个Address（现在每个插入点到下一个插入点称为一个区）。
此时如果发生冲突，后面来的key就会顺序映射到区里的下一个位置。
此时受冲突影响的只有后面来的那个key，因为不管是前一个区，还是后一个区，跟他都挨不找边~~
使用这种方法，在一个区除非满了的时候，否则是绝对不会产生影响极大的堆积效果的。
但是，由于数组最多只能有8192个，且区的Address是固定的。那么插入点会相应地减少为：8192 / District_Address_Number
这会相应地让每个区内存储的Data数上升……
嗯~~算是一点点缺点吧。
建议在Data总数比较大的时候使用。
关于线性探查法的效率改进3：
在这时，求底法依然发挥着很强的作用。
他可以将所有Handle_Address变成一个存放数字很小的表。
而裸线性探查法如果很可能会导致更多的冲突。
（具体不说了，自己想(*^__^*) 嘻嘻……）
合并了所有的东东后的线性探查法的最终版：
[codes=jass]globals
constant integer const_Max_ArrayNumber = 8192
constant integer const_Max_HouseNumber = 4
constant integer const_Max_StreetNumber = 2048
//以上3个参数，都是界限，不可超过（如House的下标最多4-1=3个）
constant integer const_ErrorOrNullNumber = -1
integer Hash_Max_Node = 0
integer Hash_Min_Node = 0
integer Hash_Node_Number = 0
integer array Hash_Node_Before //节点的前一个节点
integer array Hash_Node_Next //节点的后一个节点
integer array Hash_Node_Mission//节点的missionkey(integer)
integer array Hash_Node_Key //节点的key(integer)
integer array Hash_Node_Word //节点的word(integer)
//上为节点的链表部分
integer array Hash_Data_Int
real array Hash_Data_Real
string array Hash_Data_Str
boolean array Hash_Data_Bool
//上为节点的存储数据部分（可拓展）
integer const_BottomHandleAddress = 0
endglobals
function Hash_Data_Init takes nothing returns nothing
local integer i = 0
loop
exitwhen i >= const_Max_ArrayNumber
set Hash_Node_Mission = const_ErrorOrNullNumber
set i = i + 1
endloop
endfunction
function H2I takes handle h returns integer
return h
return 0
endfunction
function Hash_Data_H2I takes handle h returns integer
return H2I( h ) - const_BottomHandleAddress
endfunction
//如果想用Handle当mission,key,word中的一项，请用上面的函数的返回值当mission,key,word。
function Hash_Data_Init_Handle takes nothing returns nothing
local location loc = Location( 0.0, 0.0 )
set const_BottomHandleAddress = H2I( loc )
call RemoveLocation( loc )
set loc = null
endfunction
function Hash_Data_ConvertNo takes integer mission, integer key, integer word returns integer
return mission + key + word
endfunction
function Hash_Data_GetStreet takes integer No returns integer
return ModuloInteger( No, const_Max_StreetNumber )
endfunction
function Hash_Data_ConvertIndex takes integer street, integer house returns integer
return street * const_Max_HouseNumber + house
endfunction
function Hash_Data_CreateNode takes integer Index returns integer
local integer i = 0
local integer next = 0
local integer re = const_ErrorOrNullNumber
local integer temp = 0
set Hash_Node_Number = Hash_Node_Number + 1
if Hash_Node_Mission[Index] == const_ErrorOrNullNumber then
if Hash_Node_Number == 1 then
set Hash_Max_Node = Index
set Hash_Min_Node = Index
set Hash_Node_Before[Index] = Index
set Hash_Node_Next[Index] = Index
return Index
endif
if Index > Hash_Max_Node then //如果Index指的是一个大于现在任何值的Node位置
set Hash_Node_Next[Hash_Max_Node] = Index
set Hash_Node_Before[Index] = Hash_Max_Node
set Hash_Node_Next[Index] = Hash_Min_Node
set Hash_Node_Before[Hash_Min_Node] = Index
set Hash_Max_Node = Index
set re = Index
endif
if Index < Hash_Min_Node then //如果Index指的是一个小于现在任何值的Node位置
set Hash_Node_Before[Hash_Min_Node] = Index
set Hash_Node_Next[Index] = Hash_Min_Node
set Hash_Node_Before[Index] = Hash_Max_Node
set Hash_Node_Next[Hash_Max_Node] = Index
set Hash_Min_Node = Index
set re = Index
endif
if re != const_ErrorOrNullNumber then
return re
endif
//在中间
set i = Index - 1
loop
exitwhen i < 0
if Hash_Node_Mission != const_ErrorOrNullNumber then
set next = Hash_Node_Next//暂时保存前面的Node的下一个Node
set Hash_Node_Next = Index
set Hash_Node_Before[Index] = i
set Hash_Node_Before[next] = Index
set Hash_Node_Next[Index] = next
return Index
endif
set i = i - 1
endloop
call BJDebugMsg( "数据也太多了吧~~都8192个了" )
call BJDebugMsg( "数据库都存不下了哦~~" )
call BJDebugMsg( "地图作者有点点懒哦~~" )
else //如果已有Node
if Index == Hash_Min_Node and Hash_Min_Node > 0 then//如果指向的是最小的
set Index = Index - 1
set Hash_Node_Before[Hash_Min_Node] = Index
set Hash_Node_Next[Index] = Hash_Min_Node
set Hash_Node_Before[Index] = Hash_Max_Node
set Hash_Min_Node = Index
return Index
else
if Index == Hash_Min_Node and Index == 0 then
set Index = const_Max_ArrayNumber - 1
if Hash_Max_Node < const_Max_ArrayNumber - 1 then
set Hash_Node_Next[Hash_Max_Node] = Index
set Hash_Node_Before[Index] = i
set Hash_Node_Before[Hash_Min_Node] = Index
set Hash_Node_Next[Index] = next
if Index > Hash_Max_Node then
set Hash_Max_Node = Index
elseif Index > Hash_Min_Node then
set Hash_Min_Node = Index
endif
return Index
endif
endif
set i = Index
loop
set next = i//暂时保存前面的Node的下一个Node
set i = Hash_Node_Before
if i < next - 1 then
set Index = next - 1
set Hash_Node_Next = Index
set Hash_Node_Before[Index] = i
set Hash_Node_Before[next] = Index
set Hash_Node_Next[Index] = next
if Index > Hash_Max_Node then
set Hash_Max_Node = Index
elseif Index > Hash_Min_Node then
set Hash_Min_Node = Index
endif
return Index
endif
endloop
endif
endif
return const_ErrorOrNullNumber
//一般是不会执行到这里的~~
endfunction
function Hash_Data_InitNode takes integer mission, integer key, integer word returns integer
local integer Index = Hash_Data_GetStreet( Hash_Data_ConvertNo( mission, key, word ) )
set Index = Hash_Data_CreateNode( Index )
if Index != const_ErrorOrNullNumber then
set Hash_Node_Mission[Index] = mission
set Hash_Node_Key[Index] = key
set Hash_Node_Word[Index] = word
return Index
else
call BJDebugMsg( "Can't Init A New Node~~!" )
endif
return const_ErrorOrNullNumber
endfunction
function Hash_Data_FlushNode takes integer Index returns nothing
local integer before = Hash_Node_Before[Index]
local integer next = Hash_Node_Next[Index]
if Hash_Node_Mission[Index] != const_ErrorOrNullNumber then
set Hash_Node_Number = Hash_Node_Number - 1
set Hash_Node_Before[next] = before
set Hash_Node_Next[before] = next
if Hash_Max_Node == Index then
set Hash_Max_Node = before
endif
if Hash_Min_Node == Index then
set Hash_Min_Node = next
endif
set Hash_Node_Mission[Index] = const_ErrorOrNullNumber
set Hash_Node_Key[Index] = 0
set Hash_Node_Word[Index] = 0
set Hash_Node_Before[Index] = 0
set Hash_Node_Next[Index] = 0
//Node部分清空完毕
endif
endfunction
function Hash_Data_RemoveNode takes integer mission, integer key, integer word returns nothing
local integer Index = Hash_Data_GetStreet( Hash_Data_ConvertNo( mission, key, word ) )
if Hash_Node_Mission[Index] != const_ErrorOrNullNumber then
call Hash_Data_FlushNode( Hash_Data_GetStreet( Hash_Data_ConvertNo( mission, key, word ) ) )
set Hash_Data_Int[Index] = 0
set Hash_Data_Real[Index] = 0.0
set Hash_Data_Str[Index] = null
set Hash_Data_Bool[Index] = false
//如果拓展也要清空
endif
endfunction
function Hash_Data_GetIndex takes integer mission, integer key, integer word returns integer
local integer Index = Hash_Data_GetStreet( Hash_Data_ConvertNo( mission, key, word ) )
local integer i = Index
local integer temp = Hash_Node_Before
//获得初步的Node位置。
if Hash_Node_Mission[Index] == mission and Hash_Node_Key[Index] == key and Hash_Node_Word[Index] == word then
//Index是正确的Node位置。
return Index
//elseif Hash_Node_Mission[Index] == 0 then
//return Hash_Data_CreateNode( Index )
else
loop
exitwhen i == temp
set temp = i
set i = Hash_Node_Before
if Hash_Node_Mission == mission and Hash_Node_Key == key and Hash_Node_Word == word then
return i
endif
endloop
endif
return const_ErrorOrNullNumber
endfunction[/codes]
还有一种解决冲突的方法，就是二次探查法（推荐）：
这种方法的基本思想就是从基点开始，不断地在数组里跳来跳去。而且还有规律~~
准确的说，是先跳到基点-1的Address，然后再跳到基点+1的Address，再+2*2=4，-2*2=4，+3*3=9，-3*3=9…………
如此这样，可以在很大一部分程度上，避免了冲突。
（这个相当于每个基点都有一个表）
但是由于一个Address有歧义性，所以是无法使用链表来增加查找时的效率。
不过这个算法本身就很好了，嗯~~不加链表和区的线性探查法的效率，大约是二次探查法的1/2（注意这不是准确数字）。
至于加链表和区的线性探查法的效率，这个…………很难比较…………o(╯□╰)o
（当然，求底法依然强力~~）
不多说，代码：
[codes=jass]globals
constant integer const_Max_ArrayNumber = 8192
constant integer const_ErrorOrNullNumber = -1
integer array Hash_Node_Mission//节点的missionkey(integer)
integer array Hash_Node_Key //节点的key(integer)
integer array Hash_Node_Word //节点的word(integer)
//上为节点的链表部分
integer array Hash_Data_Int
real array Hash_Data_Real
string array Hash_Data_Str
boolean array Hash_Data_Bool
//上为节点的存储数据部分（可拓展）
integer const_BottomHandleAddress = 0
endglobals
function Hash_Data_Init takes nothing returns nothing
local integer i = 0
loop
exitwhen i >= const_Max_ArrayNumber
set Hash_Node_Mission = -1
set i = i + 1
endloop
endfunction
function H2I takes handle h returns integer
return h
return 0
endfunction
function Hash_Data_H2I takes handle h returns integer
return H2I( h ) - const_BottomHandleAddress
endfunction
//如果想用Handle当mission,key,word中的一项，请用上面的函数的返回值当mission,key,word。
function Hash_Data_Init_Handle takes nothing returns nothing
local location loc = Location( 0.0, 0.0 )
set const_BottomHandleAddress = H2I( loc )
call RemoveLocation( loc )
set loc = null
endfunction
function Hash_Data_ConvertNo takes integer mission, integer key, integer word returns integer
return mission + key + word
endfunction
function Hash_Data_ConvertIndex takes integer No returns integer
return ModuloInteger( No, const_Max_ArrayNumber )
endfunction
function Hash_Data_CreateNode takes integer index returns integer
local integer lift_or_right = -1
local integer add = 1
local integer i = index - 1
if Hash_Node_Mission[index] == const_ErrorOrNullNumber then
return index
endif
loop
if Hash_Node_Mission == const_ErrorOrNullNumber then
return i
endif
set lift_or_right = -lift_or_right
if lift_or_right == -1 then
set add = add + 1
exitwhen add == ( const_Max_ArrayNumber - 1 ) / 2
endif
set i = index + add * add * lift_or_right
if i < 0 then
set i = i + const_Max_ArrayNumber
elseif i >= const_Max_ArrayNumber then
set i = i - const_Max_ArrayNumber
endif
endloop
return const_ErrorOrNullNumber
//一般是不会执行到这里的~~
endfunction
function Hash_Data_InitNode takes integer mission, integer key, integer word returns integer
local integer Index = Hash_Data_ConvertIndex( Hash_Data_ConvertNo( mission, key, word ) )
set Index = Hash_Data_CreateNode( Index )
if Index != const_ErrorOrNullNumber then
set Hash_Node_Mission[Index] = mission
set Hash_Node_Key[Index] = key
set Hash_Node_Word[Index] = word
return Index
else
call BJDebugMsg( "Can't Init A New Node~~!" )
endif
return const_ErrorOrNullNumber
endfunction
function Hash_Data_FlushNode takes integer Index returns nothing
if Hash_Node_Mission[Index] != const_ErrorOrNullNumber then
set Hash_Node_Mission[Index] = const_ErrorOrNullNumber
set Hash_Node_Key[Index] = 0
set Hash_Node_Word[Index] = 0
//Node部分清空完毕
endif
endfunction
function Hash_Data_RemoveNode takes integer mission, integer key, integer word returns nothing
local integer Index = Hash_Data_ConvertIndex( Hash_Data_ConvertNo( mission, key, word ) )
if Hash_Node_Mission[Index] != const_ErrorOrNullNumber then
call Hash_Data_FlushNode( Hash_Data_ConvertNo( mission, key, word ) )
set Hash_Data_Int[Index] = 0
set Hash_Data_Real[Index] = 0.0
set Hash_Data_Str[Index] = null
set Hash_Data_Bool[Index] = false
//如果拓展也要清空
endif
endfunction
function Hash_Data_GetIndex takes integer mission, integer key, integer word returns integer
local integer index = Hash_Data_ConvertIndex( Hash_Data_ConvertNo( mission, key, word ) )
local integer lift_or_right = -1
local integer add = 1
local integer i = index - 1
if Hash_Node_Mission[index] == mission and Hash_Node_Key[index] == key and Hash_Node_Word[index] == word then
return index
endif
loop
if Hash_Node_Mission == mission and Hash_Node_Key == key and Hash_Node_Word == word then
return i
endif
set lift_or_right = -lift_or_right
if lift_or_right == -1 then
set add = add + 1
exitwhen add == ( const_Max_ArrayNumber - 1 ) / 2
endif
set i = index + add * add * lift_or_right
if i < 0 then
set i = i + const_Max_ArrayNumber
elseif i >= const_Max_ArrayNumber then
set i = i - const_Max_ArrayNumber
endif
endloop
return const_ErrorOrNullNumber
endfunction[/codes]
最后我介绍一种我认为不太靠谱的方法：
双散列法：
使用双散列法时，需要两个Hash函数：
1.Hash()
2.ReHash()
在发生冲突时，将key赋给ReHash，得到下一个index。
下一个index（设为p）的取值与key的值有关，p<8192，且与8192互质。
基本思想就是应用伪随机探查方法，使用一个伪随机数产生器（ReHash()），可以“跳”到下一个index的位置。
（嗯，我认为不太靠谱，所以就不写代码了）
比较3个来说，我认为二次探查法是比较好的。
其实大家没必要去比较这三个方法中哪个比较快什么的。
这些方法其实都差不多。
不管是什么Hash函数，也只是在平均查找效率上做手脚，所有的Hash函数在遇到了最坏的情况时，发挥的都是很差的~~ |
评分
-
查看全部评分
|
窥视卡
雷达卡
发表于 2009-3-2 12:50:32
提升卡
置顶卡
沉默卡
喧嚣卡
±????¨
千斤顶
???í?¨
，其实啊，DataSystem在Ga早就不是稀罕东西了，struct知道原理的话直接自己写吧（Hmmm...大家看 血戮魔动冰 已经把这个东西提取出来用了），拉链Hash法也是超简单的，只是因为Jass不支持二维数组才搞得实现起来有点曲折。呐，总之了，还是看大家自己的应用了。
