[發(fā)明專利]數(shù)據(jù)處理的方法和裝置

有效

• 申請(qǐng)?zhí)枺?/td>: 201310178900.0
• 申請(qǐng)日: 2013-05-15
• 公開（公告）號(hào): CN103258035B
• 公開（公告）日: 2017-02-08
• 發(fā)明（設(shè)計(jì)）人: 陳清付;劉濤;梁振宇
• 申請(qǐng)（專利權(quán)）人: 華為技術(shù)有限公司
• 主分類號(hào): G06F17/30
• 分類號(hào): G06F17/30
• 代理公司: 北京龍雙利達(dá)知識(shí)產(chǎn)權(quán)代理有限公司11329
• 代理人: 毛威,張亮

技術(shù)領(lǐng)域

本發(fā)明涉及信息技術(shù)領(lǐng)域，并且更具體地，涉及數(shù)據(jù)處理的方法和裝置。

背景技術(shù)

哈希（Hash）算法以其均勻散列、快速收縮、不可逆等特性，在海量用戶管理和信息安全等相關(guān)領(lǐng)域被廣泛應(yīng)用。

在硬件加速實(shí)現(xiàn)的Hash計(jì)算中以布茲（Robert?Uzgalis，Buz）/BKDR（Brian?Kernighan?and?Dennis?Ritchie）算法最為常見，實(shí)現(xiàn)時(shí)常規(guī)做法是通過以特征字的線性查表后，經(jīng)過特征字的字節(jié)長度次迭代移位模2加法計(jì)算后獲得均勻的Hash散列值，因此其計(jì)算速度取決于查表效率和待計(jì)算的特征字長度，一般匹配速度慢，不能很好滿足高速網(wǎng)絡(luò)中對(duì)大量流進(jìn)行匹配的需要。

Buz?hash只需要移位及異或操作，適合于硬件實(shí)現(xiàn)，在業(yè)內(nèi)廣泛應(yīng)用于硬件hash計(jì)算。然而，現(xiàn)有的Buz?hash算法只能串行查找，在輸入的關(guān)鍵字比較長，且對(duì)性能要求比較高的地方，不能夠滿足需求。

發(fā)明內(nèi)容

本發(fā)明實(shí)施例提供了一種數(shù)據(jù)處理的方法和裝置，能夠提升系統(tǒng)性能。

第一方面，提供了一種數(shù)據(jù)處理的方法，包括：獲取關(guān)鍵字的N個(gè)字節(jié)，N為整數(shù)且N≥2；根據(jù)該N個(gè)字節(jié)查J張布茲哈希表Buz?hash?table，得到N個(gè)查表結(jié)果，2≤J≤N，該J張Buz?hash?table中，后一張Buz?hash?table相對(duì)前一張Buz?hash?table進(jìn)行了循環(huán)移位；根據(jù)該N個(gè)查表結(jié)果確定該N個(gè)字節(jié)的哈希結(jié)果。

在第一種可能的實(shí)現(xiàn)方式中，該J張Buz?hash?table[table₀,table₁,...,table_J-1]中，table_j相對(duì)table_j-1循環(huán)移2位，j=1,...,J-1；根據(jù)該N個(gè)字節(jié)查J張布茲哈希表Buz?hash?table，包括：對(duì)于該N個(gè)字節(jié)[k₀,k₁,...,k_N-1]中的字節(jié)k_n查n=0,1,...,N-1，得到該N個(gè)查表結(jié)果{T[k₀],T[k₁],...,T[k_N-1]}；根據(jù)該N個(gè)查表結(jié)果確定該N個(gè)字節(jié)的哈希結(jié)果，包括：將該N個(gè)查表結(jié)果中的T[k₁],T[k₃],T[k₅],...各循環(huán)移1位，作為相應(yīng)的RT[k₁],RT[k₃],RT[k₅],...，將該N個(gè)查表結(jié)果中的T[k₀],T[k₂],T[k₄],...保持不變，作為相應(yīng)的RT[k₀],RT[k₂],RT[k₄],...，得到{RT[k₀],RT[k₁],...,RT[k_N-1]}；對(duì){RT[k₀],RT[k₁],...,RT[k_N-1]}進(jìn)行異或得到該N個(gè)字節(jié)的哈希結(jié)果。

在第二種可能的實(shí)現(xiàn)方式中，J=N，該J張Buz?hash?table[table₀,table₁,...,table_J-1]中，table_j相對(duì)table_j-1循環(huán)移1位，j=1,...,J-1；根據(jù)該N個(gè)字節(jié)查J張布茲哈希表Buz?hash?table，包括：對(duì)于該N個(gè)字節(jié)[k₀,k₁,...,k_N-1]中的字節(jié)k_n查table_n，n=0,1,...,N-1，得到該N個(gè)查表結(jié)果{T[k₀],T[k₁],...,T[k_N-1]}；根據(jù)該N個(gè)查表結(jié)果確定該N個(gè)字節(jié)的哈希結(jié)果，包括：對(duì)該N個(gè)查表結(jié)果{T[k₀],T[k₁],...,T[k_N-1]}進(jìn)行異或得到該N個(gè)字節(jié)的哈希結(jié)果。