散列表快速查找算法在单片机系统中的应用

1、散列表快速查找算法在单片机系统中的应用    0引言实时性要求很高的单片机系统往往要采用复杂的数据结构算法来实现动态查找表的查找。而在数据结构(线性表或树)中的记录数目很大时，由于关键字的比较次数多，查找速度慢，因而难以实现系统的实时性。这样，创建和选择一个好的数据查找算法就很关键。本文以澡堂消费系统为例，介绍了一种散列表快速查找算法在单片机系统中的应用方法。1散列表的引入散列表又称为哈希表，是一种重要的存储方式和检索方法。基于散列表的查找称散列0 引言实时性要求很高的单片机系统往往要采用复杂的数据结构算法来实现动态查找表的查找。而在数据结构(线性表或树

2、)中的记录数目很大时，由于关键字的比较次数多，查找速度慢，因而难以实现系统的实时性。这样，创建和选择一个好的数据查找算法就很关键。本文以澡堂消费系统为例，介绍了一种散列表快速查找算法在单片机系统中的应用方法。1散列表的引入散列表又称为哈希表，是一种重要的存储方式和检索方法。基于散列表的查找称散列查找，是一种快速查找方法，只要设计合理，其计算量并不大。一般的线性表和树中，记录在结构中的相对位置是随机的，即和记录的关键字不存在确定的关系。因此，在结构中查找记录时，需进行一系列和关键字(key)的比较，查找的效率取决于比较的次数。理想的情况是能直接找到需要的记录，因此，必须在记录的存储位置和它的关键

3、字之间建立某种确定的对应关系H，以使每个关键字和结构中唯一的存储位置相对应。这样，在查找时，只要根据对应关系H找到给定值key的像H(key)。若结构中存在和关键字相等的记录，且必定在H(key)的存储地址上，则这个对应关系H即为哈希(Hash)函数，按这个思想建立的表即为散列表。哈希函数是从关键字集合到地址集合的映像。通常，关键字集合比较大，它的元素包括所有可能的关键字，而地址集合的元素仅为哈希表中的地址值。不同的关键字可能映像到相同的哈希地址，这种现象称为冲突，生成相同哈希地址的关键字称为同义词。一般情况下，哈希函数是一个压缩映像，这就不可避免地会产生冲突(除非数据很少)，因而只能采取措施

4、尽量避免冲突或寻找解决冲突的办法。冲突的频繁程度除了与H相关外，还与表的填满程度相关。设m和n分别表示表长和表中填入的结点数，那么，可将=nm定义为散列表的装填因子(Load Factor)。越大，表越满，冲突的机会也越大，通常取1。处理冲突常用的方法有开放定址法、再哈希法及链地址法等。     由于单片机的资源有限，所以在选择哈希函数和防冲突机制时，应充分考虑单片机的运算能力和存储空间。本系统把当前消费记录存储到带I2C接口的片外存储器24LC256中，记录中包含有卡号(3个字节)和刷卡时间等字段。表1所列是一个IC卡的费散列表结构。2哈希函数的构造澡

5、堂计时收费的时间通常是以消费者消费的时间进行计算的。这种计费方式要求消费者进出澡堂时各刷一次卡，以两次刷卡的时间间隔计算消费费用。当消费者刷卡时，读写器将读得的卡号(关键字)与表中存储的卡号进行比较。若有相同卡号的记录，且标志位为000的记录，则认为该消费者是第二次刷卡(出澡堂完成消费)，计算两次刷卡的时间间隔即可得到消费费用，结帐后再修改该记录；若查找不到相同卡号的记录，或卡号相同而标志位不为000时，则认为该消费者是第一次刷卡(进入澡堂消费)，此时，系统会在表中添加一条新的记录。由于进出澡堂的人是动态变化的，要实现计时收费，重要的一点就是要能方便的实现消费记录的查找和修改，其中记录的查找最

6、为关键。由于查找表是系统在运行过程中动态生成的，所以如何方便快捷地实现查找是系统的关键。"好"的哈希函数要求计算简单快速，并且可使一组关键字的哈希地址等概率地分布在整个地址区间中，以使冲突最小化。构造哈希函数的常用方法有直接定址法、数字分析法、平方取中法、折叠法、除留余数法和随机数法。本系统采用除留余数法(取关键字被某个不大于哈希表表长m的数p除后所得余数为哈希地址)。该方法记录地址为记录存储的实际物理地址，共15位，可由下式计算：记录地址=存储块号×8+0x0500。一般情况下，可以选p为质数或不包含小于20的质因素的合数。由于表长m为2048，所以，只要质数p

7、小于2048即可(选p=173)。操作时，先求3个字节卡号的累加和，再将累加和对173取模作为哈希地址。如卡号(Key)为0x15555D，则哈希地址H(key)=(0x15+0x55+0x5d)MOD173=26。表1中的哈希地址为26的卡号还有0xC7和0xCOB2AF，这3个卡号为同义词，它们对应的记录存储在同一线性链表中。记录的内容通常包括下一条记录的存储块号、卡号、卡类型、功能字节和功能标志位(见表1)。其中，下一条记录存储块号和标志位一共占用2个字节，低11位(D0D10)为存储块号(范围从0到2047)，与头链表对应。记录的是链表中下一条记录的存储块号(卡类别相同)，如果没有下一

8、条记录，则存储块号为2048，表示空指针。高3位(D15、D14、D13)为功能标志位，     (其中000表示计时收费开始，001表示计时消费结束或表示固定消费，100表示加卡，101表示开户，110表示销户，011、111和010可作为其他拓展功能。卡号是关键字，占3个字节，由6位16进制数组成。由于卡类型是对p取模，最大不超过255，所以它占1个字节。通过功能字节可在计时模式下记录消费者进入澡堂刷卡时的时间，该功能占2个字节(高字节存储时，低字节存储分)。当计时消费结束后，记录消费金额(高字节记录元，低字节记录角)。3冲突的解决本文采用链地址法处