정렬 된 인터넷 사용 기록의 데이터 구조

Question

브라우저 기록 기능을 구현한다고 가정합니다. 처음으로 URL을 방문하면 역사에 들어갑니다. 같은 페이지를 다시 방문하면 기록 목록에 나타납니다. 내가 상위 20 개 사이트 만 표시한다고 말할 수는 있지만 지난 달, 지난 주 등의 기록이 표시되도록 선택할 수 있습니다.

무엇이 최선의 방법입니까? 이전에 방문한 경우 삽입/검사 해시 맵을 사용하지만 최근에 방문한 곳을 효율적으로 정렬하는 방법, 트리 맵 또는 트리 집합을 사용하고 싶지 않습니다. 또한, 어떻게 주와 달의 역사를 저장할 수 있습니다. 브라우저가 닫힐 때 디스크에 기록됩니까? 삭제 기록을 클릭하면 데이터 구조가 어떻게 삭제됩니까?

Answer 1

이것은 Java-ish 코드입니다.

해시 맵과 이중 연결 목록의 두 가지 데이터 구조가 필요합니다. 이중 연결 목록에는 타임 스탬프별로 정렬 된 History 객체 (URL 문자열과 타임 스탬프가 포함 된)가 있습니다. 해시 맵은 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 
    } 
} 

지난 주, 올바른 타임 스탬프를 누를 때까지 연결된 목록을 거꾸로 통과합니다.

스레드 안전성이 중요하면 스레드 안전성 큐를 사용하여 기록에 URL을 추가하고 단일 스레드를 사용하여이 큐를 처리하십시오. 이런 식으로지도와 연결된 목록은 스레드로부터 안전 할 필요가 없습니다. 즉, 잠금 등에 대해 걱정할 필요가 없습니다.

지속성을 위해 연결된 목록을 직렬화/역 직렬화 할 수 있습니다. 연결된 목록을 deserialize 할 때 해시 맵을 가로 지르고 맵에 요소를 추가하여 해시 맵을 재구성하십시오. 그런 다음 기록을 지우려면 목록을 지우고 메모리에 매핑하고 데이터를 직렬화 한 파일을 삭제하십시오.

메모리 소비 및 IO (즉, (비) 직렬화 비용)면에서보다 효율적인 솔루션은 SQLite과 같은 서버리스 데이터베이스를 사용하는 것입니다. 이 방법을 사용하면 내역을 메모리에 보관할 필요가 없습니다. 마지막 주에 연결된 목록을 탐색하는 대신 데이터베이스를 쿼리하면됩니다. 그러나 SQLite는 본질적으로 트리 맵 (특히 디스크에 저장된 데이터에 최적화 된 B-Tree)입니다.