Hash技術(shù)在消防產(chǎn)品信息檢索中的應(yīng)用

●宋玉華，李煥群，王 珺

(1.煙臺市消防支隊，山東 煙臺 264000;2.武警學(xué)院 科研部，河北 廊坊 065000;3.魯東大學(xué) 數(shù)學(xué)與統(tǒng)計科學(xué)學(xué)院，山東 煙臺 264025)

為了加強消防產(chǎn)品的審核及監(jiān)管力度，公安部消防局已在全國推廣實施消防產(chǎn)品身份證制度。該制度的引入，有利于加強對消防產(chǎn)品質(zhì)量的監(jiān)督管理，便于消防監(jiān)管人員及時發(fā)現(xiàn)和查處假冒偽劣消防產(chǎn)品，防止假冒偽劣產(chǎn)品生產(chǎn)與流通，有助于建立良好的消防產(chǎn)品市場秩序，及從根本上解決消防產(chǎn)品管理存在的問題［1］。本文以消防產(chǎn)品身份證管理制度中的跟蹤管理系統(tǒng)為研究背景，將快速查詢Hash技術(shù)用于消防產(chǎn)品信息的檢索中，并從全國消防產(chǎn)品數(shù)據(jù)庫中采集相關(guān)數(shù)據(jù)進行了測試。

1 消防產(chǎn)品的身份證制度

1.1 消防產(chǎn)品質(zhì)量現(xiàn)狀

消防產(chǎn)品是指專門用于火災(zāi)預(yù)防、滅火救援和火災(zāi)防護、避難、逃生的產(chǎn)品［2］，可以分為渠道類產(chǎn)品(包括滅火器、滅火劑、應(yīng)急燈具、防火涂料、消火栓、消防接口、消防水槍及可燃?xì)怏w報警設(shè)備等)和直銷類產(chǎn)品(包括防火門及防火閥)。自2006年在全國范圍內(nèi)開展建設(shè)工程消防產(chǎn)品監(jiān)督抽查工作以來，2006－2010年監(jiān)督抽查的抽樣平均合格率分別為54.09%、64.51%、75.34%、79.06% 和 86.0%，消防產(chǎn)品質(zhì)量整體水平保持逐年上升的趨勢［3］。

但目前我國的消防產(chǎn)品市場仍需要進一步完善，存在問題主要為以下幾個方面:(1)消防產(chǎn)品監(jiān)督管理機制有待完善。消防產(chǎn)品的生產(chǎn)、銷售、流通領(lǐng)域的監(jiān)督查處由國家質(zhì)量監(jiān)督部門負(fù)責(zé)，而按照《中華人民共和國消防法》，消防監(jiān)管部門應(yīng)對生產(chǎn)、銷售未經(jīng)檢驗機構(gòu)檢驗合格的消防產(chǎn)品的企業(yè)，責(zé)令停止違法行為、從重查處。這種機制會造成兩部門各自為政，形成管理中的漏洞。(2)消防產(chǎn)品的監(jiān)督管理缺乏有效性。消防機構(gòu)在監(jiān)督檢查和消防審核驗收時，對消防產(chǎn)品的質(zhì)量情況無法準(zhǔn)確界定，局限于查看審批意見書、檢驗報告、認(rèn)證書等資料。(3)一些獲得認(rèn)證的消防產(chǎn)品生產(chǎn)企業(yè)缺乏責(zé)任心。部分獲得生產(chǎn)認(rèn)證的企業(yè)擅自變更設(shè)計、變更或者降低關(guān)鍵技術(shù)標(biāo)準(zhǔn)，使不符合市場準(zhǔn)入的消防產(chǎn)品流向市場。

1.2 身份證管理制度

通過使用消防產(chǎn)品身份證，可以將管理消防產(chǎn)品的關(guān)口前移，遏制火災(zāi)隱患的產(chǎn)生。與消防產(chǎn)品身份證管理制度相配套的是跟蹤管理系統(tǒng)［4］，該系統(tǒng)中全面錄入并能反映出獲得消防產(chǎn)品市場準(zhǔn)入資格的產(chǎn)品及生產(chǎn)企業(yè)的詳細(xì)信息，有利于解決不合格產(chǎn)品的生產(chǎn)商和銷售商“定不了”的問題。

消防產(chǎn)品跟蹤管理系統(tǒng)主要包括防偽標(biāo)志、讀寫設(shè)備、安全密鑰、軟件系統(tǒng)以及相關(guān)支撐性的硬件和軟件系統(tǒng)等，如圖1所示的終端識別設(shè)備身份識別UD筆。其中，防偽標(biāo)志是該系統(tǒng)最重要的組成部分，它在國內(nèi)首次采用隱形精密點陣編碼技術(shù)等多項尖端防偽科技，具備信息惟一性、防復(fù)制、防轉(zhuǎn)移和可根據(jù)不同用戶身份在多個環(huán)節(jié)多次寫入信息等功能，如圖2所示。

2 Hash檢索技術(shù)

2.1 Hash 算法的原理

圖1 身份識別UD筆

圖2 消防產(chǎn)品身份標(biāo)志

Hash技術(shù)在信息的數(shù)據(jù)存儲與訪問中占有重要的地位［5］。它是將關(guān)鍵字直接映射為存儲地址，達到快速尋址的目的，即:

其中，Address為Hash地址;key為檢索的關(guān)鍵字;H為Hash函數(shù)。

在Hash檢索中，每一個記錄的關(guān)鍵字都與Hash表中的某一個位置惟一對應(yīng)，在進行信息檢索時，只需要根據(jù)關(guān)鍵字和Hash函數(shù)，就可以查找到所查詢記錄的地址值，從而檢索成功。

2.2 Hash沖突的解決方式

理想情況下，不同的關(guān)鍵字根據(jù)Hash函數(shù)進行映射后能夠得到惟一的地址，從而使Hash表的檢索性能達到，這種情況稱為完美Hash(Perfect Hash，PSH)［6］。而通常情況下，不同關(guān)鍵字通過Hash函數(shù)計算后會映射到相同的地址中，即:

其中key1≠key2，這種情況稱為Hash沖突。

Hash沖突往往難以避免，所以采用何種方式解決Hash沖突成為判斷Hash算法優(yōu)劣的關(guān)鍵因素之一。目前，常采用的解決Hash沖突的方式有以下幾種:(1)開放尋址法:沿著Hash地址向下按一定增量尋找下一地址，判斷是否沖突，如仍然沖突則繼續(xù)按同一增量尋找下一地址。(2)再Hash法:對關(guān)鍵字計算另一個Hash函數(shù)地址，直到?jīng)_突不再發(fā)生。(3)鏈接法:每一個Hash地址為一動態(tài)鏈表，發(fā)生沖突時動態(tài)為其增加一個子項。(4)公共溢出區(qū)法:建立一個公共溢出區(qū)，發(fā)生碰撞時到公共溢出區(qū)檢索記錄。

3 利用Hash技術(shù)檢索消防產(chǎn)品信息

3.1 Hash索引文件的構(gòu)建

為解決可能存在的Hash沖突問題，并充分考慮算法的復(fù)雜度和存儲空間的利用率，本文采用Hash桶技術(shù)存儲索引記錄［7－8］。

Hash索引文件由若干Hash桶組成，對于利用公式(1)計算得到相同Hash地址值的索引記錄將會存放于同一個Hash桶中。Hash桶之間通過鏈表指針鏈接，每個Hash桶中存放若干的索引記錄，對這些索引記錄使用二叉排序樹BST的形式組織，如圖3所示。

圖3 Hash索引文件結(jié)構(gòu)

需合理選取Hash桶的數(shù)量，若數(shù)量過多會造成存儲空間的浪費，若數(shù)量過少會增大沖突域，從而造成檢索效率的下降。因此從裝填因子的角度考慮，通常選取Hash桶數(shù)量為:

其中，n為Hash桶總數(shù);N為索引記錄總數(shù);C為單個Hash桶容量;α為裝填因子。

3.2 Hash 函數(shù)的構(gòu)造

本文采用數(shù)字分析法構(gòu)造Hash函數(shù)。消防產(chǎn)品身份標(biāo)志的主要特點是每組標(biāo)志都具有惟一的14位明碼。由分析可知，第1、6、7、13、14位區(qū)分度不大，不適宜作為 Hash地址，所以取第 2、4、8、10、12 位做 Hash 運算［9］:

當(dāng)使用UD筆讀取到每件消防產(chǎn)品惟一對應(yīng)的14位明碼時，通過以上函數(shù)即可得到其對應(yīng)的Hash地址。

3.3 信息檢索流程

信息檢索流程可分為以下6個步驟:(1)利用身份識別UD筆讀取消防產(chǎn)品身份標(biāo)志信息;(2)將讀取到的信息通過藍牙或USB連線傳送給跟蹤系統(tǒng)所在的計算機終端;(3)讀取UD表中采集到的產(chǎn)品信息，并對信息中代表產(chǎn)品身份的14位明碼標(biāo)志做Hash運算，進而得到其對應(yīng)的索引記錄所在Hash桶的桶號;(4)到相應(yīng)的Hash桶中對二叉排序樹BST進行二分查找;(5)若未查找到匹配的索引記錄，則返回報錯信息，否則轉(zhuǎn)向第6個步驟;(6)根據(jù)檢索到的索引記錄中datap域的數(shù)據(jù)指針，到數(shù)據(jù)存儲區(qū)的指定位置查找產(chǎn)品信息，并返回檢索結(jié)果。

3.4 性能分析

從全國消防產(chǎn)品數(shù)據(jù)庫中采集3萬條數(shù)據(jù)進行實驗測試。每條記錄提取出身份標(biāo)志的14位明碼作為索引關(guān)鍵字，再封裝鏈表頭、鏈表指針等信息組成一條索引記錄，大小為24 B。Hash桶大小與識別筆的閃存數(shù)據(jù)頁大小相同，為2 KB，所以Hash桶容量可設(shè)定為85。設(shè)置裝填因子為0.7，由公式(3)計算得到Hash桶總數(shù)為505。

實驗用計算機終端配置為Intel Core 2 Celeron G530 CPU 2.4 GHz，內(nèi)存 2 G，操作系統(tǒng)為 Win2000 Server，數(shù)據(jù)庫采用SQL Server 2000，對樣本數(shù)據(jù)進行了20次實驗測試，結(jié)果如表1所示。需說明的是:(1)1～15次實驗查找到匹配的索引記錄，用來測試匹配成功的情況;16～20次實驗未查找到匹配的記錄，用來測試匹配失敗的情況。(2)實驗結(jié)果中的耗時為Hash檢索的時間，實際查詢過程中還會包含UD筆將讀取到的信息傳送給計算機終端、跟蹤系統(tǒng)運行、Hash存儲數(shù)據(jù)等操作的耗費時間。

表1 實驗結(jié)果

實驗結(jié)果說明，將Hash技術(shù)應(yīng)用到消防產(chǎn)品信息的檢索中簡單可行。Hash算法O(1)時間復(fù)雜度的檢索特性可以減少信息查找的時間，十分適合在移動終端中使用，有利于消防監(jiān)督人員更加高效地展開執(zhí)法檢查工作。

4 結(jié)論

本文在分析我國消防產(chǎn)品監(jiān)督管理多個方面存在問題的基礎(chǔ)上，介紹了近幾年來逐步推廣與實施的消防產(chǎn)品身份證管理制度在有效加強消防產(chǎn)品管理和監(jiān)督，防止和杜絕假冒偽劣產(chǎn)品流入市場方面發(fā)揮的突出作用。針對身份證管理制度的跟蹤管理系統(tǒng)中移動終端查詢速度較慢的問題，利用Hash技術(shù)的檢索原理，嵌入采用數(shù)字分析法構(gòu)造的Hash函數(shù)，并從全國消防產(chǎn)品數(shù)據(jù)庫中采集3萬條數(shù)據(jù)進行海量實驗測試。實驗結(jié)果表明，該方法可以快速準(zhǔn)確地檢索到產(chǎn)品信息，同時能夠有效地解決Hash地址沖突問題，極大提高了信息檢索效率，從而為消防監(jiān)管人員開展監(jiān)管工作提供極大的幫助。

［1］趙立宏.淺議實施消防產(chǎn)品身份證制度對消防產(chǎn)品監(jiān)督管理的作用［J］.科技資訊，2010，23(10):238 －239.

［2］李建偉，張煒.消防產(chǎn)品監(jiān)督管理現(xiàn)狀及問題分析［J］.安防科技，2011，(7):42 －43.

［3］李軍，謝忠宇.談當(dāng)前消防產(chǎn)品監(jiān)督管理工作［J］.消防技術(shù)與產(chǎn)品信息，2011，(5):68 －71.

［4］陳映雄.淺談消防產(chǎn)品的流向監(jiān)督［J］.消防技術(shù)與產(chǎn)品信息，2009，(3):61 －63.

［5］宋葉俊，元昌安，王艷.基于Hash表的分類信息匹配及甄別算法［J］.計算機工程與設(shè)計，2009，30(6):1552 －1553.

［6］劉璟.計算機算法引論:設(shè)計與分析技術(shù)［M］.北京:科學(xué)出版社，2007:82－97.

［7］周大，梁智超，孟小峰.HF－Tree:一種閃存數(shù)據(jù)庫的高更新性能索引結(jié)構(gòu)［J］.計算機研究與發(fā)展，2010，47(5):832 －840.

［8］黃金，吳曉東，武紅斌.哈希索引在交警專用移動執(zhí)法終端數(shù)據(jù)檢索中的應(yīng)用研究［J］.智能交通，2010，20(3):83 －86.

［9］賀賢明，邵雷兵.一種基于學(xué)習(xí)的自適應(yīng)哈希算法研究［J］.計算機應(yīng)用與軟件，2004，21(11):93 －96.