Hash技术在消防产品信息检索中的应用

●宋玉华，李焕群，王 珺

(1.烟台市消防支队，山东 烟台 264000;2.武警学院 科研部，河北 廊坊 065000;3.鲁东大学 数学与统计科学学院，山东 烟台 264025)

为了加强消防产品的审核及监管力度，公安部消防局已在全国推广实施消防产品身份证制度。该制度的引入，有利于加强对消防产品质量的监督管理，便于消防监管人员及时发现和查处假冒伪劣消防产品，防止假冒伪劣产品生产与流通，有助于建立良好的消防产品市场秩序，及从根本上解决消防产品管理存在的问题［1］。本文以消防产品身份证管理制度中的跟踪管理系统为研究背景，将快速查询Hash技术用于消防产品信息的检索中，并从全国消防产品数据库中采集相关数据进行了测试。

1 消防产品的身份证制度

1.1 消防产品质量现状

消防产品是指专门用于火灾预防、灭火救援和火灾防护、避难、逃生的产品［2］，可以分为渠道类产品(包括灭火器、灭火剂、应急灯具、防火涂料、消火栓、消防接口、消防水枪及可燃气体报警设备等)和直销类产品(包括防火门及防火阀)。自2006年在全国范围内开展建设工程消防产品监督抽查工作以来，2006－2010年监督抽查的抽样平均合格率分别为54.09%、64.51%、75.34%、79.06% 和 86.0%，消防产品质量整体水平保持逐年上升的趋势［3］。

但目前我国的消防产品市场仍需要进一步完善，存在问题主要为以下几个方面:(1)消防产品监督管理机制有待完善。消防产品的生产、销售、流通领域的监督查处由国家质量监督部门负责，而按照《中华人民共和国消防法》，消防监管部门应对生产、销售未经检验机构检验合格的消防产品的企业，责令停止违法行为、从重查处。这种机制会造成两部门各自为政，形成管理中的漏洞。(2)消防产品的监督管理缺乏有效性。消防机构在监督检查和消防审核验收时，对消防产品的质量情况无法准确界定，局限于查看审批意见书、检验报告、认证书等资料。(3)一些获得认证的消防产品生产企业缺乏责任心。部分获得生产认证的企业擅自变更设计、变更或者降低关键技术标准，使不符合市场准入的消防产品流向市场。

1.2 身份证管理制度

通过使用消防产品身份证，可以将管理消防产品的关口前移，遏制火灾隐患的产生。与消防产品身份证管理制度相配套的是跟踪管理系统［4］，该系统中全面录入并能反映出获得消防产品市场准入资格的产品及生产企业的详细信息，有利于解决不合格产品的生产商和销售商“定不了”的问题。

消防产品跟踪管理系统主要包括防伪标志、读写设备、安全密钥、软件系统以及相关支撑性的硬件和软件系统等，如图1所示的终端识别设备身份识别UD笔。其中，防伪标志是该系统最重要的组成部分，它在国内首次采用隐形精密点阵编码技术等多项尖端防伪科技，具备信息惟一性、防复制、防转移和可根据不同用户身份在多个环节多次写入信息等功能，如图2所示。

2 Hash检索技术

2.1 Hash 算法的原理

图1 身份识别UD笔

图2 消防产品身份标志

Hash技术在信息的数据存储与访问中占有重要的地位［5］。它是将关键字直接映射为存储地址，达到快速寻址的目的，即:

其中，Address为Hash地址;key为检索的关键字;H为Hash函数。

在Hash检索中，每一个记录的关键字都与Hash表中的某一个位置惟一对应，在进行信息检索时，只需要根据关键字和Hash函数，就可以查找到所查询记录的地址值，从而检索成功。

2.2 Hash冲突的解决方式

理想情况下，不同的关键字根据Hash函数进行映射后能够得到惟一的地址，从而使Hash表的检索性能达到，这种情况称为完美Hash(Perfect Hash，PSH)［6］。而通常情况下，不同关键字通过Hash函数计算后会映射到相同的地址中，即:

其中key1≠key2，这种情况称为Hash冲突。

Hash冲突往往难以避免，所以采用何种方式解决Hash冲突成为判断Hash算法优劣的关键因素之一。目前，常采用的解决Hash冲突的方式有以下几种:(1)开放寻址法:沿着Hash地址向下按一定增量寻找下一地址，判断是否冲突，如仍然冲突则继续按同一增量寻找下一地址。(2)再Hash法:对关键字计算另一个Hash函数地址，直到冲突不再发生。(3)链接法:每一个Hash地址为一动态链表，发生冲突时动态为其增加一个子项。(4)公共溢出区法:建立一个公共溢出区，发生碰撞时到公共溢出区检索记录。

3 利用Hash技术检索消防产品信息

3.1 Hash索引文件的构建

为解决可能存在的Hash冲突问题，并充分考虑算法的复杂度和存储空间的利用率，本文采用Hash桶技术存储索引记录［7－8］。

Hash索引文件由若干Hash桶组成，对于利用公式(1)计算得到相同Hash地址值的索引记录将会存放于同一个Hash桶中。Hash桶之间通过链表指针链接，每个Hash桶中存放若干的索引记录，对这些索引记录使用二叉排序树BST的形式组织，如图3所示。

图3 Hash索引文件结构

需合理选取Hash桶的数量，若数量过多会造成存储空间的浪费，若数量过少会增大冲突域，从而造成检索效率的下降。因此从装填因子的角度考虑，通常选取Hash桶数量为:

其中，n为Hash桶总数;N为索引记录总数;C为单个Hash桶容量;α为装填因子。

3.2 Hash 函数的构造

本文采用数字分析法构造Hash函数。消防产品身份标志的主要特点是每组标志都具有惟一的14位明码。由分析可知，第1、6、7、13、14位区分度不大，不适宜作为 Hash地址，所以取第 2、4、8、10、12 位做 Hash 运算［9］:

当使用UD笔读取到每件消防产品惟一对应的14位明码时，通过以上函数即可得到其对应的Hash地址。

3.3 信息检索流程

信息检索流程可分为以下6个步骤:(1)利用身份识别UD笔读取消防产品身份标志信息;(2)将读取到的信息通过蓝牙或USB连线传送给跟踪系统所在的计算机终端;(3)读取UD表中采集到的产品信息，并对信息中代表产品身份的14位明码标志做Hash运算，进而得到其对应的索引记录所在Hash桶的桶号;(4)到相应的Hash桶中对二叉排序树BST进行二分查找;(5)若未查找到匹配的索引记录，则返回报错信息，否则转向第6个步骤;(6)根据检索到的索引记录中datap域的数据指针，到数据存储区的指定位置查找产品信息，并返回检索结果。

3.4 性能分析

从全国消防产品数据库中采集3万条数据进行实验测试。每条记录提取出身份标志的14位明码作为索引关键字，再封装链表头、链表指针等信息组成一条索引记录，大小为24 B。Hash桶大小与识别笔的闪存数据页大小相同，为2 KB，所以Hash桶容量可设定为85。设置装填因子为0.7，由公式(3)计算得到Hash桶总数为505。

实验用计算机终端配置为Intel Core 2 Celeron G530 CPU 2.4 GHz，内存 2 G，操作系统为 Win2000 Server，数据库采用SQL Server 2000，对样本数据进行了20次实验测试，结果如表1所示。需说明的是:(1)1～15次实验查找到匹配的索引记录，用来测试匹配成功的情况;16～20次实验未查找到匹配的记录，用来测试匹配失败的情况。(2)实验结果中的耗时为Hash检索的时间，实际查询过程中还会包含UD笔将读取到的信息传送给计算机终端、跟踪系统运行、Hash存储数据等操作的耗费时间。

表1 实验结果

实验结果说明，将Hash技术应用到消防产品信息的检索中简单可行。Hash算法O(1)时间复杂度的检索特性可以减少信息查找的时间，十分适合在移动终端中使用，有利于消防监督人员更加高效地展开执法检查工作。

4 结论

本文在分析我国消防产品监督管理多个方面存在问题的基础上，介绍了近几年来逐步推广与实施的消防产品身份证管理制度在有效加强消防产品管理和监督，防止和杜绝假冒伪劣产品流入市场方面发挥的突出作用。针对身份证管理制度的跟踪管理系统中移动终端查询速度较慢的问题，利用Hash技术的检索原理，嵌入采用数字分析法构造的Hash函数，并从全国消防产品数据库中采集3万条数据进行海量实验测试。实验结果表明，该方法可以快速准确地检索到产品信息，同时能够有效地解决Hash地址冲突问题，极大提高了信息检索效率，从而为消防监管人员开展监管工作提供极大的帮助。

［1］赵立宏.浅议实施消防产品身份证制度对消防产品监督管理的作用［J］.科技资讯，2010，23(10):238 －239.

［2］李建伟，张炜.消防产品监督管理现状及问题分析［J］.安防科技，2011，(7):42 －43.

［3］李军，谢忠宇.谈当前消防产品监督管理工作［J］.消防技术与产品信息，2011，(5):68 －71.

［4］陈映雄.浅谈消防产品的流向监督［J］.消防技术与产品信息，2009，(3):61 －63.

［5］宋叶俊，元昌安，王艳.基于Hash表的分类信息匹配及甄别算法［J］.计算机工程与设计，2009，30(6):1552 －1553.

［6］刘璟.计算机算法引论:设计与分析技术［M］.北京:科学出版社，2007:82－97.

［7］周大，梁智超，孟小峰.HF－Tree:一种闪存数据库的高更新性能索引结构［J］.计算机研究与发展，2010，47(5):832 －840.

［8］黄金，吴晓东，武红斌.哈希索引在交警专用移动执法终端数据检索中的应用研究［J］.智能交通，2010，20(3):83 －86.

［9］贺贤明，邵雷兵.一种基于学习的自适应哈希算法研究［J］.计算机应用与软件，2004，21(11):93 －96.