看流星社区

 找回密码
 注册账号
查看: 2920|回复: 2

[Delphi] 【对武林、完美中怪物ID以及很多处用到的hash运算,请一起探讨】

[复制链接]

该用户从未签到

发表于 2011-3-31 09:46:02 | 显示全部楼层 |阅读模式
我也不太明白。我找了一些资料看起来比较清晰。我会不断补充我对他的理解和看法。希望大家都指教一下

哈希表支持的运算主要有:初始化(makenull)、哈希函数值的运算(h(x))、插入元素(insert)、查找元素(member)。
========================初始化(makenull)========================
  设插入的元素的关键字为 x ,A 为存储的数组。
  初始化比较容易,例如
  const empty=maxlongint; // 用非常大的整数代表这个位置没有存储元素
     p=9997;      // 表的大小
  procedure makenull;
   var i:integer;
   begin
    for i:=0 to p-1 do
     A[ i ]:=empty;
   End;

========================函数值的运算(h(x))========================

function h(x:longint):Integer;
   begin
    h:= x mod p;
   end;

========================定位函数 locate========================

我们注意到,插入和查找首先都需要对这个元素定位,即如果这个元素若存在,它应该存储在什么位置,因此加入一个定位的函数 locate  
  function locate(x:longint):integer;
   var orig,i:integer;
   begin
    orig:=h(x);
    i:=0;
    while (i<S)and(A[(orig+i)mod S]<>x)and(A[(orig+i)mod S]<>empty) do
     inc(i);  
     //当这个循环停下来时,要么找到一个空的存储单元,要么找到这个元
     //素存储的单元,要么表已经满了
    locate:=(orig+i) mod S;
   end;
=====================插入元素========================
  procedure insert(x:longint);
   var posi:integer;
   begin
    posi:=locate(x);      //定位函数的返回值
    if A[posi]=empty then A[posi]:=x
          else error; //error 即为发生了错误,当然这是可以避免的
   end;  

========================查找元素========================

  查找元素是否已经在表中
  procedure member(x:longint):boolean;
    var posi:integer;  
    begin
     posi:=locate(x);
     if A[posi]=x then member:=true
             else member:=false;
    end;

该用户从未签到

发表于 2011-3-31 09:46:17 | 显示全部楼层
散列表的最主要的东西就是散列函数的选择,大多数使用的都是取模运算,也可以根据表中要存储的元素的特征自己去设计散列函数,
还有就是使用散列的根本用意就是速度,所以这里不要使用数组,用双链表实现,如果闲烦,你也可以使用TList去实现,都比数组要快.

该用户从未签到

发表于 2013-4-2 21:11:14 | 显示全部楼层
能告诉我下完美国际的怪物数组是怎么找到的吗?
点击按钮快速添加回复内容: 支持 高兴 激动 给力 加油 苦寻 生气 回帖 路过 感恩
您需要登录后才可以回帖 登录 | 注册账号

本版积分规则

小黑屋|手机版|Archiver|看流星社区 |网站地图

GMT+8, 2024-3-29 07:04

Powered by Kanliuxing X3.4

© 2010-2019 kanliuxing.com

快速回复 返回顶部 返回列表