[發明專利]對多線程應用的雜湊表執行并行的重雜湊

有效

• 申請號: 200980159762.3
• 申請日: 2009-04-08
• 公開（公告）號: CN102460392A
• 公開（公告）日: 2012-05-16
• 發明（設計）人: A.A.馬拉霍夫
• 申請（專利權）人: 英特爾公司
• 主分類號: G06F9/46
• 分類號: G06F9/46
• 代理公司: 中國專利代理(香港)有限公司 72001
• 代理人: 張濤;蔣駿

1.一種方法，包括：

為同時被多個線程所共享的雜湊表分配第二數量的桶，所述雜湊表具有第一數量的桶，桶的第二數量至少等于桶的第一數量并且第二數量的桶中的每一個被邏輯映射到第一或第二數量的桶中對應的一個母桶；并且

公布包括第一和第二數量的桶的雜湊表的更新容量，其中所述分配通過公布所述更新容量而完成而不對所述第一數量的桶的內容執行任何重雜湊。

2.如權利要求1所述的方法，進一步包括執行檢查而并不閉鎖桶以確定是否需要重雜湊。

3.如權利要求1所述的方法，進一步包括隨后在對存在于第一數量的桶的第一桶中的數據對執行查找操作時，將該第一桶的內容重雜湊到第二數量的桶的第二桶。

4.如權利要求1所述的方法，進一步包括使用所述更新容量計算桶索引，使用所述桶索引訪問桶，確定該桶沒有被重雜湊，并且使用所述更新容量遞歸地計算母桶的母桶索引，直至找到該桶被邏輯映射到的、被重雜湊的根桶。

5.如權利要求4所述的方法，進一步包括在搜索查找請求的數據對時或之前將被重雜湊的根桶的內容的至少一部分重雜湊到所述桶中。

6.如權利要求5所述的方法，進一步包括在根桶僅有一部分內容被重雜湊時對部分重雜湊指示符進行置位。

7.如權利要求4所述的方法，進一步包括在桶中搜索查找請求的數據對并返回該數據對，并且不對桶的內容進行重雜湊。

8.如權利要求1所述的方法，進一步包括響應于由第一線程進行的查找操作，在所述第一數量的桶的第一桶中沒有找到所請求的數據對，將雜湊表容量的當前值與在針對該查找操作確定桶索引時所使用的雜湊表容量的值相比較，并且如果當前值和該值不同，則計算最接近的繼承桶的索引，訪問最接近的繼承桶并且確定該最接近的繼承桶的重雜湊狀態。

9.如權利要求8所述的方法，進一步包括如果重雜湊狀態沒有指示新的（未重雜湊）狀態則重新開始查找操作。

10.如權利要求1所述的方法，進一步包括將多次分配組合為針對第二數量的桶的單次分配。

11.如權利要求1所述的方法，進一步包括公布多次分配并且一次性公布針對該多次分配的更新容量。

12.一種包括機器可讀存儲介質的物品，所述機器可讀存儲介質包括指令，所述指令在被機器執行的情況下使得該機器能夠執行一種方法，所述方法包括：

對同時被多個線程所共享的雜湊表執行查找操作，包括使用該雜湊表的第一容量值計算該雜湊表的第一桶的桶索引，使用所述桶索引訪問所述第一桶，并且確定所述第一桶不包括所述查找操作的數據對；

將所述雜湊表容量的當前容量值與第一容量值進行比較，并且如果當前容量值和第一值不同，則使用當前容量值計算更新的桶索引；并且

如果更新的桶索引和所述桶索引不同，則計算下一個桶索引，訪問對應于所述更新的桶索引的下一個桶，并且確定該下一個桶的重雜湊狀態。

13.如權利要求12所述的物品，其中所述方法進一步包括如果重雜湊狀態沒有指示新的狀態則重新開始查找操作。

14.如權利要求12所述的物品，其中所述方法進一步包括在查找操作期間訪問雜湊表的桶的同時對該桶進行重雜湊。

15.如權利要求12所述的物品，其中所述查找操作由第一線程執行，并且所述雜湊表在第一線程獲得用于計算的第一容量值并且第三線程在第一線程訪問第一桶之前開始對第一桶進行重雜湊之后由第二線程進行擴展。