Location拉链hash法

疯人￠衰人

我不是学计算机的……
再次声明下……！

这么说是因为如果诸位计算机专业的同学发现我这篇帖子有什么说明上的错误，特别是用错名称、定义的话，请诸位同学谅解。恩恩，应该是可以原谅的吧……

虽然我跟血戮不是最早提出使用Location实现链表的，但是终于我们还是对其下了很大的心力研究，血戮跟各位一样，都是按照一些计算机书籍学习的，使用的方法大多都是理论化的东西，比如hash、二叉树……而我是实践型的，我不会考虑那些教材上的经典方法，因为不知道-_-! 。对于我自己来说，只要能够在允许的运行效率下完成功能就行，所以很多时候我的想法比较“野”，不然怎么会想创建连续handle呢？……

恩恩，用Location实现拉链hash法，这个的思路是在端午回家时想到的，虽然cccty1l 在还是说数组存储系统、还是说数组存储系统续两个帖子里详细介绍了拉链hash的实现方法，但是我根本没看懂……甚至以为拉链法是cccty1l 发明的，误会误会……

放假时借了本《实用数据结构》，才知道什么是真正的拉链hash法，不过cccty1l 的帖子还是看的一知半解……

恩恩废话结束了
下面就是代码和说明：

[jass]
globals
location udg_l
integer  udg_i
integer array udg_HashTable
endglobals
function LinearListInput takes location l,real r returns location
    //Location链表的存入，（栈式，后人先出）
    local location udg_l = null
    local integer udg_i = 0
    local integer TempInt = 0
    set udg_l = l
    set TempInt = udg_i
    set udg_l =Location(r,I2R(TempInt))
    return udg_l
endfunction
function LinearListOutput takes location l,integer i returns real
    //读取Location链表l的第i个结点存储的值（表头的i为1）
    local location udg_l = null
    local integer udg_i = 0
    set udg_l = l
    loop
        exitwhen i == 1
        set udg_i = R2I(GetLocationY(udg_l))
        if udg_i == 0 then
             //出错时的反馈，return多少都行
            return -2000000000   
        endif                     
        set i = i - 1
    endloop     
    return GetLocationX(udg_l)
endfunction
function LinearListDestroy takes location l returns nothing
    //销毁Location链表l
    local location udg_l = null
    local integer udg_i = 0   
    local integer TempInt = 0
    loop
        set TempInt = R2I(GetLocationY(udg_l))
        call RemoveLocation(udg_l)
        set udg_i = TempInt
        exitwhen TempInt == 0
    endloop      
endfunction
function HashInput takes integer index,location l returns nothing
    //将创建好的Location链表加入到index为关键字的Hash表中
    local location udg_l = null
    local integer udg_i = 0
    local integer TempIndex = 0
    set TempIndex = index - index/8192*8192
    set udg_l = l
    set udg_l = Location(I2R(index),I2R(udg_i))
    set udg_l = Location(I2R(udg_i),I2R(udg_HashTable[TempIndex]))
    set udg_HashTable[TempIndex] = udg_i
endfunction
function HashOutput takes integer index returns location
    //通过关键字index读取对应的Location链表
    local location udg_l = null
    local integer udg_i = 0  
    local integer TempIndex = 0
    local location TempLoc = null
    set TempIndex = index - index/8192*8192  
    set udg_i = udg_HashTable[TempIndex]
    loop
        if udg_i == 0 then
            set TempLoc = null
            return null
        endif
        set TempLoc =udg_l
        set udg_i = R2I(GetLocationX(udg_l))
        exitwhen index == R2I(GetLocationX(udg_l))
        set udg_i = R2I(GetLocationY(TempLoc))  
    endloop
    set udg_i = R2I(GetLocationY(udg_l))
    set TempLoc = null
    return udg_l
endfunction
function HashDestroy takes integer index returns nothing
    //释放对应关键字为index的存储空间
    local location udg_l = null
    local integer udg_i = 0  
    local integer TempInt = 0
    local integer TempIndex = 0
    local location TempLocA = null
    local location TempLocB = null   
    set TempIndex = index - index/8192*8192  
    set udg_i = udg_HashTable[TempIndex]
    if udg_i == 0 then
        return
    endif
    set TempInt = R2I(GetLocationY(udg_l))
    set TempLocA = udg_l
    set udg_i = R2I(GetLocationX(udg_l))
    if index == R2I(GetLocationX(udg_l)) then
        if TempInt == 0 then
            set udg_HashTable[TempIndex] = 0
        else
            set udg_HashTable[TempIndex] = R2I(GetLocationY(TempLocA))
        endif
        call RemoveLocation(udg_l)
        call RemoveLocation(TempLocA)
        set TempLocA = null
        return
    endif
    if TempInt == 0 then
        set TempLocA = null
        return
    endif
    set udg_i = TempInt
    loop
        if udg_i == 0 then
            set TempLocA = null  
            set TempLocB = null
            return
        endif
        set TempLocB = TempLocA
        set TempLocA = udg_l
        set udg_i = R2I(GetLocationX(udg_l))
        exitwhen index == R2I(GetLocationX(udg_l))
        set udg_i = R2I(GetLocationY(TempLocA))  
    endloop
    call MoveLocation(TempLocB,GetLocationX(TempLocB),GetLocationY(TempLocA))
    call RemoveLocation(udg_l)
    call RemoveLocation(TempLocA)
    set TempLocA = null  
    set TempLocB = null
endfunction
[/jass]

其实整个系统实际上是一个类似struct的东西，也就是将一系列东西绑定到一起，用一个整数index索引。只是这个系统的存储结构使用了拉链hash的方法。

这个系统与使用数组的拉链法，还是有很大差别的，最明显的就是这个系统并不是给出一个不冲突的index，再用数组存储，而是直接存储内容。

前三个function：LinearListInput、LinearListOutput、LinearListDestroy实际上是对Location单链链表的输入输出和删除。恩，为了提高效率，使用的是类似栈的方法（后人先出）。这个系统存储内容就是存储到这Location单链链表上，关于Location链表，大家可以看血戮的帖子一种新的存储结构和HASH改进算法及HandleTable运用 。

后三个function：HashInput、HashOutput、HashDestroy则是真正使用了拉链法的存储结构了。

这个结构使用一个数组（udg_HashTable）作为存储的表，这个实际上也可以使用初始化创建的Location单链链表（连续handle的），这样可以使同时使用的存储位置超过8192，但是那并没有什么意义，反而减少了效率。

hash方法跟正常的hash一样，求index=handle-handle/8192*8192，也就是求余。只是在冲突时将后创建的作为一个结点添加到对应index的链表中去。这就是所谓的拉链法。

对比使用数组的拉链法：恩，在我感觉上，如果要使用数量不确定个较短的链表时，用数组实现不如用Location实现，Location链表在对结点的插入和删除方面要比数组方便。缺点是长链表的读取速度很差，不过因为是hash的链表，一般不可能出现过多的冲突index，毕竟如果index是对handle进行hash的话，两个冲突的index对应的handle最小要差8192
（差为8192的倍数时，两个index=handle-handle/8192*8192才会冲突），所以除非排泄很不好，并且创建的handle变量很多才可能会使Location链表的结点变得很多，毕竟10个结点就说明至少handle表中有81920个元素……

很不幸的是Location存储的实数时，当整数部分超过7位时，小数部分就会被省略，而整数部分的有效数字也不过是8位左右。因为这个问题我不得不多使用了一个Location。效率差了很多（一倍）。

有个测试的演示
大体上的应用方法看那里就行了

Flyingsnow

支持一切算法研究   [s:187]

lunaflywar

支持研究，但是只用GC和DataSys的人路过
效率难以保证吧，而且地图也不需要那么大的数据量

疯人￠衰人

引用第2楼lunaflywar于2009-05-31 11:31发表的  :
支持研究，但是只用GC和DataSys的人路过
效率难以保证吧，而且地图也不需要那么大的数据量

为什么效率不能保证呢？

血戮魔动冰

恩恩~~早就想到这个方法了~其实还是效率比较慢而已…………哈~~

疯人￠衰人

确实……

血戮魔动冰

倒是如果在一开始就创建10000000（打个比方）个Location的话，是不是会更快些呢？恩~
倒是觉得如果能用庞大的locationTable映射数组index值的话，应该会和Hash不相上下吧，毕竟hash表写起来语句确实比GetLocationX这样复杂多了~~
不是说过吗，if的开销为1什么的~~~
不过这样也没必要，毕竟还是限制在8192里……哎……哎哎哎…………

疯人￠衰人

能够实现任意创建连续handle就好了
这样也许能够提高效率？
如果成功到话
struct的实现就简单了
不过很多内容还是要用location保存
……

血戮魔动冰

是啊~不过没有那么搞高效的Bug存在呢~~

疯人￠衰人

这个就要自己试验了