排序瀏覽歷史數據結構

假設我想實現瀏覽器歷史記錄功能。如果我第一次訪問這個網址，它會進入歷史記錄，如果我再次訪問同一頁面，它會出現在歷史記錄列表中。可以說我只顯示前20個網站，但我可以選擇查看上個月，上週等歷史記錄。排序瀏覽歷史數據結構

這是最好的方法是什麼？我會使用哈希映射插入/檢查它是否被訪問過，但如何有效地排序最近訪問，我不想使用樹映射或樹集。另外，我如何存儲數週和數月的歷史。瀏覽器關閉時是否寫入磁盤？當我點擊清除歷史記錄時，數據結構如何刪除？

來源

2014-02-19 user775093

如果使用哈希映射，則無法快速檢索排序結果。爲什麼你不想使用樹形圖，又名紅黑色的搜索樹？ – mbroshi

，因爲紅黑樹內部需要大量的旋轉來保持平衡，特別是如果有很多的增加，我假設發生在瀏覽器中，因爲用戶可以從已知網站跳到新網站。 HashMap會表現更好，問題是使用輔助數據結構進行排序並在內容中移動。 – user775093

您希望在歷史緩存中有多少個網站？如果你一年有10萬頁，我會感到驚訝，但即使是100萬也不是什麼大不了的事。只需將它們存儲在線性列表中並按順序搜索即可。這對於像瀏覽器這樣的用戶界面應用來說足夠快了。 –

這是Java-ish代碼。

你需要兩個數據結構：一個哈希映射和一個雙向鏈表。雙向鏈表包含歷史對象（其中包含一個url字符串和一個時間戳），按時間順序排序;哈希映射是一個Map<String, History>，以網址爲關鍵。

class History { 
    History prev 
    History next 
    String url 
    Long timestamp 
    void remove() { 
    prev.next = next 
    next.prev = prev 
    next = null 
    prev = null 
    } 
}

當您向歷史記錄中添加url時，請檢查它是否位於哈希映射中;如果它然後更新它的時間戳，請將其從鏈接列表中刪除，並將其添加到鏈接列表的末尾。如果它不在哈希映射中，則將其添加到哈希映射中，並將其添加到鏈表的末尾。添加一個url（不管它是否已經在哈希映射中）是一個常量時間操作。

class Main { 
    History first // first element of the linked list 
    History last // last element of the linked list 
    HashMap<String, History> map 

    void add(String url) { 
    History hist = map.get(url) 
    if(hist != null) { 
     hist.remove() 
     hist.timestamp = System.currenttimemillis() 
    } else { 
     hist = new History(url, System.currenttimemillis()) 
     map.add(url, hist) 
    } 
    last.next = hist 
    hist.prev = last 
    last = hist 
    } 
}

要獲取來自例如在最後一週，向後遍歷鏈表，直到找到正確的時間戳。

如果線程安全是一個問題，那麼使用線程安全隊列將urls添加到歷史記錄中，並使用單個線程來處理該隊列;這樣你的地圖和鏈表就不需要線程安全，即你不需要擔心鎖等。

對於持久性你可以序列化/反序列化鏈表;當您反序列化鏈表時，通過遍歷哈希映射並將其元素添加到映射中來重構哈希映射。然後清除歷史記錄，將列表清空並映射到內存中，並刪除將數據序列化到的文件。

關於內存消耗和IO（即（反）串行化成本）更有效的解決方案是使用無服務器數據庫，如SQLite;這樣你就不需要將記錄保存在記憶中，並且如果你想從歷史記錄中獲得歷史記錄，上個星期你只需要查詢數據庫而不是遍歷鏈表。但是，SQLite本質上是一個樹形圖（特別是一個B-Tree，它針對存儲在磁盤上的數據進行了優化）。

來源

2014-02-20 02:46:10

好！但是這兩者如何連接？散列表值是歷史列表，那它究竟包含什麼？對象在列表中的位置？ – user775093

@ user775093您可以使用哈希映射來確保URL在歷史列表中不會出現兩次。說一個url在'List [i]'的歷史列表中 - 當你第二次從哈希映射中檢索List [i]時添加url，然後調用'remove'來拼接'List [ i-1]'到List [i + 1]'，從列表中刪除List [i]'（現在是'List [null]'），然後在列表的末尾添加'List [null]'列表使它成爲'List [last]'。如果沒有哈希映射，它會進行線性時間操作，從歷史列表中刪除重複的URL。 –

排序瀏覽歷史數據結構

回答

相關問題