[發明專利]一種基于雙層列表結構的容量擴充方法及系統

有效

• 申請號: 201810111712.9
• 申請日: 2018-02-05
• 公開（公告）號: CN108256103B
• 公開（公告）日: 2019-02-05
• 發明（設計）人: 王建民;黃向東;張金瑞;劉昆;曹高飛;王晨
• 申請（專利權）人: 清華大學
• 主分類號: G06F16/22
• 分類號: G06F16/22
• 代理公司: 北京路浩知識產權代理有限公司 11002
• 代理人: 王瑩;吳歡燕

1.一種基于雙層列表結構的容量擴充方法，其特征在于，所述雙層列表結構的第一層列表為第一數組，所述第一數組中存儲至少一個數組標識，所述雙層列表結構的第二層列表包括至少一個第二數組，每個所述第二數組用于存儲待存儲的數據，每個所述第二數組與且僅與一個所述數組標識對應，所述方法包括：

S1，當每個所述數組標識對應的第二數組中存儲的數據數量均達到最大值時，則創建一個新的第一數組，所述最大值為所述第二數組的最大容量，所述新的第一數組的大小大于當前所述第一數組的大小，并增加所述第二數組的數量；

S2，將當前所述第一數組中存儲的數組標識拷貝到所述新的第一數組中，并將當前所述第一數組替換為所述新的第一數組。

2.根據權利要求1所述的方法，其特征在于，步驟S1中所述當每個所述數組標識對應的第二數組中存儲的數據數量均達到最大值時，則創建一個新的第一數組具體包括：

若當前所述第一數組的大小為n，則所述新的第一數組的大小為n+d，所述d為預設的大小增量；

相應地，新增一個所述第二數組，新增的所述第二數組與所述新的第一數組中的第n+1個數組標識對應。

3.根據權利要求2所述的方法，其特征在于，所述步驟S1之后還包括：當新增的所述第二數組中存儲的數據數量達到所述最大值時，繼續增加所述第二數組的數量，直至所述第二數組的數量與所述數組標識的數量相等。

4.根據權利要求2或3所述的方法，其特征在于，新增的所述第二數組的大小為所述最大值。

5.根據權利要求1所述的方法，其特征在于，所述步驟S1還包括：當所述第二數組的數量為1，且所述第二數組中存儲的數據數量達到了所述第二數組的當前容量而未達到所述最大值時，則創建一個新的第二數組，所述新的第二數組的大小大于當前所述第二數組的大小，且不大于所述最大值；

相應地，所述步驟S2還包括：將當前所述第二數組中存儲的數據拷貝到所述新的第二數組中，并將當前所述第二數組替換為所述新的第二數組。

6.根據權利要求5所述的方法，其特征在于，若當前所述第二數組的大小為m，所述最大值為M，則所述新的第二數組的大小為min(1.5m，M)。

7.一種基于雙層列表結構的容量擴充系統，其特征在于，所述雙層列表結構的第一層列表為第一數組，所述第一數組中存儲至少一個數組標識，所述雙層列表結構的第二層列表包括至少一個第二數組，每個所述第二數組用于存儲待存儲的數據，每個所述第二數組與且僅與一個所述數組標識對應，所述系統包括：

擴容模塊，用于當每個所述數組標識對應的第二數組中存儲的數據數量均達到最大值時，則創建一個新的第一數組，所述最大值為所述第二數組的最大容量，所述新的第一數組的大小大于當前所述第一數組的大小，并增加所述第二數組的數量；

替換模塊，用于將當前所述第一數組中存儲的數組標識拷貝到所述新的第一數組中，并將當前所述第一數組替換為所述新的第一數組。

8.根據權利要求7所述的系統，其特征在于，所述擴容模塊還用于：當所述第二數組的數量為1，且所述第二數組中存儲的數據數量達到了所述第二數組的當前容量而未達到所述最大值時，則創建一個新的第二數組，所述新的第二數組的大小大于當前所述第二數組的大小，且不大于所述最大值；

相應地，所述替換模塊還包括：將當前所述第二數組中存儲的數據拷貝到所述新的第二數組中，并將當前所述第二數組替換為所述新的第二數組。

9.一種基于雙層列表結構的容量擴充方法的設備，其特征在于，包括：

至少一個處理器；以及

與所述處理器通信連接的至少一個存儲器，其中：

所述存儲器存儲有可被所述處理器執行的程序指令，所述處理器調用所述程序指令能夠執行如權利要求1至6任一所述的方法。

10.一種非暫態計算機可讀存儲介質，其特征在于，所述非暫態計算機可讀存儲介質存儲計算機指令，所述計算機指令使所述計算機執行如權利要求1至6任一所述的方法。