我應該使用什麼數據結構來緩存有序實體

Question

我需要在緩存中存儲一​​些項目，例如聊天消息。我還需要在關鍵值範圍內分割這些項目。例如（返回聊天消息），緩存中最常見的操作是從開始日期到結束日期獲取聊天消息。

我應該考慮什麼數據結構？我正在考慮簡單的數組，但它將適用於O（n）。有沒有更快的數據結構？

Answer 1

使用關聯集合，將數據存儲在array<data>中，但使用散列表來存儲pair<data , arrayIndex>。這樣你可以用o（1）搜索，插入和刪除。

Answer 2

您可以使用像Red-Black Tree這樣的自平衡二叉搜索樹，它以有序方式存儲條目，並將在平均值和最差情況下在O（logn）中提供插入，刪除和搜索。

因此，當您需要日期間隔之間的聊天消息時，您可以搜索您已經訂購的數據範圍的RB樹。