[發明專利]散列沖突降低系統

有效

• 申請號: 201310168101.5
• 申請日: 2013-05-06
• 公開（公告）號: CN103425725B
• 公開（公告）日: 2017-04-12
• 發明（設計）人: J·L·卡爾維尼亞克;C·M·德卡塞提斯;F·J·韋普蘭肯;D·溫德
• 申請（專利權）人: 國際商業機器公司
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 北京市中咨律師事務所11247
• 代理人: 張亞非,于靜

1.一種系統，包括

包含計算機處理器的控制器，在與引入到控制器的新組件相接口時，該控制器降低插入次數和散列沖突中的至少一個；

沖突避免裝置，其通過使用多個表以及每個桶多個鍵來降低散列沖突;

與控制器通信的散列裝置，以將所述多個鍵映射到所述多個表，其中，該散列裝置使用單個散列邏輯在一個鍵改變時提供雪崩效應，所述一個鍵改變導致所述多個表中的將近一半位改變。

2.如權利要求1所述的系統，其中，所述單個散列邏輯基于Cuckoo算法。

3.如權利要求1所述的系統，其中，所述單個散列邏輯包括可配置的循環冗余檢查多項式。

4.如權利要求1所述的系統，其中，所述散列裝置基于雪崩效應提供所述多個表的并行表查找。

5.如權利要求1所述的系統，其中，所述雪崩效應基于用于所述多個表中的每個的正交散列函數，并且所述單個散列邏輯實現每個正交散列函數。

6.如權利要求5所述的系統，其中，所述單個散列邏輯的每位輸出包括鍵位的匯集結果。

7.如權利要求6所述的系統，其中，所述匯集結果是由異或函數產生的。

8.如權利要求1所述的系統，其中，所述多個表是可配置的。

9.如權利要求8所述的系統，其中，通過控制單個散列邏輯輸出的位數，所述多個表的全局負載是可配置的。

10.一種方法，包括：

當新組件被引入到包含計算機處理器的控制器時，降低插入次數和散列沖突中的至少一個；

由沖突避免裝置通過使用多個表和每個桶多個鍵來降低散列沖突；以及

使用與控制器通信的散列裝置將所述多個鍵映射到所述多個表，該散列裝置使用單個散列邏輯在一個鍵改變時提供雪崩效應，所述一個鍵改變導致多個表中的將近一半位改變。

11.如權利要求10所述的方法，還包括基于雪崩效應通過散列裝置來提供所述多個表的并行表查找。

12.如權利要求10所述的方法，還包括使雪崩效應基于用于所述多個表中的每個的正交散列函數，并且所述單個散列邏輯實現每個正交散列函數。

13.如權利要求12所述的方法，還包括匯集所述單個散列邏輯的每位輸出的鍵位的結果。

14.如權利要求10所述的方法，還包括使得所述多個表可配置。

15.如權利要求14所述的方法，還包括控制單個散列邏輯輸出的位數，從而所述多個表的全局負載是可配置的。