Die Implementierung einer gleichzeitigen LinkedHashMap

Ich versuche zu schaffen, eine gleichzeitige LinkedHashMap für eine Multithread-Architektur.

Wenn ich Collections#synchronizedMap(), ich hätte zu verwenden synchronisierte Blöcke für die iteration. Diese Umsetzung würde dazu führen, dass die sequenzielle addition von Elementen.

Wenn ich ConcurrentSkipListMap gibt es eine Möglichkeit zu implementieren, eine Comparator zu speichern sequentiell, gespeichert ist, in der Verknüpften Liste oder queue.

Ich möchte mit java gebaut, die statt des Drittanbieter-Pakete.

EDIT:

In diesem gleichzeitigen LinkedHashMap, wenn die Schlüssel sind die Namen, ich möchte die keys in der Reihenfolge Ihrer Ankunft. d.h. neuer Wert angehängt werden, entweder beim start oder Ende, aber der Reihe nach.

Während der Iteration, die LinkedHashMap Hinzugefügt werden könnten, mit neue Einträge oder entfernt werden. aber der iteration werden sollte, in welcher Reihenfolge die Einträge Hinzugefügt wurden.

Verstehe ich, dass durch die Verwendung Collections#synchronizedMap() eine synchronized-block für die iteration ausgeführt werden müßte, aber würde die Karte geändert werden (Einträge Hinzugefügt/entfernt), während es gerade Durchlaufen.

Was getter/setter sind redest du? Was versuchen Sie zu "speichern sequentiell"? Geben Sie bitte mehr details - es ist schwer zu verstehen, was Sie wirklich versuchen zu tun im moment.
Was sind Sie versuchen zu speichern, die nacheinander? Wenn Sie Ihre Tasten haben eine definierbare Ordnung, dann sollten Sie in der Lage zu schreiben, einen Komparator. Vielleicht sollten Sie noch mehr Informationen über den Schlüssel in Ihren anzeigen und wie Sie Sie bestellt haben.

InformationsquelleAutor Nilesh | 2010-04-23

  1. 2

    Wenn Sie synchronizedMap, Sie müssen nicht zum synchronisieren von extern, außer für die iteration. Wenn Sie brauchen, um beizubehalten, die Reihenfolge der anzeigen, die Sie verwenden sollten eine SortedMap. Könnten Sie ConcurrentSkipListMap, die thread-sicher ist, oder eine andere SortedMap in Kombination mit synchronizedSortedMap.

    InformationsquelleAutor Matthew Flaschen

  2. 2

    Einen LinkedHashMap hat eine doppelt verkettete Liste ausgeführt durch eine hashtable. Ein FIFO nur mutiert Sie die links auf ein schreiben (einfügen oder entfernen). Dies macht die Implementierung einer version Recht einfach.

    1. Schreiben Sie eine LHM mit nur einsetzen, um erlaubt.
    2. Wechseln Sie zu einer ConcurrentHashMap wie die hashtable.
    3. Schützen #put() /#putIfAbsent() /#remove() mit einem Schloss.
    4. Stellen Sie die "weiter" - Feld volatil.

    Auf iteration, keine Sperre notwendig ist, da können Sie sicher Folgen Sie dem "weiter" - Feld. Liest kann lock-frei einfach durch delegieren an das CHM auf eine #get().

    Nichts für ungut, aber ich hasse es, wenn Leute so reden. Ich weiß, was eine doppelt verkettete Liste. Ich weiß, was ist ein hashtable. Aber was bedeutet eine doppelt verkettete Liste ausgeführt durch eine Hashtabelle soll das bedeuten?
    Ja, es ist schwer zu erklären und zu visualisieren. Finden Sie diese Präsentation, wo ich gab ihm einen Versuch. Die Idee ist, dass eine verknüpfte Liste verwaltet die Bestellung und erfordert eine O(n) suchen. Eine hashtable ist ungeordnet und findet einen Eintrag in O(1) Zeit. Die Kombination ist, dass die hash-table-Eintrag enthält eine Liste von Zeigern, so ein Eintrag ist bestellt auf der Liste. Einträge in der Liste kann angefügt werden (FIFO-Reihenfolge), bewegt den Kopf/Schwanz (LRU-Reihenfolge), und entfernt in O(1) Zeit (Räumung). Dies stellt einen Einfüge-oder access-Karte bestellt Billig.
    ist es nicht wahr, dass, wenn ich Sortiere meine HashMap es würde effektiv zu einem "bestellten" hashmap, die im Grunde Niederlagen den Zweck eines LinkedHashMap ?
    Jeder Vergleich basiert Sortieren ist O(lg n) und verlangt etwas zu vergleichen mit (z.B. timestamp). Dies ist kein Vergleich und ist schneller für die Pflege einsetzen oder access-Reihenfolge.

    InformationsquelleAutor Ben Manes

  3. 1

    Verwenden Sammlungen#synchronizedMap().

    Gemäß meinem glauben, wenn ich Sammlungen.synchronizedMap(), ich hätte zu verwenden synchronisierte Blöcke für getter/setter.

    Dies ist nicht wahr. Sie brauchen nur zu synchronisieren, wird die iteration auf alle Ansichten (keyset, values, entryset). Siehe auch die abovelinked API-Dokumentation.

    wenn die Karte, wird Sie Durchlaufen, dann würde es möglich sein, für den anderen thread zum hinzufügen oder entfernen von Elementen aus der Karte?
    Würde diese Umsetzung führt zu sequentiellen addition von Elementen
    1) Nicht, wenn Sie synchronisieren, wird die iteration gemäß der Dokumentation (haben Sie geklickt haben den link überhaupt???). Das ist der ganze Sinn der Synchronisation. 2) ja, der Zusatz ist bereits intern synchronisiert, das ist auch deine Absicht, oder?
    1) Nein - Lesen Sie in der javadoc. 2) ja, dies impliziert die javadoc und garantiert durch die aktuelle Umsetzung.
    es ist möglich, zu synchronisieren, ohne Serialisierung werden alle get und put-Operationen. Zum Beispiel ConcurrentHashMap auf diese Weise funktioniert. Doch die javadoc-impliziert, dass Operationen auf einer Karte von dieser Methode zurückgegeben wird serialisiert werden.

    InformationsquelleAutor BalusC

  4. 1

    Bis jetzt, mein Projekt verwendet LRUMap von Apache-Sammlungen, aber es basiert auf SequencedHashMap. Kollektionen schlägt ListOrderedMap aber keine sind thread-sicher.

    Habe ich eingeschaltet, um MapMaker von Google Guava. Sie können sich CacheBuilder zu.

    InformationsquelleAutor Yves Martin

  5. 0

    Ähm, eine einfache Antwort wäre, die Nutzung eine monoton steigende key-Anbieter, die Ihre Comparator arbeitet. Denke AtomicInteger, und jedes mal, wenn Sie einfügen, erstellen Sie einen neuen Schlüssel an, der für Vergleiche. Wenn Sie pool echt dein key, können Sie eine interne Karte OrderedKey<MyRealKeyType>.

    class OrderedKey<T> implements Comparable<OrderedKey<T>> {
  T realKey;
  int index;
  OrderedKey(AtomicInteger source, T key) {
    index = source.getAndIncrement();
    realKey = key;
  }
  public int compareTo(OrderedKey<T> other) {
    if (Objects.equals(realKey, other.realKey)) {
      return 0;
    }
    return index - other.index;
  }


}

    Dies würde die Beseitigung der Notwendigkeit für eine benutzerdefinierte Komparator, und geben Ihnen eine schöne O(1) Methode zur Berechnung der Größe (es sei denn, Sie erlauben entfernt, in dem Fall zählen die als gut, so kann man einfach subtrahieren "alle erfolgreich entfernt" von "erfolgreicher" ergänzt, wobei erfolgreich bedeutet, dass ein Eintrag tatsächlich erstellt wurde oder entfernt wurde).

    Tun hüten Sie sich vor memory leaks; Sie können hinzufügen, WeakReference, um teure Dinge... wenn auch teure Dinge, die in der Regel ziemlich schlecht als Schlüssel in einer map, manchmal braucht man einfach eine dynamische Liste von Tupeln (und zu faul sind, um ein reales Objekt), und java nicht die syntax, um auszudrücken, dass anmutig. Mit der eigentlichen Karte Semantik, natürlich, Sie wollen ein threadsicher insertion bestellten anzeigen, die OrderedKey ermöglicht für Sie.

    InformationsquelleAutor Ajax

Schreibe einen Kommentar