●宋玉華，李煥群，王 珺

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

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

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

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

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

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

1.2 身份證管理制度

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

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

2 Hash檢索技術(shù)

2.1 Hash 算法的原理

圖1 身份識(shí)別UD筆

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

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

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

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

2.2 Hash沖突的解決方式

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

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

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

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

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

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

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

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

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

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

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

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

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

3.3 信息檢索流程

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

3.4 性能分析

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

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

表1 實(shí)驗(yàn)結(jié)果

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

4 結(jié)論

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

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

［2］李建偉，張煒.消防產(chǎn)品監(jiān)督管理現(xiàn)狀及問(wè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］.計(jì)算機(jī)工程與設(shè)計(jì)，2009，30(6):1552 －1553.

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

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

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

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