DataStructure用於存儲元素並按照它們的使用頻率/時間戳順序對它們排序

我有一個問題陳述：假設有Employee類，並且必須設計一個類來提供get和put方法來訪問和添加僱員。 Employee class是第三方類，所以我們無法對其進行更改。有一個內存限制，像最多50k員工可以存儲。現在，如果同時加入的員工，如果達到內存限制然後按照以下任何方式的刪除一個員工，並添加新員工：DataStructure用於存儲元素並按照它們的使用頻率/時間戳順序對它們排序

訪問頻率
的時間戳的基礎上的基礎上。一個與舊的時間戳應該被刪除

我可以考慮採取兩個hashmaps： - 一個用於存儲員工對象和一個與關鍵和時間戳或頻率值的員工。

但這不是最佳解決方案。請提供哪些數據結構可以用來解決這個問題的寶貴建議。

來源

2016-10-02 Infotechie

可能的重複http://stackoverflow.com/questions/221525/how-would-you-implement-an-lru-cache-in-java?rq=1 –

請看看堆數據結構[鏈接]（https://en.wikipedia.org/wiki/Heap_%28data_structure%29） –

參考LRU緩存 –

只需使用普通集合來存儲您的員工。在添加新員工並檢測到內存已滿時，只需確定具有最小排序順序標準的員工，並將其從數據庫中刪除即可。

既然你沒有提供的Employee類，我宣佈這裏一個例子：

class Employee { 
    int frequency; 
    Instant lastAccess; 
}

您的數據庫（也可以是鏈表）：

private List<Employee> myDatabase = new ArrayList<>();

與最小評估員工的comporator標準（第一頻率進行比較，如果等於lastAccess進行比較：

public int compare(Employee emp1, Employee emp2) 
{ 
    int result = emp1.frequency - emp2.frequency; 
    if (result == 0) 
    { 
     result = emp1.lastAccess.compareTo(emp2.lastAccess); 
    } 
    return result; 
}

這裏的「主」方法，插入一個新員工到你的數據庫（isMemoryFull的實施留給你）：

private void insertEmp(Employee emp) 
{ 
    if (isMemoryFull()) 
    { 
     Employee minEmp = myDatabase.stream().min(this::compare).get(); 
     myDatabase.remove(minEmp); 
    } 

    myDatabase.add(emp); 
}

注：這適用於Java8 lambda表達式和溪流。對於java < 8，您必須將比較方法正式實現爲比較器，並使用Collections.sort而不是stream（）。min（）方法。

來源

2016-10-02 18:39:05 Heri

員工類是第三方類。我們不能像頻率變量那樣對其進行修改。 – Infotechie

我的Employee類只是一個示例，爲的是我的代碼甚至可以在IDE中編譯。當然，你必須根據你的需要調整比較方法。 – Heri

DataStructure用於存儲元素並按照它們的使用頻率/時間戳順序對它們排序

回答

相關問題