摘要：散列(hash)是一種重要的存儲方法,也是一種常見的查找方法。它是指在記錄的存儲位置和它的關(guān)鍵字之間建立一個確定的對應(yīng)關(guān)系。本文以射頻卡門禁控制器為例,說明用射頻卡卡號作為關(guān)鍵字,用Hash查找法確定此卡能否開門,并給出對應(yīng)的Keil C51程序。
單片機應(yīng)用系統(tǒng)中,經(jīng)常要涉及到數(shù)據(jù)的存儲和查找。以射頻卡門禁系統(tǒng)為例,見圖1。系統(tǒng)由51系列單片機、射頻卡(RF卡)讀卡電路、存儲單元24C256、繼電器等部分組成。其基本原理為：用戶刷卡后,RF卡讀卡電路讀出卡號,通過I/O口線送入單片機。單片機收到卡號后,在存儲單元中查找此卡是否允許開門。如允許,則命令繼電器動作,打開電磁門鎖：如不允許,則返回。
圖1 射頻卡門禁系統(tǒng)
在內(nèi)存中查找卡號有多種方法,最簡單的有線性查找法,即從存儲單元內(nèi)第一個記錄起與關(guān)鍵字比較,一直到記錄與關(guān)鍵字匹配。時間復(fù)雜程度為O(n),記錄數(shù)越多,比較過程耗時越長。一般記錄數(shù)為100～200時較合適,如在系統(tǒng)內(nèi)存儲1000～2 000條記錄,則用戶在刷卡開門時,因比較的次數(shù)較多,等待時間較長,將難以忍受。
對于記錄數(shù)較多(1000～2 000)的場合,可以采用對分法查找。此方法的時間復(fù)雜程度為O(log2n),2000個左右的記錄只需查找10～11次即可完成,效率大大提高。只是此法需要將記錄事先排序,隨機增加一個記錄或養(yǎng)活一個記錄將較麻煩。
二叉排序樹的方法可以兼有對分法查找的高效率和隨機插入記錄、刪除記錄的便利。但在編程中,由于要使用到指針變量,KeilC51要生成較大的目標(biāo)代碼。
Hash查找法在實踐中被證實是最快的一種查找方法,它的時間復(fù)雜度為O(1),即幾乎只要比較一次就可確定比較結(jié)果。它的基本思想是以空
間換時間,需要數(shù)據(jù)存儲器容量大,好在當(dāng)前存儲器的價格并不貴,采用大容量的存儲并不會使系統(tǒng)成本增加多少。
Hash查找法又稱散列查找,是一種重要的存儲和查找方法。它是指在記錄的存儲位置和它的關(guān)鍵字之間建立一個確定的對應(yīng)關(guān)系,使每個關(guān)
鍵字和存儲器中的唯一的存儲位置相對應(yīng)。將記錄的關(guān)鍵字與記錄的存儲位置對應(yīng)起來的關(guān)系稱為Hash函數(shù)。在查找時,如關(guān)鍵字是Key,只需要根據(jù)對應(yīng)關(guān)系計算出關(guān)鍵字Key對應(yīng)的值H(Key),就可得到記錄的存儲位置,這個位置稱為Hash地址。以射頻卡門禁系統(tǒng)為例,開門卡的卡
號為關(guān)鍵字,通過文中給定的一種運算即可直接得到對應(yīng)的記錄的存儲位置(Hash地址),從中取出是否可以開門的信息。
使用Hash查找法,會產(chǎn)生對于不同的關(guān)鍵字其Hash函數(shù)計算的Hash地址相同的情況,這種情況稱為沖突。在Hash查找法中沖突是不可避
免的。關(guān)鍵的問題是如何構(gòu)造Hash函數(shù),使所有關(guān)鍵字對應(yīng)的Hash地址均勻地分布在整個地址空間,盡可能少地減少活沖突。同時一旦發(fā)生沖
突要有足夠的辦法解決。本文采用折疊法來構(gòu)成Hash函數(shù),用線性探測法解決一旦發(fā)生的沖突。其細(xì)節(jié)可見參考文獻(xiàn)[1]、[2]。
當(dāng)前單片機應(yīng)用的普遍趨勢是采用片內(nèi)ROM,采用SPI或I2C等串行方式擴展外部設(shè)備,所以文中采用的存儲器是I2C總線的24C256,共32K字節(jié)。其中分配給Hash查找的存儲空間是16K,每記錄8個字節(jié),共2000條記錄,即可存儲2000個開門卡卡號。(24C256中剩余的地址留作它用)每條記錄分配如下：
0 1 2 3 4 5 6 7
55 16 92 64 02 XX XX
第0個字節(jié)0X55,表示該地址已有記錄。
第1個字節(jié)到第4個字節(jié)存放后8位卡號,BCD方式。
第5個字節(jié)～第7個字節(jié)留作參數(shù),如可控制開門卡在什么時間段內(nèi)可以開門,也可控制該卡不同的權(quán)限。
記錄從0000號單元開始存放。
卡號存放在數(shù)組d[0]～d[9]中,它是一個10位的10進(jìn)制數(shù),如卡號是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
程序中作如下運算
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]這樣的運算體現(xiàn)在hashfunc()函數(shù)中,hashfunc()函數(shù)的功能為根據(jù)10位卡號計算出對應(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ù),限于篇幅,這里不再申明,請參考main()程序中相應(yīng)的注釋。程序是以位變量setflag控制程序分支,setflag=1表明要將讀到的卡號存儲(函數(shù)save())到相應(yīng)的hash地址中,setflag=0表明要將讀到的卡號作為關(guān)鍵字,在內(nèi)存中進(jìn)行hash查找,找到相匹配的紀(jì)錄。KeilC51程序如下：
Main(){uinthashaddr,IICaddr;ucharstatus,i,k,cardmen,cardnum,seterr;reterr=0;start:Rfread();//讀卡,卡號存d[0]-d[9]Setflag=checkcard();//檢測是否是設(shè)置卡,是設(shè)置卡返回1,是開門卡返回0。if(setflag==0){k=0;hashaddr=hashfunc();//對關(guān)鍵字進(jìn)行Hashing運算,得到Hashing地址。while(k<10){IICaddr=(hashaddr+k)*8;//從Hashing地址換算到實際內(nèi)存地址。Status=IICRead(IICaddr);if(status==0x55){for(i=1;i<5;i++){cardmen=IICRead(IICaddr+i);//取出內(nèi)存中卡號。cardnum=d[i*2]*16+d[1+i*2];//與當(dāng)前的卡號比較,if(cardmen!=cardnum)break;//}if(i==5){open(3);//開門3秒gotostart;}}k++;//進(jìn)行10次探測。}}else{k=0;hashaddr=hashfunc();//對關(guān)鍵字進(jìn)行Hashing運算,得到Hashing地址。while(k<10)。//進(jìn)行10次線性探測,10次不成功．不再進(jìn)行探測,令錯誤標(biāo)記errflag=1{IICaddr=(hashaddr+k)*8;//從Hashing地址換算到實際內(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;}}}} 
下載文檔
