用于排序浏览历史的数据结构

Question

假设我想实现浏览器历史功能。如果我第一次访问该 url，它会进入历史记录，如果我再次访问同一页面，它会出现在历史记录列表中。假设我只显示前 20 个站点，但我可以选择查看上个月、上周等的历史记录。

最好的方法是什么？我会使用哈希图来插入/检查它是否更早被访问过，但是我如何有效地对最近访问过的进行排序，我不想使用树图或树集。另外，我如何存储周和月的历史记录。浏览器关闭时是否写入磁盘？当我点击清除历史记录时，数据结构是如何被删除的？

Answer 1

这是在 Java-ish 代码中。

您将需要两种数据结构：哈希映射和双向链表。双向链表包含按时间戳排序的 History 对象（其中包含一个 url 字符串和一个时间戳）；哈希映射是 a Map<String, History>，以 urls 作为键。

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
  }
}

要获取例如上周的历史记录，请向后遍历链表，直到找到正确的时间戳。

如果关注线程安全，则使用线程安全队列将 url 添加到历史记录中，并使用单个线程来处理此队列；这样你的地图和链表不需要是线程安全的，即你不需要担心锁等。

对于持久性，您可以序列化/反序列化链表；当您反序列化链表时，通过遍历哈希映射并将其元素添加到映射来重建哈希映射。然后要清除历史记录，您将列表清空并映射到内存中，然后删除将数据序列化到的文件。

在内存消耗和 IO（即（反）序列化成本）方面更有效的解决方案是使用无服务器数据库，如SQLite；这样你就不需要将历史保存在内存中，如果你想从上周获取历史，你只需要查询数据库而不是遍历链表。然而，SQLite 本质上是一个树状图（特别是一个 B 树，它针对存储在磁盘上的数据进行了优化）。