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

在審

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

1.一種基于內存的散列表的構建方法，其特征在于，包括：

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

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

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

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

2.根據權利要求1所述的方法，其特征在于，使用預設的至少一個從散列函數，計算所述文本數據對應的從散列值，并基于所述從散列值得到目標散列值，包括：

分別使用預設的多個從散列函數中的各個從散列函數，計算所述文本數據對應的從散列值；

將計算得到的各個從散列值合并在一起，生成目標散列值。

3.根據權利要求1所述的方法，其特征在于，將所述目標散列值存儲至內存中與所述散列表入口地址對應的單向鏈表，以構建散列表，包括：

判斷內存中所述散列表入口地址處，是否存儲有用于指向與所述散列表入口地址對應的單向鏈表的表頭指針；

如果是，則在所述單向鏈表的隊尾插入一個新節點，將所述目標散列值存儲至所述新節點中的信息域；

如果否，則創建用于指向與所述散列表入口地址對應的單向鏈表的表頭指針，存儲至所述散列表入口地址處，并在所述內存中的所述表頭指針指向的存儲位置處，創建所述單向鏈表的第一個節點，將所述目標散列值存儲至所述第一個節點中的信息域。

4.根據權利要求1-3中任一項所述的方法，其特征在于，所述主散列函數和所述從散列函數為BKDRHash函數、APHash函數、DJBHash函數、JSHash函數、RSHash函數、SDBMHash函數、PJWHash函數、ELFHash函數和DEKHash函數中兩種不同的散列函數；

所述設定的映射算法為質數取余法、平方取中法或折疊法。

5.一種文本查找方法，其特征在于，包括：

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

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

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

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

6.一種基于內存的散列表的構建裝置，其特征在于，包括：

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

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

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

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

7.根據權利要求6所述的裝置，其特征在于，所述目標散列值生成單元，具體用于：

分別使用預設的多個從散列函數中的各個從散列函數，計算所述文本數據對應的從散列值；

將計算得到的各個從散列值合并在一起，生成目標散列值。

8.根據權利要求6所述的裝置，其特征在于，所述目標散列值存儲單元，具體用于：

判斷內存中所述散列表入口地址處，是否存儲有用于指向與所述散列表入口地址對應的單向鏈表的表頭指針；

如果是，則在所述單向鏈表的隊尾插入一個新節點，將所述目標散列值存儲至所述新節點中的信息域；

如果否，則創建用于指向與所述散列表入口地址對應的單向鏈表的表頭指針，存儲至所述散列表入口地址處，并在所述內存中的所述表頭指針指向的存儲位置處，創建所述單向鏈表的第一個節點，將所述目標散列值存儲至所述第一個節點中的信息域。