[發明專利]基于內存的散列表的構建方法、文本查找方法及相應裝置

在審

• 申請號: 201410856681.1
• 申請日: 2014-12-31
• 公開（公告）號: CN104572983A
• 公開（公告）日: 2015-04-29
• 發明（設計）人: 肖冰
• 申請（專利權）人: 北京銳安科技有限公司
• 主分類號: G06F17/30
• 分類號: G06F17/30;G06F12/08
• 代理公司: 北京品源專利代理有限公司 11332
• 代理人: 胡彬;路凱

技術領域

本發明實施例涉及計算機技術領域，尤其涉及基于內存的散列表的構建方法、文件查找方法及相應裝置。

背景技術

散列函數是一種從任何一種數據中創建小的數字“指紋”的方法，可以把任何一種數據(例如消息)壓縮成摘要。所述摘要，也即散列值，其基本特性包括：如果兩個散列值是不同的，那么對應的兩個原始數據也是不同的(同一散列函數)，如果兩個散列值相同，那么兩個原始數據可能相同，也可能不同；典型的散列函數都是無限定義域和有限的值域，一般散列值的長度比原始值長度要小。

散列表技術是散列函數的一個主要應用，常用于數據的快速查找，其基本思想把數據在散列表中的存儲位置和該數據的散列值之間建立一種映射關系，散列值在這種映射關系下的像，就是相應記錄在散列表中的存儲位置。

在通常情況下，散列函數是一個壓縮映像，因此無論如何設計散列函數，也無法完全避免散列沖突(即不同數據的散列值相同)的問題。而鏈地址法(開散列法)是一種常見的解決沖突的方法，其做法是將所有沖突的數據鏈接在同一個單向鏈表中，并將散列表定義為由B(表長)個單表頭指針組成的指針數據F[0,1,….,B-1]。

鏈地址法本身是內存利用率比較高的一種處理沖突方法。若選擇的散列函數能使同義詞(散列值相同的不同數據)的個數等于散列表的平均長度：n/B(n為數據的個數)，則查找定位的時間將是一個小常數(與單向鏈表F[i]的最大長度相關)。

目前，海量數據處理中常用到文本的查找定位。采用上述鏈地址法，在內存中構建用于查找海量文本的散列表的方案，雖然在一定程度上提高了內存利用率，但其提高效果并不是十分顯著，依然會占用較多內存。

發明內容

本發明實施例提供基于內存的散列表的構建方法、文件查找方法及相應裝置，以更好的提高內存利用率，更加節約內存。

一方面，本發明實施例提供了一種基于內存的散列表的構建方法，該方法包括：

獲取用于查找的文本數據；

使用預設的主散列函數，計算所述文本數據對應的主散列值，并根據設定的映射算法確定所述主散列值對應的散列表入口地址；

使用預設的至少一個從散列函數，計算所述文本數據對應的從散列值，并基于所述從散列值得到目標散列值；

將所述目標散列值存儲至內存中與所述散列表入口地址對應的單向鏈表，以構建散列表。

另一方面，本發明實施例還提供了一種文件查找方法，該方法包括：

獲取本次待查找的文本數據；

使用預設的主散列函數，計算所述文本數據對應的主散列值，并根據設定的映射算法確定所述主散列值對應的散列表入口地址；

使用預設的至少一個從散列函數，計算所述文本數據對應的從散列值，并基于所述從散列值得到目標散列值；

遍歷內存中構建的散列表中與所述散列表入口地址對應的單向鏈表，查找所述單向鏈表中是否存在信息域包含有所述目標散列值的節點。

再一方面，本發明實施例還提供了一種基于內存的散列表的構建裝置，該裝置包括：

文本數據獲取單元，用于獲取用于查找的文本數據；

散列表入口地址確定單元，用于使用預設的主散列函數，計算所述文本數據對應的主散列值，并根據設定的映射算法確定所述主散列值對應的散列表入口地址；

目標散列值生成單元，用于使用預設的至少一個從散列函數，計算所述文本數據對應的從散列值，并基于所述從散列值得到目標散列值；

目標散列值存儲單元，用于將所述目標散列值存儲至內存中與所述散列表入口地址對應的單向鏈表，以構建散列表。再一方面，本發明實施例還提供了一種文件查找裝置，該裝置包括：

文本數據獲取單元，用于獲取本次待查找的文本數據；

散列表入口地址確定單元，用于使用預設的主散列函數，計算所述文本數據對應的主散列值，并根據設定的映射算法確定所述主散列值對應的散列表入口地址；

目標散列值生成單元，用于使用預設的至少一個從散列函數，計算所述文本數據對應的從散列值，并基于所述從散列值得到目標散列值；

目標散列值查找單元，用于遍歷內存中構建的散列表中與所述散列表入口地址對應的單向鏈表，查找所述單向鏈表中是否存在信息域包含有所述目標散列值的節點。