散列表快速查找算法在單片機系統(tǒng)中的應用

1、散列表快速查找算法在單片機系統(tǒng)中的應用    0引言實時性要求很高的單片機系統(tǒng)往往要采用復雜的數(shù)據(jù)結(jié)構(gòu)算法來實現(xiàn)動態(tài)查找表的查找。而在數(shù)據(jù)結(jié)構(gòu)(線性表或樹)中的記錄數(shù)目很大時，由于關鍵字的比較次數(shù)多，查找速度慢，因而難以實現(xiàn)系統(tǒng)的實時性。這樣，創(chuàng)建和選擇一個好的數(shù)據(jù)查找算法就很關鍵。本文以澡堂消費系統(tǒng)為例，介紹了一種散列表快速查找算法在單片機系統(tǒng)中的應用方法。1散列表的引入散列表又稱為哈希表，是一種重要的存儲方式和檢索方法?；谏⒘斜淼牟檎曳Q散列0 引言實時性要求很高的單片機系統(tǒng)往往要采用復雜的數(shù)據(jù)結(jié)構(gòu)算法來實現(xiàn)動態(tài)查找表的查找。而在數(shù)據(jù)結(jié)構(gòu)(線性表或樹

2、)中的記錄數(shù)目很大時，由于關鍵字的比較次數(shù)多，查找速度慢，因而難以實現(xiàn)系統(tǒng)的實時性。這樣，創(chuàng)建和選擇一個好的數(shù)據(jù)查找算法就很關鍵。本文以澡堂消費系統(tǒng)為例，介紹了一種散列表快速查找算法在單片機系統(tǒng)中的應用方法。1散列表的引入散列表又稱為哈希表，是一種重要的存儲方式和檢索方法?；谏⒘斜淼牟檎曳Q散列查找，是一種快速查找方法，只要設計合理，其計算量并不大。一般的線性表和樹中，記錄在結(jié)構(gòu)中的相對位置是隨機的，即和記錄的關鍵字不存在確定的關系。因此，在結(jié)構(gòu)中查找記錄時，需進行一系列和關鍵字(key)的比較，查找的效率取決于比較的次數(shù)。理想的情況是能直接找到需要的記錄，因此，必須在記錄的存儲位置和它的關鍵

3、字之間建立某種確定的對應關系H，以使每個關鍵字和結(jié)構(gòu)中唯一的存儲位置相對應。這樣，在查找時，只要根據(jù)對應關系H找到給定值key的像H(key)。若結(jié)構(gòu)中存在和關鍵字相等的記錄，且必定在H(key)的存儲地址上，則這個對應關系H即為哈希(Hash)函數(shù)，按這個思想建立的表即為散列表。哈希函數(shù)是從關鍵字集合到地址集合的映像。通常，關鍵字集合比較大，它的元素包括所有可能的關鍵字，而地址集合的元素僅為哈希表中的地址值。不同的關鍵字可能映像到相同的哈希地址，這種現(xiàn)象稱為沖突，生成相同哈希地址的關鍵字稱為同義詞。一般情況下，哈希函數(shù)是一個壓縮映像，這就不可避免地會產(chǎn)生沖突(除非數(shù)據(jù)很少)，因而只能采取措施

4、盡量避免沖突或?qū)ふ医鉀Q沖突的辦法。沖突的頻繁程度除了與H相關外，還與表的填滿程度相關。設m和n分別表示表長和表中填入的結(jié)點數(shù)，那么，可將=nm定義為散列表的裝填因子(Load Factor)。越大，表越滿，沖突的機會也越大，通常取1。處理沖突常用的方法有開放定址法、再哈希法及鏈地址法等。     由于單片機的資源有限，所以在選擇哈希函數(shù)和防沖突機制時，應充分考慮單片機的運算能力和存儲空間。本系統(tǒng)把當前消費記錄存儲到帶I2C接口的片外存儲器24LC256中，記錄中包含有卡號(3個字節(jié))和刷卡時間等字段。表1所列是一個IC卡的費散列表結(jié)構(gòu)。2哈希函數(shù)的構(gòu)造澡

5、堂計時收費的時間通常是以消費者消費的時間進行計算的。這種計費方式要求消費者進出澡堂時各刷一次卡，以兩次刷卡的時間間隔計算消費費用。當消費者刷卡時，讀寫器將讀得的卡號(關鍵字)與表中存儲的卡號進行比較。若有相同卡號的記錄，且標志位為000的記錄，則認為該消費者是第二次刷卡(出澡堂完成消費)，計算兩次刷卡的時間間隔即可得到消費費用，結(jié)帳后再修改該記錄；若查找不到相同卡號的記錄，或卡號相同而標志位不為000時，則認為該消費者是第一次刷卡(進入澡堂消費)，此時，系統(tǒng)會在表中添加一條新的記錄。由于進出澡堂的人是動態(tài)變化的，要實現(xiàn)計時收費，重要的一點就是要能方便的實現(xiàn)消費記錄的查找和修改，其中記錄的查找最

6、為關鍵。由于查找表是系統(tǒng)在運行過程中動態(tài)生成的，所以如何方便快捷地實現(xiàn)查找是系統(tǒng)的關鍵。"好"的哈希函數(shù)要求計算簡單快速，并且可使一組關鍵字的哈希地址等概率地分布在整個地址區(qū)間中，以使沖突最小化。構(gòu)造哈希函數(shù)的常用方法有直接定址法、數(shù)字分析法、平方取中法、折疊法、除留余數(shù)法和隨機數(shù)法。本系統(tǒng)采用除留余數(shù)法(取關鍵字被某個不大于哈希表表長m的數(shù)p除后所得余數(shù)為哈希地址)。該方法記錄地址為記錄存儲的實際物理地址，共15位，可由下式計算：記錄地址=存儲塊號×8+0x0500。一般情況下，可以選p為質(zhì)數(shù)或不包含小于20的質(zhì)因素的合數(shù)。由于表長m為2048，所以，只要質(zhì)數(shù)p

7、小于2048即可(選p=173)。操作時，先求3個字節(jié)卡號的累加和，再將累加和對173取模作為哈希地址。如卡號(Key)為0x15555D，則哈希地址H(key)=(0x15+0x55+0x5d)MOD173=26。表1中的哈希地址為26的卡號還有0xC7和0xCOB2AF，這3個卡號為同義詞，它們對應的記錄存儲在同一線性鏈表中。記錄的內(nèi)容通常包括下一條記錄的存儲塊號、卡號、卡類型、功能字節(jié)和功能標志位(見表1)。其中，下一條記錄存儲塊號和標志位一共占用2個字節(jié)，低11位(D0D10)為存儲塊號(范圍從0到2047)，與頭鏈表對應。記錄的是鏈表中下一條記錄的存儲塊號(卡類別相同)，如果沒有下一

8、條記錄，則存儲塊號為2048，表示空指針。高3位(D15、D14、D13)為功能標志位，     (其中000表示計時收費開始，001表示計時消費結(jié)束或表示固定消費，100表示加卡，101表示開戶，110表示銷戶，011、111和010可作為其他拓展功能?？ㄌ柺顷P鍵字，占3個字節(jié)，由6位16進制數(shù)組成。由于卡類型是對p取模，最大不超過255，所以它占1個字節(jié)。通過功能字節(jié)可在計時模式下記錄消費者進入澡堂刷卡時的時間，該功能占2個字節(jié)(高字節(jié)存儲時，低字節(jié)存儲分)。當計時消費結(jié)束后，記錄消費金額(高字節(jié)記錄元，低字節(jié)記錄角)。3沖突的解決本文采用鏈地址法處