摘要：散列(hash)是一種重要的存儲(chǔ)方法,也是一種常見的查找方法。它是指在記錄的存儲(chǔ)位置和它的關(guān)鍵字之間建立一個(gè)確定的對(duì)應(yīng)關(guān)系。本文以射頻卡門禁控制器為例,說(shuō)明用射頻卡卡號(hào)作為關(guān)鍵字,用Hash查找法確定此卡能否開門,并給出對(duì)應(yīng)的Keil C51程序。

單片機(jī)應(yīng)用系統(tǒng)中,經(jīng)常要涉及到數(shù)據(jù)的存儲(chǔ)和查找。以射頻卡門禁系統(tǒng)為例,見圖1。系統(tǒng)由51系列單片機(jī)、射頻卡(RF卡)讀卡電路、存儲(chǔ)單元24C256、繼電器等部分組成。其基本原理為：用戶刷卡后,RF卡讀卡電路讀出卡號(hào),通過(guò)I/O口線送入單片機(jī)。單片機(jī)收到卡號(hào)后,在存儲(chǔ)單元中查找此卡是否允許開門。如允許,則命令繼電器動(dòng)作,打開電磁門鎖：如不允許,則返回。

圖1 射頻卡門禁系統(tǒng)
在內(nèi)存中查找卡號(hào)有多種方法,最簡(jiǎn)單的有線性查找法,即從存儲(chǔ)單元內(nèi)第一個(gè)記錄起與關(guān)鍵字比較,一直到記錄與關(guān)鍵字匹配。時(shí)間復(fù)雜程度為O(n),記錄數(shù)越多,比較過(guò)程耗時(shí)越長(zhǎng)。一般記錄數(shù)為100～200時(shí)較合適,如在系統(tǒng)內(nèi)存儲(chǔ)1000～2 000條記錄,則用戶在刷卡開門時(shí),因比較的次數(shù)較多,等待時(shí)間較長(zhǎng),將難以忍受。
對(duì)于記錄數(shù)較多(1000～2 000)的場(chǎng)合,可以采用對(duì)分法查找。此方法的時(shí)間復(fù)雜程度為O(log2n),2000個(gè)左右的記錄只需查找10～11次即可完成,效率大大提高。只是此法需要將記錄事先排序,隨機(jī)增加一個(gè)記錄或養(yǎng)活一個(gè)記錄將較麻煩。
二叉排序樹的方法可以兼有對(duì)分法查找的高效率和隨機(jī)插入記錄、刪除記錄的便利。但在編程中,由于要使用到指針變量,KeilC51要生成較大的目標(biāo)代碼。
Hash查找法在實(shí)踐中被證實(shí)是最快的一種查找方法,它的時(shí)間復(fù)雜度為O(1),即幾乎只要比較一次就可確定比較結(jié)果。它的基本思想是以空
間換時(shí)間,需要數(shù)據(jù)存儲(chǔ)器容量大,好在當(dāng)前存儲(chǔ)器的價(jià)格并不貴,采用大容量的存儲(chǔ)并不會(huì)使系統(tǒng)成本增加多少。
Hash查找法又稱散列查找,是一種重要的存儲(chǔ)和查找方法。它是指在記錄的存儲(chǔ)位置和它的關(guān)鍵字之間建立一個(gè)確定的對(duì)應(yīng)關(guān)系,使每個(gè)關(guān)
鍵字和存儲(chǔ)器中的唯一的存儲(chǔ)位置相對(duì)應(yīng)。將記錄的關(guān)鍵字與記錄的存儲(chǔ)位置對(duì)應(yīng)起來(lái)的關(guān)系稱為Hash函數(shù)。在查找時(shí),如關(guān)鍵字是Key,只需要根據(jù)對(duì)應(yīng)關(guān)系計(jì)算出關(guān)鍵字Key對(duì)應(yīng)的值H(Key),就可得到記錄的存儲(chǔ)位置,這個(gè)位置稱為Hash地址。以射頻卡門禁系統(tǒng)為例,開門卡的卡
號(hào)為關(guān)鍵字,通過(guò)文中給定的一種運(yùn)算即可直接得到對(duì)應(yīng)的記錄的存儲(chǔ)位置(Hash地址),從中取出是否可以開門的信息。
使用Hash查找法,會(huì)產(chǎn)生對(duì)于不同的關(guān)鍵字其Hash函數(shù)計(jì)算的Hash地址相同的情況,這種情況稱為沖突。在Hash查找法中沖突是不可避
免的。關(guān)鍵的問(wèn)題是如何構(gòu)造Hash函數(shù),使所有關(guān)鍵字對(duì)應(yīng)的Hash地址均勻地分布在整個(gè)地址空間,盡可能少地減少活沖突。同時(shí)一旦發(fā)生沖
突要有足夠的辦法解決。本文采用折疊法來(lái)構(gòu)成Hash函數(shù),用線性探測(cè)法解決一旦發(fā)生的沖突。其細(xì)節(jié)可見參考文獻(xiàn)[1]、[2]。
當(dāng)前單片機(jī)應(yīng)用的普遍趨勢(shì)是采用片內(nèi)ROM,采用SPI或I2C等串行方式擴(kuò)展外部設(shè)備,所以文中采用的存儲(chǔ)器是I2C總線的24C256,共32K字節(jié)。其中分配給Hash查找的存儲(chǔ)空間是16K,每記錄8個(gè)字節(jié),共2000條記錄,即可存儲(chǔ)2000個(gè)開門卡卡號(hào)。(24C256中剩余的地址留作它用)每條記錄分配如下：

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

第0個(gè)字節(jié)0X55,表示該地址已有記錄。
第1個(gè)字節(jié)到第4個(gè)字節(jié)存放后8位卡號(hào),BCD方式。
第5個(gè)字節(jié)～第7個(gè)字節(jié)留作參數(shù),如可控制開門卡在什么時(shí)間段內(nèi)可以開門,也可控制該卡不同的權(quán)限。
記錄從0000號(hào)單元開始存放。
卡號(hào)存放在數(shù)組d[0]～d[9]中,它是一個(gè)10位的10進(jìn)制數(shù),如卡號(hào)是0016926402,則d[0]=0,d[1]=0,d[2]=1,d[3]=6,d[4]=9……。折疊法把關(guān)鍵字分割成位數(shù)相同的幾部分,然后取這幾部分疊加其和再取2000的模(舍去進(jìn)位)作為哈希地址。
1692
+ 6402
————H(key)=94
8094
程序中作如下運(yùn)算
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]這樣的運(yùn)算體現(xiàn)在hashfunc()函數(shù)中,hashfunc()函數(shù)的功能為根據(jù)10位卡號(hào)計(jì)算出對(duì)應(yīng)的hash地址。

uinthashfunc(){uinthashtem;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程序中要用到其他一些函數(shù),限于篇幅,這里不再申明,請(qǐng)參考main()程序中相應(yīng)的注釋。程序是以位變量setflag控制程序分支,setflag=1表明要將讀到的卡號(hào)存儲(chǔ)(函數(shù)save())到相應(yīng)的hash地址中,setflag=0表明要將讀到的卡號(hào)作為關(guān)鍵字,在內(nèi)存中進(jìn)行hash查找,找到相匹配的紀(jì)錄。KeilC51程序如下：

Main(){uinthashaddr,IICaddr;ucharstatus,i,k,cardmen,cardnum,seterr;reterr=0;start:Rfread();//讀卡,卡號(hào)存d[0]-d[9]Setflag=checkcard();//檢測(cè)是否是設(shè)置卡,是設(shè)置卡返回1,是開門卡返回0。if(setflag==0){k=0;hashaddr=hashfunc();//對(duì)關(guān)鍵字進(jìn)行Hashing運(yùn)算,得到Hashing地址。while(k<10){IICaddr=(hashaddr+k)*8;//從Hashing地址換算到實(shí)際內(nèi)存地址。Status=IICRead(IICaddr);if(status==0x55){for(i=1;i<5;i++){cardmen=IICRead(IICaddr+i);//取出內(nèi)存中卡號(hào)。cardnum=d[i*2]*16+d[1+i*2];//與當(dāng)前的卡號(hào)比較,if(cardmen!=cardnum)break;//}if(i==5){open(3);//開門3秒gotostart;}}k++;//進(jìn)行10次探測(cè)。}}else{k=0;hashaddr=hashfunc();//對(duì)關(guān)鍵字進(jìn)行Hashing運(yùn)算,得到Hashing地址。while(k<10)。//進(jìn)行10次線性探測(cè),10次不成功．不再進(jìn)行探測(cè),令錯(cuò)誤標(biāo)記errflag=1{IICaddr=(hashaddr+k)*8;//從Hashing地址換算到實(shí)際內(nèi)存地址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)gotostart;//內(nèi)存中已有本卡的紀(jì)錄,不須再寫入。k++;}else{if(k<8)save(IICaddr);//將一條記錄存入。elseseterr=1;gotostart;}}}}