用於設計高速緩存的數據結構，具有高效的插入，刪除和最高值檢索

Question

我必須實現具有普通高速緩存操作的高速緩存，以及從高速緩存中快速檢索最大元素的功能。

你可以請建議數據結構來實現這個？

我正在考慮使用哈希映射和列表來維護最小元素。

建議更好的複雜性的其他方法。

Answer 1

堆是最大元素的快速恢復偉大。

Answer 2

有一種類型的結構，我稱之爲指數後視列表，這些列表經常被操作系統用來跟蹤空閒的內存塊。你開始列表的一些基本大小N（介於8個字節，並在OS的頁面大小），然後建立一個數組（或疊層）：

[list N] 
[list N*2] 
[list N*4] 
[list N*8] 
... 

等等直到某個最大值。爲了維護它們，您只需取一個新條目（S）的大小，然後使用LOG2（S/N）作爲您的偏移量到列表數組中，以確定將哪個列表添加到新的數據塊。當您需要釋放（或返回）最大塊時，只需從最高大小的列表中掃描，直到找到第一個非空列表，然後掃描該列表中最大的塊。