[發(fā)明專利]處理哈希沖突的方法及系統(tǒng)

無效

• 申請?zhí)枺?/td>: 201210405722.6
• 申請日: 2012-10-23
• 公開（公告）號: CN102880724A
• 公開（公告）日: 2013-01-16
• 發(fā)明（設(shè)計）人: 黃嫻婷;顧祥洪
• 申請（專利權(quán)）人: 盛科網(wǎng)絡(luò)（蘇州）有限公司
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 蘇州威世朋知識產(chǎn)權(quán)代理事務(wù)所(普通合伙) 32235
• 代理人: 楊林潔

1.一種處理哈希沖突的方法，其特征在于，包括如下步驟：

S1、將用于存儲哈希數(shù)據(jù)的表項進行拆分，所述表項包括對應(yīng)于第一哈希函數(shù)的第一表項、對應(yīng)于第二哈希函數(shù)的第二表項；

S2、接收哈希關(guān)鍵字，并判斷是否發(fā)生哈希沖突，若在第一表項中發(fā)生沖突，則按照第二哈希函數(shù)將所述哈希關(guān)鍵字存儲于第二表項的相應(yīng)位置；若無沖突，則按照第一哈希函數(shù)將所述哈希關(guān)鍵字存儲于第一表項的相應(yīng)位置；

S3、根據(jù)所述第一、第二哈希函數(shù)，依次在第一、第二表項中查找哈希關(guān)鍵字對應(yīng)的條目。

2.根據(jù)權(quán)利要求1所述的方法，其特征在于，若待存關(guān)鍵字在第一、第二表項中均發(fā)生哈希沖突，其中，第一表項中相沖突的為第一關(guān)鍵字，第二表項中相沖突的為第二關(guān)鍵字，則所述步驟S2還包括：

將第一關(guān)鍵字從第一表項移除，并按照第二哈希函數(shù)存儲于第二表項的相應(yīng)位置；

將待存關(guān)鍵字按照第一哈希函數(shù)存儲于第一表項的相應(yīng)位置。

3.根據(jù)權(quán)利要求1所述的方法，其特征在于，若待存關(guān)鍵字在第一、第二表項中均發(fā)生哈希沖突，其中，第一表項中相沖突的為第一關(guān)鍵字，第二表項中相沖突的為第二關(guān)鍵字，則所述步驟S2還包括：

將第二關(guān)鍵字從第二表項移除，并按照第一哈希函數(shù)存儲于第一表項的相應(yīng)位置；

將待存關(guān)鍵字按照第二哈希函數(shù)存儲于第二表項的相應(yīng)位置。

4.根據(jù)權(quán)利要求2或3所述的方法，其特征在于，在所述步驟S2之后，該方法還包括：設(shè)置公共溢出區(qū)，若待存關(guān)鍵字在第一、第二表項仍發(fā)生哈希沖突，則將其存儲于所述公共溢出區(qū)。

5.根據(jù)權(quán)利要求4所述的方法，其特征在于，所述步驟S3具體為：

S31、根據(jù)第一哈希函數(shù)，在第一表項中相應(yīng)位置處查找待查哈希關(guān)鍵字，若查找成功，則結(jié)束查找；若未查找成功，跳轉(zhuǎn)步驟S32；

S32、根據(jù)第二哈希函數(shù)，在第二表項中相應(yīng)位置處查找待查哈希關(guān)鍵字，若查找成功，則結(jié)束查找；若未查找成功，跳轉(zhuǎn)步驟S33；

S33、在所述公共溢出區(qū)查找待查關(guān)鍵字。

6.一種處理哈希沖突的系統(tǒng)，其特征在于，包括如下單元：

表項拆分單元、用于將用于存儲哈希數(shù)據(jù)的表項進行拆分，所述表項包括對應(yīng)于第一哈希函數(shù)的第一表項、對應(yīng)于第二哈希函數(shù)的第二表項；

哈希存儲單元、用于接收哈希關(guān)鍵字，并判斷是否發(fā)生哈希沖突，若在第一表項中發(fā)生沖突，則按照第二哈希函數(shù)將所述哈希關(guān)鍵字存儲于第二表項的相應(yīng)位置；若無沖突，則按照第一哈希函數(shù)將所述哈希關(guān)鍵字存儲于第一表項的相應(yīng)位置；

哈希查找單元、用于根據(jù)所述第一、第二哈希函數(shù)，依次在第一、第二表項中查找哈希關(guān)鍵字對應(yīng)的條目。

7.根據(jù)權(quán)利要求6所述的系統(tǒng)，其特征在于，若待存關(guān)鍵字在第一、第二表項中均發(fā)生哈希沖突，其中，第一表項中相沖突的為第一關(guān)鍵字，第二表項中相沖突的為第二關(guān)鍵字，則所述哈希存儲單元還包括一哈希遷移單元，該哈希遷移單元用于：

將第一關(guān)鍵字從第一表項移除，并按照第二哈希函數(shù)存儲于第二表項的相應(yīng)位置；

將待存關(guān)鍵字按照第一哈希函數(shù)存儲于第一表項的相應(yīng)位置。

8.根據(jù)權(quán)利要求6所述的系統(tǒng)，其特征在于，若待存關(guān)鍵字在第一、第二表項中均發(fā)生哈希沖突，其中，第一表項中相沖突的為第一關(guān)鍵字，第二表項中相沖突的為第二關(guān)鍵字，則所述哈希存儲單元還包括一哈希遷移單元，該哈希遷移單元用于：

將第二關(guān)鍵字從第二表項移除，并按照第一哈希函數(shù)存儲于第一表項的相應(yīng)位置；

將待存關(guān)鍵字按照第二哈希函數(shù)存儲于第二表項的相應(yīng)位置。

9.根據(jù)權(quán)利要求7或8所述的系統(tǒng)，其特征在于，所述哈希存儲單元還包括一公共存儲單元，其用于：若待存關(guān)鍵字在第一、第二表項仍發(fā)生哈希沖突，則將其存儲于所述公共溢出區(qū)。

10.根據(jù)權(quán)利要求9所述的系統(tǒng)，其特征在于，所述哈希查找單元具體用于：

根據(jù)第一哈希函數(shù)，在第一表項中相應(yīng)位置處查找待查哈希關(guān)鍵字，若查找成功，則結(jié)束查找；若未查找成功，則根據(jù)第二哈希函數(shù)，在第二表項中相應(yīng)位置處查找待查哈希關(guān)鍵字，若查找成功，則結(jié)束查找；若未查找成功，則在所述公共溢出區(qū)查找待查關(guān)鍵字。