[發明專利]哈希數據處理方法和裝置

有效

• 申請號: 201010142145.7
• 申請日: 2010-04-02
• 公開（公告）號: CN101826107A
• 公開（公告）日: 2010-09-08
• 發明（設計）人: 劉振肖
• 申請（專利權）人: 華為技術有限公司
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 北京同立鈞成知識產權代理有限公司 11205
• 代理人: 劉芳

技術領域

本發明實施例涉及通信領域，尤其涉及一種哈希數據處理方法和裝置。

背景技術

布隆過濾器(以下簡稱：Bloom?Filter)是一種空間效率很高的隨機數據 結構，它利用位數組表示一個集合，并能判斷一個元素是否屬于這個集合。

現有的Bloom?Filter一般采用計數式布隆過濾器(以下簡稱：counting Bloom?filter)以支持刪除操作。以三個哈希函數h1、h2和h3舉例來說，在 添加數據時，可以采用三個哈希函數h1、h2和h3對原始的鍵值(以下簡稱： key)進行哈希變換，從而得到三個哈希表地址，然后將與這三個哈希表地址 對應的計數器加1，在每一次添加數據時，與哈希表地址對應的計數器均需 要加1。在查找原始數據時，該原始key經過哈希函數h1、h2和h3得到三個 哈希表地址，如果三個哈希表地址對應的計數器的值都大于0，則表示查找 到對應的數據。在刪除數據時，需要刪除的原始key，經過哈希函數h1、h2 和h3得到三個哈希表地址，然后將這三個哈希表地址對應的計數器都減1。 由于片內容量的限制，現有的counting?Bloom?filter為了支持大容量集合，一 般都采用片外方式實現。

在實現本發明過程中，發明人發現現有技術中至少存在如下問題：在采 用counting?Bloom?filter判定某一個數據是否屬于該集合時，在片外需要隨機 訪問多個地址，判斷效率較低。

發明內容

本發明實施例提供一種哈希數據處理方法和裝置。

本發明實施例提供一種哈希數據處理方法，包括：

對所需添加的數據進行第一哈希處理，獲取第一哈希值；

若與所述第一哈希值對應的片外哈希表的第一地址上存儲用于表示所需 添加的數據已存在的第一標識，則對所述數據進行第二哈希處理獲取第二哈 希值，并將所述第二哈希值與所述第一地址添加到片內哈希表中。

本發明實施例提供另一種哈希數據處理方法，包括：

對所需查找的數據進行第一哈希處理獲取第一哈希值，對所述數據進行 第二哈希處理獲取第二哈希值，在片內哈希表中查找與所述第一哈希值對應 的第一地址和所述第二哈希值；

若所述片內哈希表中不存在所述第一地址和第二哈希值，則在片外哈希 表中查找所述第一地址上存儲的用于表示所需查找的數據是否已存在的標識 信息。

本發明實施例提供一種哈希數據處理裝置，包括：

第一處理模塊，用于對所需添加的數據進行第一哈希處理，獲取第一哈希 值；

第二處理模塊，用于若與所述第一哈希值對應的片外哈希表的第一地址 上存儲用于表示所需添加的數據已存在的第一標識，則對所述數據進行第二 哈希處理獲取第二哈希值，并將所述第二哈希值與所述第一地址添加到片內 哈希表中。

本發明實施例提供另一種哈希數據處理裝置，包括：

第三處理模塊，用于對所需查找的數據進行第一哈希處理獲取第一哈希 值，對所述數據進行第二哈希處理獲取第二哈希值，在片內哈希表中查找與 所述第一哈希值對應的第一地址和所述第二哈希值；

第四處理模塊，用于若所述片內哈希表中不存在所述第一地址和第二哈 希值，則在片外哈希表中查找所述第一地址上存儲的用于表示所需查找的數 據是否已存在的標識信息。

本發明實施例，在添加或者查找數據時，片外只需要采用一個哈希函數 對所需添加或者查找的數據進行哈希變換，從而只需訪問一次片外地址，因 此，提高了判斷效率。

附圖說明

為了更清楚地說明本發明實施例或現有技術中的技術方案，下面將對實 施例或現有技術描述中所需要使用的附圖作一簡單地介紹，顯而易見地，下 面描述中的附圖是本發明的一些實施例，對于本領域普通技術人員來講，在 不付出創造性勞動性的前提下，還可以根據這些附圖獲得其他的附圖。

圖1為本發明哈希數據處理方法一個實施例的流程圖；

圖2為本發明哈希數據處理方法另一個實施例的流程圖；

圖3為本發明哈希數據處理方法再一個實施例的流程圖；

圖4為本發明哈希數據處理方法又一個實施例的流程圖；

圖5為本發明哈希數據處理裝置一個實施例的結構示意圖；

圖6為本發明哈希數據處理裝置再一個實施例的結構示意圖；