Java LinkedHashMap erhält ersten oder letzten Eintrag

138

Ich habe verwendet, LinkedHashMapweil es wichtig ist, in welcher Reihenfolge die Schlüssel in die Karte eingegeben werden.

Aber jetzt möchte ich den Wert des Schlüssels zuerst (den zuerst eingegebenen Eintrag) oder den letzten erhalten.

Sollte es eine Methode wie first()und last()oder so geben?

Benötige ich einen Iterator, um nur den ersten Schlüsseleintrag zu erhalten? Deshalb habe ich verwendet LinkedHashMap!

Vielen Dank!

maiky
quelle
3
Die Situation ist in der Tat unglücklich. Hier ist die (Anforderung mit niedriger Priorität) Funktion, die das bietet, was Sie benötigen: bugs.sun.com/view_bug.do?bug_id=6266354
Kevin Bourrillion
stackoverflow.com/a/30984049/1808829 könnte Ihnen helfen
Ayaz Alifov

Antworten:

158

Die Semantik von LinkedHashMapist immer noch die einer Karte und nicht die einer LinkedList. Es behält die Einfügereihenfolge bei, ja, aber das ist eher ein Implementierungsdetail als ein Aspekt seiner Schnittstelle.

Der schnellste Weg, um den "ersten" Eintrag zu erhalten, ist immer noch entrySet().iterator().next(). Das Abrufen des "letzten" Eintrags ist möglich, erfordert jedoch das Durchlaufen des gesamten Eintragssatzes durch Aufrufen, .next()bis Sie den letzten erreichen. while (iterator.hasNext()) { lastElement = iterator.next() }

Bearbeiten : Wenn Sie jedoch bereit sind, über die JavaSE-API hinauszugehen, verfügt Apache Commons Collections über eine eigene LinkedMapImplementierung, die Methoden wie firstKeyund enthält lastKey, die das tun, wonach Sie suchen. Die Schnittstelle ist erheblich umfangreicher.

Skaffman
quelle
Ich muss einen Eintrag (Schlüssel, Wert) als ersten Eintrag in meine verknüpfte Karte einfügen. ODER so etwas wie indexbasiertes Einfügen. ist das mit Apache-Sammlungen möglich?
Kanagavelu Sugumar
2
Die Links "LinkedMap", "firstKey" und "lastKey" sind veraltet.
Josh
Anscheinend können Sie die Commons LinkedMap sogar verwenden, um sie in umgekehrter Reihenfolge zu durchlaufen, indem Sie lastKey abrufen und anschließend den vorherigenKey verwenden, um einen Schritt zurückzutreten ... schön.
Rogerdpack
Anscheinend können Sie die Commons LinkedMap sogar verwenden, um sie in umgekehrter Reihenfolge zu durchlaufen, indem Sie lastKey abrufen und anschließend den vorherigenKey verwenden, um einen Schritt zurückzutreten ... schön. Sie könnten dann sogar Ihr eigenes Iterable schreiben, wenn Sie es in foreach-Schleifen verwenden möchten, z.
B
1
@skaffman, könnten Sie bitte helfen: Was ist mylinkedmap.entrySet().iterator().next()Zeitkomplexität? Ist es O (1)?
Tkrishtop
25

Können Sie versuchen, etwas zu tun wie (um den letzten Eintrag zu erhalten):

linkedHashMap.entrySet().toArray()[linkedHashMap.size() -1];
FRR
quelle
5
Es ist immer noch schneller, das letzte Element zu iterieren und zu behalten. T last = null ; for( T item : linkedHashMap.values() ) last = item; Oder etwas ähnliches. Es ist O (N) in der Zeit, aber O (1) im Speicher.
Florian F
@FlorianF Es kommt also darauf an, wie groß deine Liste ist. Die Array-Lösung wäre schneller und würde den Speicher nicht beeinträchtigen, wenn die Sammlung nicht so groß wäre. Andernfalls dauert es besser, sie zu durchlaufen ... Ich frage mich, ob es als Lösung ein bisschen von beidem gibt, insbesondere seit Java 8.
skinny_jones
1
@skinny_jones: Warum sollte die Array-Lösung schneller sein? Es geht immer noch darum, die gesamte Karte zu iterieren. Jetzt befindet sich die Iteration nur noch in einer JDK-Methode anstatt explizit.
Ruakh
17

Ich weiß, dass ich zu spät gekommen bin, aber ich möchte einige Alternativen anbieten, nicht etwas Außergewöhnliches, sondern einige Fälle, die hier nicht erwähnt wurden. Für den Fall, dass jemand nicht so viel Wert auf Effizienz legt, aber etwas einfacheres möchte (vielleicht den letzten Eingabewert mit einer Codezeile finden), wird dies mit der Einführung von Java 8 erheblich vereinfacht . Ich biete einige nützliche Szenarien.

Der Vollständigkeit halber vergleiche ich diese Alternativen mit der Lösung von Arrays, die bereits in diesem Beitrag von anderen Benutzern erwähnt wurden. Ich fasse alle Fälle zusammen und denke, dass sie nützlich sind (wenn Leistung wichtig ist oder nicht), insbesondere für neue Entwickler, hängt immer von der Frage jedes Problems ab

Mögliche Alternativen

Verwendung der Array-Methode

Ich habe es der vorherigen Antwort entnommen, um die folgenden Vergleiche anzustellen. Diese Lösung gehört @feresr.

  public static String FindLasstEntryWithArrayMethod() {
        return String.valueOf(linkedmap.entrySet().toArray()[linkedmap.size() - 1]);
    }

Verwendung der ArrayList-Methode

Ähnlich wie bei der ersten Lösung mit etwas anderer Leistung

public static String FindLasstEntryWithArrayListMethod() {
        List<Entry<Integer, String>> entryList = new ArrayList<Map.Entry<Integer, String>>(linkedmap.entrySet());
        return entryList.get(entryList.size() - 1).getValue();
    }

Methode reduzieren

Diese Methode reduziert die Menge der Elemente, bis das letzte Element des Streams abgerufen wird. Außerdem werden nur deterministische Ergebnisse zurückgegeben

public static String FindLasstEntryWithReduceMethod() {
        return linkedmap.entrySet().stream().reduce((first, second) -> second).orElse(null).getValue();
    }

SkipFunction-Methode

Diese Methode erhält das letzte Element des Streams, indem einfach alle Elemente davor übersprungen werden

public static String FindLasstEntryWithSkipFunctionMethod() {
        final long count = linkedmap.entrySet().stream().count();
        return linkedmap.entrySet().stream().skip(count - 1).findFirst().get().getValue();
    }

Iterable Alternative

Iterables.getLast von Google Guava. Es gibt auch einige Optimierungen für Listen und SortedSets

public static String FindLasstEntryWithGuavaIterable() {
        return Iterables.getLast(linkedmap.entrySet()).getValue();
    }

Hier ist der vollständige Quellcode

import com.google.common.collect.Iterables;
import java.math.BigDecimal;
import java.math.RoundingMode;
import java.util.ArrayList;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;

public class PerformanceTest {

    private static long startTime;
    private static long endTime;
    private static LinkedHashMap<Integer, String> linkedmap;

    public static void main(String[] args) {
        linkedmap = new LinkedHashMap<Integer, String>();

        linkedmap.put(12, "Chaitanya");
        linkedmap.put(2, "Rahul");
        linkedmap.put(7, "Singh");
        linkedmap.put(49, "Ajeet");
        linkedmap.put(76, "Anuj");

        //call a useless action  so that the caching occurs before the jobs starts.
        linkedmap.entrySet().forEach(x -> {});



        startTime = System.nanoTime();
        FindLasstEntryWithArrayListMethod();
        endTime = System.nanoTime();
        System.out.println("FindLasstEntryWithArrayListMethod : " + "took " + new BigDecimal((endTime - startTime) / 1000000.000).setScale(3, RoundingMode.CEILING) + " milliseconds");


         startTime = System.nanoTime();
        FindLasstEntryWithArrayMethod();
        endTime = System.nanoTime();
        System.out.println("FindLasstEntryWithArrayMethod : " + "took " + new BigDecimal((endTime - startTime) / 1000000.000).setScale(3, RoundingMode.CEILING) + " milliseconds");

        startTime = System.nanoTime();
        FindLasstEntryWithReduceMethod();
        endTime = System.nanoTime();

        System.out.println("FindLasstEntryWithReduceMethod : " + "took " + new BigDecimal((endTime - startTime) / 1000000.000).setScale(3, RoundingMode.CEILING) + " milliseconds");

        startTime = System.nanoTime();
        FindLasstEntryWithSkipFunctionMethod();
        endTime = System.nanoTime();

        System.out.println("FindLasstEntryWithSkipFunctionMethod : " + "took " + new BigDecimal((endTime - startTime) / 1000000.000).setScale(3, RoundingMode.CEILING) + " milliseconds");

        startTime = System.currentTimeMillis();
        FindLasstEntryWithGuavaIterable();
        endTime = System.currentTimeMillis();
        System.out.println("FindLasstEntryWithGuavaIterable : " + "took " + (endTime - startTime) + " milliseconds");


    }

    public static String FindLasstEntryWithReduceMethod() {
        return linkedmap.entrySet().stream().reduce((first, second) -> second).orElse(null).getValue();
    }

    public static String FindLasstEntryWithSkipFunctionMethod() {
        final long count = linkedmap.entrySet().stream().count();
        return linkedmap.entrySet().stream().skip(count - 1).findFirst().get().getValue();
    }

    public static String FindLasstEntryWithGuavaIterable() {
        return Iterables.getLast(linkedmap.entrySet()).getValue();
    }

    public static String FindLasstEntryWithArrayListMethod() {
        List<Entry<Integer, String>> entryList = new ArrayList<Map.Entry<Integer, String>>(linkedmap.entrySet());
        return entryList.get(entryList.size() - 1).getValue();
    }

    public static String FindLasstEntryWithArrayMethod() {
        return String.valueOf(linkedmap.entrySet().toArray()[linkedmap.size() - 1]);
    }
}

Hier ist die Ausgabe mit der Leistung jeder Methode

FindLasstEntryWithArrayListMethod : took 0.162 milliseconds
FindLasstEntryWithArrayMethod : took 0.025 milliseconds
FindLasstEntryWithReduceMethod : took 2.776 milliseconds
FindLasstEntryWithSkipFunctionMethod : took 3.396 milliseconds
FindLasstEntryWithGuavaIterable : took 11 milliseconds
Panagiotis Drakatos
quelle
11

LinkedHashMapDie aktuelle Implementierung (Java 8) verfolgt den Überblick. Wenn die Leistung ein Problem darstellt und / oder die Karte groß ist, können Sie über Reflexion auf dieses Feld zugreifen.

Da sich die Implementierung möglicherweise ändert, ist es wahrscheinlich eine gute Idee, auch eine Fallback-Strategie zu haben. Möglicherweise möchten Sie etwas protokollieren, wenn eine Ausnahme ausgelöst wird, damit Sie wissen, dass sich die Implementierung geändert hat.

Es könnte so aussehen:

public static <K, V> Entry<K, V> getFirst(Map<K, V> map) {
  if (map.isEmpty()) return null;
  return map.entrySet().iterator().next();
}

public static <K, V> Entry<K, V> getLast(Map<K, V> map) {
  try {
    if (map instanceof LinkedHashMap) return getLastViaReflection(map);
  } catch (Exception ignore) { }
  return getLastByIterating(map);
}

private static <K, V> Entry<K, V> getLastByIterating(Map<K, V> map) {
  Entry<K, V> last = null;
  for (Entry<K, V> e : map.entrySet()) last = e;
  return last;
}

private static <K, V> Entry<K, V> getLastViaReflection(Map<K, V> map) throws NoSuchFieldException, IllegalAccessException {
  Field tail = map.getClass().getDeclaredField("tail");
  tail.setAccessible(true);
  return (Entry<K, V>) tail.get(map);
}
Assylien
quelle
1
Ich denke, ich würde ClassCastExceptiondem catchnur für den Fall hinzufügen , dass es tailsich nicht Entryum eine Unterklasse (oder eine zukünftige Implementierung) handelt.
Paul Boddington
@PaulBoddington Ich habe es durch ein Catch All ersetzt - im Allgemeinen nicht empfohlen, aber hier wahrscheinlich angemessen.
Assylias
7
ahh die "schmutzige" Antwort :)
Rogerdpack
6

Eine weitere Möglichkeit, den ersten und letzten Eintrag einer LinkedHashMap zu erhalten, ist die Verwendung der "toArray" -Methode der Set-Schnittstelle.

Ich denke jedoch, dass es besser ist, die Einträge im Eintragssatz zu durchlaufen und den ersten und letzten Eintrag zu erhalten.

Die Verwendung von Array-Methoden führt zu einer Warnung des Formulars "... muss deaktiviert konvertiert werden, um ... zu entsprechen." das nicht behoben werden kann [sondern nur durch Verwendung der Anmerkung @SuppressWarnings ("nicht aktiviert") unterdrückt werden kann].

Hier ist ein kleines Beispiel, um die Verwendung der "toArray" -Methode zu demonstrieren:

public static void main(final String[] args) {
    final Map<Integer,String> orderMap = new LinkedHashMap<Integer,String>();
    orderMap.put(6, "Six");
    orderMap.put(7, "Seven");
    orderMap.put(3, "Three");
    orderMap.put(100, "Hundered");
    orderMap.put(10, "Ten");

    final Set<Entry<Integer, String>> mapValues = orderMap.entrySet();
    final int maplength = mapValues.size();
    final Entry<Integer,String>[] test = new Entry[maplength];
    mapValues.toArray(test);

    System.out.print("First Key:"+test[0].getKey());
    System.out.println(" First Value:"+test[0].getValue());

    System.out.print("Last Key:"+test[maplength-1].getKey());
    System.out.println(" Last Value:"+test[maplength-1].getValue());
}

// the output geneated is :
First Key:6 First Value:Six
Last Key:10 Last Value:Ten

Sateesh
quelle
4
Die toArray-Methode selbst iteriert erneut über die Hashmap :) Daher ist sie aufgrund der wenigen zusätzlichen Zyklen, die beim Erstellen des Arrays verschwendet werden, und des für das Array zugewiesenen Speicherplatzes ineffizienter.
Durin
5

Es ist ein bisschen schmutzig, aber Sie können die removeEldestEntryMethode von LinkedHashMap überschreiben, die Sie möglicherweise als privates anonymes Mitglied verwenden:

private Splat eldest = null;
private LinkedHashMap<Integer, Splat> pastFutures = new LinkedHashMap<Integer, Splat>() {

    @Override
    protected boolean removeEldestEntry(Map.Entry<Integer, Splat> eldest) {

        eldest = eldest.getValue();
        return false;
    }
};

So erhalten Sie immer den ersten Eintrag bei Ihrem eldestMitglied. Es wird jedes Mal aktualisiert, wenn Sie eine put.

Es sollte auch leicht zu überschreiben putund einzustellen sein youngest...

    @Override
    public Splat put(Integer key, Splat value) {

        youngest = value;
        return super.put(key, value);
    }

Alles bricht zusammen, wenn Sie Einträge entfernen. Ich habe keinen Weg gefunden, das zu klären.

Es ist sehr ärgerlich, dass man sonst nicht auf vernünftige Weise Zugang zu Kopf oder Schwanz bekommt ...

Robert
quelle
Guter Versuch, aber der älteste Eintrag wird aktualisiert, wenn map.get aufgerufen wird. Daher wird eldestEntry in diesen Fällen nicht aktualisiert, es sei denn, put wird danach aufgerufen.
Vishr
@vishr ältester Eintrag wird aktualisiert, wenn put aufgerufen wird. (Get and Put für Zugriffsbestellung LinkedHashMap)
Shiji.J
2

Vielleicht so etwas:

LinkedHashMap<Integer, String> myMap;

public String getFirstKey() {
  String out = null;
  for (int key : myMap.keySet()) {
    out = myMap.get(key);
    break;
  }
  return out;
}

public String getLastKey() {
  String out = null;
  for (int key : myMap.keySet()) {
    out = myMap.get(key);
  }
  return out;
}
user2127649
quelle
2

Vorschlag:

map.remove(map.keySet().iterator().next());
Tadeu Jr.
quelle
Es gibt den ersten eingefügten Schlüssel in der Karte. Das Finden des ersten Schlüssels erfolgt in O (1). Das Problem hierbei ist, in O (1) einen Weg zu finden, um den zuletzt eingefügten Schlüssel zu finden.
Emad Aghayi
1

Ich würde empfehlen, ConcurrentSkipListMap zu verwenden, die firstKey()und lastKey()Methoden hat

Doua Beri
quelle
1
Für ConcurrentSkipListMap ist ein Komparator (oder ein natürlicher Komparator) erforderlich. Sie müssen daher zusätzliche Arbeit leisten, um die Reihenfolge zu speichern, in der die Einträge abgelegt werden.
AlikElzin-Kilaka
HashMap und speziell LinkedHashMap bieten Zugriff im Durchschnitt von O (1) - im Gegensatz zu einer SkipList, die Zugriff im Durchschnitt von O (logn) bietet.
AlikElzin-Kilaka
"Die Karte ist nach der natürlichen Reihenfolge ihrer Schlüssel sortiert"
1

Verwenden Sie für das erste Element entrySet().iterator().next()und beenden Sie die Iteration nach 1 Iteration. Zum Schluss ist es am einfachsten, den Schlüssel in einer Variablen beizubehalten, wenn Sie eine map.put ausführen.

Arnab
quelle
0

Obwohl linkedHashMap keine Methode bietet, um das erste, letzte oder bestimmte Objekt abzurufen.

Aber es ist ziemlich trivial zu bekommen:

  • Map orderMap = new LinkedHashMap ();
    Setze al = orderMap.keySet ();

jetzt Iterator für alle Objekte verwenden; Sie können jedes Objekt bekommen.

rai.skumar
quelle
0

Ja, ich bin auf das gleiche Problem gestoßen, aber zum Glück brauche ich nur das erste Element ... - Das habe ich dafür getan.

private String getDefaultPlayerType()
{
    String defaultPlayerType = "";
    for(LinkedHashMap.Entry<String,Integer> entry : getLeagueByName(currentLeague).getStatisticsOrder().entrySet())
    {
        defaultPlayerType = entry.getKey();
        break;
    }
    return defaultPlayerType;
}

Wenn Sie auch das letzte Element benötigen - ich würde untersuchen, wie Sie die Reihenfolge Ihrer Karte umkehren können -, speichern Sie es in einer temporären Variablen, greifen Sie auf das erste Element in der umgekehrten Karte zu (daher wäre es Ihr letztes Element), töten Sie das Temp-Variable.

Hier sind einige gute Antworten zum Umkehren der Reihenfolge einer Hashmap:

So iterieren Sie Hashmap in Java in umgekehrter Reihenfolge

Wenn Sie die Hilfe über den obigen Link verwenden, geben Sie ihnen bitte Up-Votes :) Ich hoffe, dies kann jemandem helfen.

Ryvianstyron
quelle
0

Richtig, Sie müssen den Keyset bis zum Ende der verknüpften Liste manuell auflisten, dann den Eintrag per Schlüssel abrufen und diesen Eintrag zurückgeben.

unbekannter Wille
quelle
0
public static List<Fragment> pullToBackStack() {
    List<Fragment> fragments = new ArrayList<>();
    List<Map.Entry<String, Fragment>> entryList = new ArrayList<>(backMap.entrySet());
    int size = entryList.size();
    if (size > 0) {
        for (int i = size - 1; i >= 0; i--) {// last Fragments
            fragments.add(entryList.get(i).getValue());
            backMap.remove(entryList.get(i).getKey());
        }
        return fragments;
    }
    return null;
}
Владислав Шестернин
quelle