Hash查找法在Keil C51中的实现

摘要：散列(hash)是一种重要的存储方法,也是一种常见的查找方法。它是指在记录的存储位置和它的关键字之间建立一个确定的对应关系。本文以射频卡门禁控制器为例,说明用射频卡卡号作为关键字,用Hash查找法确定此卡能否开门,并给出对应的Keil C51程序。

    单片机应用系统中,经常要涉及到数据的存储和查找。以射频卡门禁系统为例,见图1。系统由51系列单片机、射频卡(RF卡)读卡电路、存储单元24C256、继电器等部分组成。其基本原理为：用户刷卡后,RF卡读卡电路读出卡号,通过I/O口线送入单片机。单片机收到卡号后,在存储单元中查找此卡是否允许开门。如允许,则命令继电器动作,打开电磁门锁：如不允许,则返回。
 
图1 射频卡门禁系统
    在内存中查找卡号有多种方法,最简单的有线性查找法,即从存储单元内第一个记录起与关键字比较,一直到记录与关键字匹配。时间复杂程度为O(n),记录数越多,比较过程耗时越长。一般记录数为100～200时较合适,如在系统内存储1000～2 000条记录,则用户在刷卡开门时,因比较的次数较多,等待时间较长,将难以忍受。
    对于记录数较多(1000～2 000)的场合,可以采用对分法查找。此方法的时间复杂程度为O(log2n),2000个左右的记录只需查找10～11次即可完成,效率大大提高。只是此法需要将记录事先排序,随机增加一个记录或养活一个记录将较麻烦。
    二叉排序树的方法可以兼有对分法查找的高效率和随机插入记录、删除记录的便利。但在编程中,由于要使用到指针变量,KeilC51要生成较大的目标代码。
    Hash查找法在实践中被证实是最快的一种查找方法,它的时间复杂度为O(1),即几乎只要比较一次就可确定比较结果。它的基本思想是以空
间换时间,需要数据存储器容量大,好在当前存储器的价格并不贵,采用大容量的存储并不会使系统成本增加多少。
    Hash查找法又称散列查找,是一种重要的存储和查找方法。它是指在记录的存储位置和它的关键字之间建立一个确定的对应关系,使每个关
键字和存储器中的唯一的存储位置相对应。将记录的关键字与记录的存储位置对应起来的关系称为Hash函数。在查找时,如关键字是Key,只需要根据对应关系计算出关键字Key对应的值H(Key),就可得到记录的存储位置,这个位置称为Hash地址。以射频卡门禁系统为例,开门卡的卡
号为关键字,通过文中给定的一种运算即可直接得到对应的记录的存储位置(Hash地址),从中取出是否可以开门的信息。
    使用Hash查找法,会产生对于不同的关键字其Hash函数计算的Hash地址相同的情况,这种情况称为冲突。在Hash查找法中冲突是不可避
免的。关键的问题是如何构造Hash函数,使所有关键字对应的Hash地址均匀地分布在整个地址空间,尽可能少地减少活冲突。同时一旦发生冲
突要有足够的办法解决。本文采用折叠法来构成Hash函数,用线性探测法解决一旦发生的冲突。其细节可见参考文献[1]、[2]。
    当前单片机应用的普遍趋势是采用片内ROM,采用SPI或I2C等串行方式扩展外部设备,所以文中采用的存储器是I2C总线的24C256,共32K字节。其中分配给Hash查找的存储空间是16K,每记录8个字节,共2000条记录,即可存储2000个开门卡卡号。(24C256中剩余的地址留作它用)每条记录分配如下：

0     1    2   3   4    5   6   7
55 16 92 64 02 XX XX

    第0个字节0X55,表示该地址已有记录。
    第1个字节到第4个字节存放后8位卡号,BCD方式。
    第5个字节～第7个字节留作参数,如可控制开门卡在什么时间段内可以开门,也可控制该卡不同的权限。
    记录从0000号单元开始存放。
    卡号存放在数组d[0]～d[9]中,它是一个10位的10进制数,如卡号是0016926402,则d[0]=0,d[1]=0,d[2]=1,d[3]=6,d[4]=9……。折叠法把关键字分割成位数相同的几部分,然后取这几部分叠加其和再取2000的模(舍去进位)作为哈希地址。
  1692
+ 6402
————H(key)=94
  8094
程序中作如下运算
1000 d[2]+100*d[3]+10*d[4]+d[5]+1000*d[6]+100*d[7]+10* [8]+d[9]=1000*(d[2]+d[6])+100*(d[3]+d[7])+10*(d[4]+d[8])+d[5]+d[9]这样的运算体现在hashfunc()函数中,hashfunc()函数的功能为根据10位卡号计算出对应的hash地址。

uint hashfunc()   
{   
  uint hashtem;   
  hashtem=1000*(d[2]+d[6])+100*(d[3]+d[7])+10*(d[4]+d[8]+d[5]+d[9];   
  hashtem =hashtem%2000;   
  retun(hashtem);   
}

    本文所附C51程序中要用到其他一些函数,限于篇幅,这里不再申明,请参考main()程序中相应的注释。程序是以位变量setflag控制程序分支,setflag=1表明要将读到的卡号存储(函数save())到相应的hash地址中,setflag=0表明要将读到的卡号作为关键字,在内存中进行hash查找,找到相匹配的纪录。KeilC51程序如下：

Main()   
{   
  uint hashaddr,IICaddr;   
  uchar status,i,k,cardmen,cardnum,seterr;   
  reterr=0;   
start:   
  Rfread(); //读卡,卡号存d[0]-d[9]   
  Setflag=checkcard(); //检测是否是设置卡,是设置卡返回1,是开门卡返回0。   
  if(setflag==0)   
  {   
    k=0;   
    hashaddr=hashfunc();//对关键字进行Hashing运算,得到Hashing地址。   
    while(k<10)   
    {   
      IICaddr=(hashaddr+k)*8;//从Hashing地址换算到实际内存地址。   
      Status=IICRead(IICaddr);   
      if(status==0x55)   
      {   
        for(i=1;i<5;i++)   
        {   
          cardmen=IICRead(IICaddr+i);//取出内存中卡号。   
          cardnum=d[i*2]*16+d[1+i*2];//与当前的卡号比较,   
          if(cardmen!=cardnum)   
            break;//           }   
        if(i==5)   
        {   
          open(3);//开门3秒   
          goto start;   
        }   
      }   
      k++;//进行10次探测。       }   
  }   
  else  
  {   
    k=0;   
    hashaddr=hashfunc();//对关键字进行Hashing运算,得到Hashing地址。   
    while(k<10)。   
    //进行10次线性探测,10次不成功．不再进行探测,令错误标记errflag=1       {   
      IICaddr=(hashaddr+k)*8;//从Hashing地址换算到实际内存地址   
      status=IICRead(IICaddr);   
      if(status==0x55)   
      {   
        for(i=1;i<5;i++)   
        {   
           cardmem=IICRead(IICaddr+i);   
           cardnum=d[i*2]*16+d[1+i*2];   
           if(eardmem!=cardnum)   
             break;   
           if(i==5)   
             goto start;//内存中已有本卡的纪录,不须再写入。   
           k++;   
         }   
         else  
         {   
           if(k<8)   
             save(IICaddr);//将一条记录存入。   
           else seterr=1;   
           goto start;   
         }   
      }   
   }   
}

参考文献：
[1] 严蔚敏,吴伟民．数据结构(C语言版)[M]．北京：清华大学出版社．
[2] 李云清．数据结构(C语言版)[M]．北京：人民邮电出版社.
[3] 马忠梅. 单片机的C语言应用程序设计[M]．北京：北京航空航天大学出版社.