本发明涉及通信技术领域， 尤其涉及关键字存储、 查找的方法及装置。 背景技术

基于哈希 （hash ) 的精确匹配算法在各领域均有广泛应用。 低延时、 低 冲突概率和高性能是大家追求的目标。

现有技术提供了一种通过二次哈希算法实现精 确匹配查找的方案。 该方 案中， 对于一个进行精确匹配查找的关键字 （key ) ， 使用两个哈希函数。

通过哈希函数 1运算， 可以得到一个初始哈希桶地址， 初始哈希桶中包 含若干压缩关键字单元和一个级连链表指针。 每个压缩关键字单元由一个压 缩关键字和一个关键字指针构成。 有效的级连链表指针指向一个级连哈希 桶。 级连哈希桶的数据结构与初始哈希桶一致。

通过哈希函数 2运算， 可以得到一个压缩关键字。 将得到的压缩关键字 与初始哈希桶和 /或级连哈希桶中存储的有效的压缩关键字进� �如下比较： 如果初始哈希桶及相应的链表中没有匹配的压 缩关键字， 则需要检查是 否有有效的级连哈希桶指针， 并比较级连哈希桶中是否存在有效的匹配的压 缩关键字；

如果所有关联的哈希桶中都没有匹配的压缩关 键字， 则说明本次查找没 有命中； 如果有有效的匹配的压缩关键字， 则需要一一检查对应的完整关键 字是否匹配， 直至遍历结束或找到匹配的完整关键字；

如果所有有效匹配的压缩关键字对应的完整关 键字都不匹配， 说明本次 查找没有命中； 如果查到有匹配的完整关键字， 则说明本次查找命中， 查找 结束。

发明人在实现本发明的过程中， 发现上述现有技术存在如下不足： 哈希函数 1的冲突会导致初始哈希桶中需要保存较多表� �才能达到减少 级连哈希桶的目的。 但是初始哈希桶的桶深过深会导致存储空间和 带宽的浪 费。 哈希函数 2的冲突会导致压缩关键字冲突， 需要多次访问哈希桶才能完 成查找， 这样会增加查找延时。 发明内容

本发明实施例提供一种关键字的存储方法， 用以节约存储空间和带宽， 该方法包括：

将关键字经第一哈希函数运算， 获得第一哈希桶的地址； 根据第一哈希 桶的地址， 查找第一哈希桶；

将所述关键字经第二哈希函数运算， 获得第二哈希桶的地址； 根据第二 哈希桶的地址， 查找第二哈希桶；

若第一哈希桶中没有与所述关键字的压缩关键 字相冲突的压缩关键字， 所述关键字的压缩关键字由所述关键字经第三 哈希函数运算获得， 贝 IJ :

在第一哈希桶有剩余空间时， 将所述关键字的压缩关键字及所述关键字 的指针存入第一哈希桶；

在第一哈希桶没有剩余空间、 第二哈希桶有剩余空间且第二哈希桶中没 有与所述关键字的压缩关键字相冲突的压缩关 键字时， 将所述关键字的压缩 关键字及所述关键字的指针存入第二哈希桶。

本发明实施例还提供一种关键字的查找方法， 用以降低查找延时， 提高 查找效率， 该查找方法包括：

在所述 TCAM 中查找所述关键字或所述关键字的压缩关键字 ； 若未查找 到， 则:

在第一哈希桶中查找所述关键字的压缩关键字 ； 若未查找到， 贝 IJ : 在第二哈希桶中查找所述关键字的压缩关键字 。 本发明实施例还提供一种关键字的存储装置， 用以节约存储空间和带 宽， 该装置包括：

第一哈希桶查找模块， 用于将关键字经第一哈希函数运算， 获得第一哈 希桶的地址； 根据第一哈希桶的地址， 查找第一哈希桶；

第二哈希桶查找模块， 用于将所述关键字经第二哈希函数运算， 获得第 二哈希桶的地址； 根据第二哈希桶的地址， 查找第二哈希桶；

第一确定模块， 用于确定第一哈希桶中没有与所述关键字的压 缩关键字 相冲突的压缩关键字， 所述关键字的压缩关键字由所述关键字经第三 哈希函 数运算获得；

第一存储模块， 用于在第一哈希桶有剩余空间时， 将所述关键字的压缩 关键字及所述关键字的指针存入第一哈希桶；

第二存储模块， 用于在第一哈希桶没有剩余空间、 第二哈希桶有剩余空 间且第二哈希桶中没有与所述关键字的压缩关 键字相冲突的压缩关键字时， 将所述关键字的压缩关键字及所述关键字的指 针存入第二哈希桶。

本发明实施例还提供一种关键字的查找装置， 用以降低查找延时， 提高 查找效率， 该查找装置中的关键字由上述关键字的存储装 置进行存储， 该查 找装置包括：

第一关键字查找模块， 用于在所述 TCAM 中查找所述关键字或所述关键 字的压缩关键字；

第二关键字查找模块， 用于在所述第一关键字查找模块未查找到所述 关 键字或所述关键字的压缩关键字时， 在第一哈希桶中查找所述关键字的压缩 关键字；

第三关键字查找模块， 用于在所述第二关键字查找模块未查找到所述 关 键字的压缩关键字时， 在第二哈希桶中查找所述关键字的压缩关键字 。

本发明实施例中， 将关键字经第一哈希函数运算， 获得第一哈希桶的地 址； 根据第一哈希桶的地址， 查找第一哈希桶； 将所述关键字经第二哈希函 数运算， 获得第二哈希桶的地址； 根据第二哈希桶的地址， 查找第二哈希 桶； 不同于现有技术中仅通过一个哈希函数获得初 始哈希桶地址， 由初始哈 希桶中级连链表指针指向级连哈希桶， 而是通过两个由不同哈希函数独立获 取地址的哈希桶， 来完成对关键字的存储操作， 从而大大提高内存利用率， 节省存储空间和带宽； 并且， 由关键字经不同哈希函数运算获得地址的两个 哈希桶可以采用不同的深度， 可以增加存储的灵活性； 另外， 在第一哈希桶 或第二哈希桶存储关键字时进行的压缩关键字 冲突判断， 也可以避免第一哈 希桶或第二哈希桶中出现压缩关键字冲突的情 况。

本发明实施例中， 先在 TCAM 中查找关键字或关键字的压缩关键字， 若 能够查找到， 则可以避免查找第一哈希桶和 /或第二哈希桶， 从而使查找延 时大幅降低， 查找效率得以有效提高。 附图说明

为了更清楚地说明本发明实施例或现有技术中 的技术方案， 下面将对实 施例或现有技术描述中所需要使用的附图作简 单地介绍， 显而易见地， 下面 描述中的附图仅仅是本发明的一些实施例， 对于本领域普通技术人员来讲， 在不付出创造性劳动性的前提下 ， 还可以根据这些附图获得其他的附图。 在 附图中：

图 1为本发明实施例中关键

图 2为本发明实施例中关键

图 3为本发明实施例中关键

图 4为本发明实施例中关键

图 5、 图 6、 图 7为本发明实施例中关键字的存储装置的结构� �意图； 图 8、 图 9为本发明实施例中关键字的查找装置的结构� �意图。 具体实施方式 为使本发明实施例的目的、 技术方案和优点更加清楚明白， 下面结合附 图对本发明实施例做进一歩详细说明。 在此， 本发明的示意性实施例及其说 明用于解释本发明， 但并不作为对本发明的限定。

如图 1 所示， 本发明实施例中， 关键字的存储方法的处理流程可以包 括：

歩骤 101、 将关键字经第一哈希函数运算， 获得第一哈希桶的地址； 根 据第一哈希桶的地址， 查找第一哈希桶；

歩骤 102、 将所述关键字经第二哈希函数运算， 获得第二哈希桶的地 址； 根据第二哈希桶的地址， 查找第二哈希桶；

歩骤 103、 若第一哈希桶中没有与所述关键字的压缩关键 字相冲突的压 缩关键字， 所述关键字的压缩关键字由所述关键字经第三 哈希函数运算获 得， 确定第一哈希桶是否有剩余空间， 若是， 则转入歩骤 104; 若否， 则转 入歩骤 105;

歩骤 104、 将所述关键字的压缩关键字及所述关键字的指 针存入第一哈 希桶；

歩骤 105、 在第二哈希桶有剩余空间且第二哈希桶中没有 与所述关键字 的压缩关键字相冲突的压缩关键字时， 将所述关键字的压缩关键字及所述关 键字的指针存入第二哈希桶。

由图 1所示流程可以得知， 本发明实施例中， 将关键字经第一哈希函数 运算， 获得第一哈希桶的地址； 根据第一哈希桶的地址， 查找第一哈希桶； 将所述关键字经第二哈希函数运算， 获得第二哈希桶的地址； 根据第二哈希 桶的地址， 查找第二哈希桶； 不同于现有技术中仅通过一个哈希函数获得初 始哈希桶地址， 由初始哈希桶中级连链表指针指向级连哈希桶 ， 而是通过两 个由不同哈希函数独立获取地址的哈希桶， 来完成对关键字的存储操作， 从 而大大提高内存利用率， 节省存储空间和带宽； 并且， 由关键字经不同哈希 函数运算获得地址的两个哈希桶可以采用不同 的深度， 可以增加存储的灵活 性； 另外， 在第一哈希桶或第二哈希桶存储关键字时进行 的压缩关键字冲突 判断， 也可以避免第一哈希桶或第二哈希桶中出现压 缩关键字冲突的情况。

图 1中歩骤 101和歩骤 102的执行先后顺序并不影响本发明实施例的具 体实施。 歩骤 101和歩骤 102中， 将关键字经第一哈希函数运算， 可以获得 第一哈希桶的地址； 将关键字经第二哈希函数运算， 可以获得第二哈希桶的 地址； 此处， 第一哈希函数和第二哈希函数为不同的哈希函 数， 将关键字经 这两个不同的哈希函数进行运算， 可以获得两个不同的哈希桶地址， 这两个 哈希函数的具体设定利用现有技术即可得知。 根据第一哈希桶的地址可以查 找到第一哈希桶； 根据第二哈希桶的地址可以查找到第二哈希桶 ， 从而可以 实施歩骤 103至歩骤 105， 在第一哈希桶或第二哈希桶中， 对关键字进行存 储操作。 具体实施时， 待存储的关键字的压缩关键字， 可以由关键字经第三 哈希函数运算获得， 第三哈希函数的具体设定利用现有技术也可得 知。

为了更进一歩地避免存储时第一哈希桶或第二 哈希桶中出现压缩关键字 冲突的情况， 另一实施例中， 还可以引入 TCAM ( Ternary Content Addressable Memory , 三进制内容可寻址存储器） ， 对关键字进行存储操 作。 当然， TCAM 中可以存储完整的关键字和关键字的指针， 也可以为节省 存储空间的目的， 存储关键字的压缩关键字和关键字的指针。 gp， 具体可实 施为：

若第一哈希桶中有与所述关键字的压缩关键字 相冲突的压缩关键字， 则 将所述关键字及所述关键字的指针存入 TCAM, 或将所述关键字的压缩关键 字及所述关键字的指针存入所述 TCAM;

或， 若第一哈希桶中没有与所述关键字的压缩关键 字相冲突的压缩关键 字且没有剩余空间、 第二哈希桶中有与所述关键字的压缩关键字相 冲突的压 缩关键字， 则将所述关键字及所述关键字的指针存入所述 TCAM, 或将所述 关键字的压缩关键字及所述关键字的指针存入 所述 TCAM; 或， 若第一哈希桶和第二哈希桶均没有剩余空间， 则将所述关键字及所 述关键字的指针存入所述 TCAM, 或将所述关键字的压缩关键字及所述关键 字的指针存入所述 TCAM。

一个实施例中， 上述关键字的存储方法还可以包括：

若所述 TCAM 中有与第一哈希桶中压缩关键字不相冲突的压 缩关键字， 则将该压缩关键字及对应的关键字指针搬移到 第一哈希桶中；

若所述 TCAM 中有与第二哈希桶中压缩关键字不相冲突的压 缩关键字， 则将该压缩关键字及对应的关键字指针搬移到 第二哈希桶中。

例如， 当在第一哈希桶或第二哈希桶中删除的关键字 的压缩关键字及关 键字的指针达到一定数量时， 原冲突的压缩关键字可能已不再冲突； 此时可 以启动 TCAM 扫描， 将不再存在冲突的压缩关键字及对应的关键字 指针从 TCAM搬移到第一哈希桶或第二哈希桶中， 这样可以有效的节约 TCAM空间， 避免反复添加删除后 TCAM可用空间的降低。

如图 2所示， 本发明实施例中还提供一种关键字的查找方法 ， 该查找方 法中的关键字按前述关键字的存储方法进行存 储， 该查找方法可以包括： 歩骤 201、 在所述 TCAM 中查找所述关键字或所述关键字的压缩关键 歩骤 202、 若在所述 TCAM 中未查找到所述关键字或所述关键字的压缩 关键字， 则在第一哈希桶中查找所述关键字的压缩关键 字；

歩骤 203、 若在第一哈希桶中仍未查找到所述关键字的压 缩关键字， 则 在第二哈希桶中查找所述关键字的压缩关键字 。

由图 2所示流程可以得知， 本发明实施例中， 按前述关键字的存储方法 存储关键字后， 先在 TCAM 中查找关键字或关键字的压缩关键字， 若能够查 找到， 则可以避免查找第一哈希桶和 /或第二哈希桶， 从而使查找延时大幅 降低， 查找效率得以有效提高。 具体实施时， 查找延时还可以稳定在一个固 定值。 当然， 实施过程中， 为了提高查找的准确性， 在第一哈希桶和 /或第二 哈希桶中查找到关键字的压缩关键字后， 还可以进一歩按该压缩关键字对应 的关键字指针查找完整的关键字， 以确定是否真正能够找到要找的关键字。

一个实施例中， 若在第一哈希桶中查找到所述关键字的压缩关 键字， 则 进一歩按该压缩关键字对应的关键字指针查找 所述关键字； 若未查找到， 则 在第二哈希桶中查找所述关键字的压缩关键字 ； 若在第二哈希桶中查找到所 述关键字的压缩关键字， 则进一歩按该压缩关键字对应的关键字指针查 找所 述关键字。

查找过程中， 若在第一哈希桶和第二哈希桶中均查找到所述 关键字的压 缩关键字， 还可以将所述关键字的压缩关键字及所述关键 字的指针搬移到所 述 TCAM 中， 这样可以保证下次查找时不会既访问第一哈希 桶又访问第二哈 希桶， 从而进一歩提高查找的效率。

下面结合图例综合说明上述实施例中关键字的 存储方法和查找方法。 图 3为上述关键字的存储方法和查找方法的示意� �。 图 3中的哈希桶包括： 第 一哈希桶 （HT1 ) 、 第二哈希桶 （HT2 ) ； 图 3中还示出了第一哈希桶、 第二 哈希桶和 TCAM 中存储的关键字指针指向的完整关键字， 这些完整关键字存 储于一个完整关键字桶 （KT ) 。 哈希桶通过存储接口 0 与查找引擎相互通 信； 完整关键字桶通过存储接口 1 与查找引擎相互通信； 查找引擎与 TCAM 相互通信； TCAM与 SRAM相互通信。 如图 3所示， 由第一哈希桶、 第二哈希 桶和 TCAM配合完成对关键字的操作过程。 第一哈希桶和第二哈希桶的桶深 可以不同。

图 4具体示出了图 3所示第一哈希桶、 第二哈希桶和 TCAM所存储的关 键字、 压缩关键字和关键字的指针。 其中， 第一哈希桶和第二哈希桶中均存 储有压缩关键字和对应关键字指针， 关键字的指针还指向完整关键字桶中完 整的关键字。 TCAM中存储有关键字和关键字的指针。 本领域普通技术人员可以理解实现上述实施例 方法中的全部或部分歩骤 是可以通过程序来指令相关的硬件完成， 所述的程序可以存储于一计算机可 读取存储介质中， 该程序在执行时， 可以包括上述实施例方法中的全部或部 分歩骤， 所述的存储介质可以包括： R0M、 RAM, 磁盘、 光盘等。

本发明实施例中还提供了一种关键字的存储装 置和查找装置， 如下面的 实施例所述。 由于该些装置解决问题的原理与关键字存储方 法和查找方法相 似， 因此该些装置的实施可以参见方法的实施， 重复之处不再赘述。

如图 5所示， 本发明实施例中的关键字的存储装置可以包括 ： 第一哈希桶查找模块 501， 用于将关键字经第一哈希函数运算， 获得第 一哈希桶的地址； 根据第一哈希桶的地址， 查找第一哈希桶；

第二哈希桶查找模块 502， 用于将所述关键字经第二哈希函数运算， 获 得第二哈希桶的地址； 根据第二哈希桶的地址， 查找第二哈希桶；

第一确定模块 503， 用于确定第一哈希桶中没有与所述关键字的压 缩关 键字相冲突的压缩关键字， 所述关键字的压缩关键字由所述关键字经第三 哈 希函数运算获得；

第一存储模块 504， 用于在第一哈希桶有剩余空间时， 将所述关键字的 压缩关键字及所述关键字的指针存入第一哈希 桶；

第二存储模块 505， 用于在第一哈希桶没有剩余空间、 第二哈希桶有剩 余空间且第二哈希桶中没有与所述关键字的压 缩关键字相冲突的压缩关键字 时， 将所述关键字的压缩关键字及所述关键字的指 针存入第二哈希桶。

如图 6所示， 一个实施例中， 图 5所示关键字的存储装置还可以包括： 第二确定模块 601， 用于确定第一哈希桶中有与所述关键字的压缩 关键 字相冲突的压缩关键字； 第三存储模块 602， 用于将所述关键字及所述关键 字的指针存入 TCAM, 或将所述关键字的压缩关键字及所述关键字的 指针存 入所述 TCAM; 或， 所述第二确定模块 601用于确定第一哈希桶中没有与所述关键字的 压缩关键字相冲突的压缩关键字且没有剩余空 间、 第二哈希桶中有与所述关 键字的压缩关键字相冲突的压缩关键字； 所述第三存储模块 602用于将所述 关键字及所述关键字的指针存入所述 TCAM, 或将所述关键字的压缩关键字 及所述关键字的指针存入所述 TCAM;

或， 所述第二确定模块 601用于确定第一哈希桶和第二哈希桶均没有剩 余空间； 所述第三存储模块 602用于将所述关键字及所述关键字的指针存入 所述 TCAM , 或将所述关键字的压缩关键字及所述关键字的 指针存入所述 TCAMo

如图 7所示， 一个实施例中， 图 6所示关键字的存储装置还可以包括： 第一搬移模块 701， 用于在所述 TCAM 中有与第一哈希桶中压缩关键字 不相冲突的压缩关键字时， 将该压缩关键字及对应的关键字指针搬移到第 一 哈希桶中； 在所述 TCAM 中有与第二哈希桶中压缩关键字不相冲突的压 缩关 键字时， 将该压缩关键字及对应的关键字指针搬移到第 二哈希桶中。

如图 8所示， 本发明实施例中还提供一种关键字的查找装置 ， 所查找的 关键字由图 6 或图 7 所示关键字的存储装置进行存储， 该查找装置可以包 括：

第一关键字查找模块 801， 用于在所述 TCAM 中查找所述关键字或所述 关键字的压缩关键字；

第二关键字查找模块 802， 用于在所述第一关键字查找模块 801未查找 到所述关键字的压缩关键字时， 在第一哈希桶中查找所述关键字的压缩关键 第三关键字查找模块 803， 用于在所述第二关键字查找模块 802未查找 到所述关键字的压缩关键字时， 在第二哈希桶中查找所述关键字的压缩关键 一个实施例中， 二关键字查找模块 802还可以用于: 在第一哈希桶中查找到所述关键字的压缩关键 字时， 按该压缩关键字对 应的关键字指针查找所述关键字；

第三关键字查找模块 803还可以用于： 在第二关键字查找模块 802未查 找到所述关键字时， 在第二哈希桶中查找所述关键字的压缩关键字 ； 在第二 哈希桶中查找到所述关键字的压缩关键字时， 按该压缩关键字对应的关键字 指针查找所述关键字。

如图 9所示， 一个实施例中， 图 8所示关键字的查找装置还可以包括： 第二搬移模块 901， 用于在所述第二关键字查找模块在第一哈希桶 查找 到所述关键字的压缩关键字， 且所述第三关键字查找模块在第二哈希桶中查 找到所述关键字的压缩关键字时， 将所述关键字的压缩关键字及所述关键字 的指针搬移到所述 TCAM中。

本发明实施例中， 将关键字经第一哈希函数运算， 获得第一哈希桶的地 址； 根据第一哈希桶的地址， 查找第一哈希桶； 将所述关键字经第二哈希函 数运算， 获得第二哈希桶的地址； 根据第二哈希桶的地址， 查找第二哈希 桶； 不同于现有技术中仅通过一个哈希函数获得初 始哈希桶地址， 由初始哈 希桶中级连链表指针指向级连哈希桶， 而是通过两个由不同哈希函数独立获 取地址的哈希桶， 来完成对关键字的存储操作， 从而大大提高内存利用率， 节省存储空间和带宽； 并且， 由关键字经不同哈希函数运算获得地址的两个 哈希桶可以采用不同的深度， 可以增加存储的灵活性； 另外， 在第一哈希桶 或第二哈希桶存储关键字时进行的压缩关键字 冲突判断， 也可以避免第一哈 希桶或第二哈希桶中出现压缩关键字冲突的情 况。

本发明实施例中， 引入 TCAM对关键字进行存储操作， 还可以进一歩地 避免哈希桶中出现压缩关键字冲突的情况， 并且， 在上述关键字的查找方法 中， 先在 TCAM 中查找关键字或关键字的压缩关键字， 若能够查找到， 则可 以避免查找第一哈希桶和 /或第二哈希桶， 使查找延时大幅降低， 查找效率 得以有效提高。 另外， 将不再存在冲突的压缩关键字及对应的关键字 指针从 TCAM搬移到哈希桶中， 也可以有效的节约 TCAM空间， 避免反复添加删除后 TCAM可用空间的降低。

以上所述的具体实施例， 对本发明的目的、 技术方案和有益效果进行了 进一歩详细说明， 所应理解的是， 以上所述仅为本发明的具体实施例而已， 并不用于限定本发明的保护范围， 凡在本发明的精神和原则之内， 所做的任 何修改、 等同替换、 改进等， 均应包含在本发明的保护范围之内。