Java LinkedHashMap pobiera pierwszy lub ostatni wpis

139

Skorzystałem LinkedHashMapbo ważna jest kolejność w jakiej wpisywano klucze na mapie.

Ale teraz chcę uzyskać wartość klucza na pierwszym miejscu (pierwszy wpisany wpis) lub na końcu.

Czy powinna istnieć taka metoda first()i last()czy coś takiego?

Czy muszę mieć iterator, aby uzyskać tylko pierwszy wpis klucza? Dlatego użyłem LinkedHashMap!

Dzięki!

maiky
źródło
3
Sytuacja jest rzeczywiście niefortunna. Oto żądanie funkcji (o niskim priorytecie), które zapewniłoby to, czego potrzebujesz: bugs.sun.com/view_bug.do?bug_id=6266354
Kevin Bourrillion,
stackoverflow.com/a/30984049/1808829 może ci pomóc
Ayaz Alifov

Odpowiedzi:

159

Semantyka LinkedHashMapjest nadal semantyka Map, a nie a LinkedList. Zachowuje kolejność reklam, tak, ale jest to szczegół implementacji, a nie aspekt interfejsu.

Najszybszym sposobem uzyskania „pierwszego” wpisu jest nadal entrySet().iterator().next(). Uzyskanie „ostatniego” wpisu jest możliwe, ale pociągnie za sobą iterację po całym zestawie przez wywołanie, .next()aż dotrzesz do ostatniego. while (iterator.hasNext()) { lastElement = iterator.next() }

edycja : Jeśli jednak chcesz wyjść poza API JavaSE, Apache Commons Collections ma własną LinkedMapimplementację, która ma metody takie jak firstKeyi lastKey, które robią to, czego szukasz. Interfejs jest znacznie bogatszy.

skaffman
źródło
Muszę wstawić wpis (klucz, wartość) jako pierwszy wpis w mojej połączonej mapie; LUB coś w rodzaju wstawiania na podstawie indeksu. czy to możliwe w przypadku kolekcji Apache?
Kanagavelu Sugumar
2
Linki „LinkedMap”, „firstKey” i „lastKey” są nieaktualne, fyi.
Josh,
Wygląda na to, że możesz nawet użyć Commons LinkedMap, aby przejść przez nią w odwrotnej kolejności, uzyskując lastKey, a następnie używając poprzedniego klawisza, aby cofnąć się ... fajnie.
rogerdpack
Wygląda na to, że możesz nawet użyć Commons LinkedMap, aby przejść przez nią w odwrotnej kolejności, uzyskując lastKey, a następnie używając poprzedniego klawisza, aby cofnąć się ... fajnie. Możesz nawet napisać własną iterowalną, jeśli chcesz jej używać w pętlach foreach, np .: stackoverflow.com/a/1098153/32453
rogerdpack
1
@skaffman, czy mógłbyś pomóc: czym jest mylinkedmap.entrySet().iterator().next()złożoność czasowa? Czy to O (1)?
tkrishtop
25

Czy możesz spróbować zrobić coś takiego (aby uzyskać ostatni wpis):

linkedHashMap.entrySet().toArray()[linkedHashMap.size() -1];
FRR
źródło
5
Nadal szybciej można iterować i zachować ostatnią pozycję. T last = null ; for( T item : linkedHashMap.values() ) last = item; Czy jakoś tak. To jest O (N) w czasie, ale O (1) w pamięci.
Florian F
@FlorianF Więc to zależy od tego, jak duża jest Twoja lista. Rozwiązanie macierzowe byłoby szybsze i nie zagroziłoby pamięci, gdyby kolekcja nie była tak duża, w przeciwnym razie iteracja zajmie więcej czasu ... Zastanawiam się, czy istnieje jedno i drugie jako rozwiązanie, zwłaszcza od czasu Java 8.
skinny_jones
1
@skinny_jones: Dlaczego rozwiązanie macierzy miałoby być szybsze? Wciąż wymaga iteracji po całej mapie, po prostu teraz iteracja znajduje się wewnątrz metody JDK, a nie jawna.
ruakh
17

Wiem, że przyszedłem za późno, ale chciałbym zaproponować kilka alternatyw, nie coś niezwykłego, ale kilka przypadków, o których nikt tutaj nie wspomniał. W przypadku, gdy komuś nie zależy tak bardzo na wydajności, ale chce czegoś bardziej prostego (być może znaleźć ostatnią wartość wpisu z jedną linią kodu), wszystko to zostanie dość uproszczone wraz z pojawieniem się Java 8 . Podaję kilka przydatnych scenariuszy.

Ze względu na kompletność zestawiam te alternatywy z rozwiązaniami tablic, o których wspominali już w tym poście inni użytkownicy. Podsumowuję wszystkie przypadki i myślę, że byłyby przydatne (gdy wydajność ma znaczenie lub nie), szczególnie dla nowych programistów, zawsze zależy od istoty każdego problemu

Możliwe alternatywy

Wykorzystanie metody tablicowej

Wziąłem to z poprzedniej odpowiedzi do, aby dokonać następujących porównań. To rozwiązanie należy do @feresr.

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

Wykorzystanie metody ArrayList

Podobne do pierwszego rozwiązania z nieco inną wydajnością

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

Zmniejsz metodę

Ta metoda zredukuje zestaw elementów do momentu pobrania ostatniego elementu strumienia. Ponadto zwróci tylko wyniki deterministyczne

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

Metoda SkipFunction

Ta metoda pozwoli uzyskać ostatni element strumienia, po prostu pomijając wszystkie elementy przed nim

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

Iterowalna alternatywa

Iterables.getLast z Google Guava. Ma również pewną optymalizację dla List i SortedSets

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

Oto pełny kod źródłowy

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]);
    }
}

Oto wynik z wydajnością każdej metody

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
źródło
11

LinkedHashMapobecna implementacja (Java 8) śledzi swój koniec. Jeśli problemem jest wydajność i / lub mapa ma duży rozmiar, możesz uzyskać dostęp do tego pola poprzez odbicie.

Ponieważ implementacja może się zmienić, prawdopodobnie dobrym pomysłem jest również posiadanie strategii awaryjnej. Możesz chcieć zarejestrować coś, jeśli zostanie zgłoszony wyjątek, aby wiedzieć, że implementacja uległa zmianie.

Może to wyglądać następująco:

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);
}
asylias
źródło
1
Myślę, że dodam, ClassCastExceptionże na catchwszelki wypadek tailnie jest Entryw podklasie (lub przyszłej implementacji).
Paul Boddington
@PaulBoddington Zastąpiłem to haczykiem wszystko - ogólnie nie zalecane, ale prawdopodobnie odpowiednie tutaj.
asylias
7
ahh "brudna" odpowiedź :)
rogerdpack
6

Jeszcze jednym sposobem uzyskania pierwszego i ostatniego wpisu w LinkedHashMap jest użycie metody „toArray” interfejsu Set.

Ale myślę, że iterowanie wpisów w zestawie wpisów i uzyskanie pierwszego i ostatniego wpisu jest lepszym podejściem.

Użycie metod tablicowych prowadzi do ostrzeżenia o postaci „... wymaga niesprawdzonej konwersji, aby była zgodna z ...”, której nie można naprawić [ale można ją wyłączyć tylko za pomocą adnotacji @SuppressWarnings („unchecked”)].

Oto mały przykład pokazujący użycie metody „toArray”:

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
źródło
4
sama metoda toArray będzie ponownie iterować po hashmap :) Więc jest raczej nieefektywna ze względu na kilka dodatkowych cykli zmarnowanych na tworzenie tablicy i przestrzeń przydzieloną dla tablicy.
Durin
5

To trochę brudne, ale możesz zastąpić removeEldestEntrymetodę LinkedHashMap, którą możesz zrobić jako prywatny anonimowy członek:

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

Dzięki temu zawsze będziesz mógł uzyskać pierwszy wpis u swojego eldestczłonka. Będzie aktualizowany za każdym razem, gdy wykonasz put.

Powinien być również łatwy do zastąpienia puti ustawienia youngest...

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

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

Jednak wszystko się psuje, gdy zaczniesz usuwać wpisy; nie wymyśliłem sposobu, żeby to rozgryźć.

To bardzo irytujące, że w inny sposób nie można uzyskać rozsądnego dostępu do głowy lub ogona ...

robert
źródło
Dobra próba, ale najstarszy wpis jest aktualizowany po wywołaniu map.get. Dlatego eldestEntry nie zostanie zaktualizowany w takich przypadkach, chyba że zostanie wywołane polecenie put.
vishr
Najstarszy wpis @vishr jest aktualizowany po wywołaniu put. (pobierz i
złóż
2

Może coś takiego:

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
źródło
2

Sugestia:

map.remove(map.keySet().iterator().next());
Tadeu Jr.
źródło
daje pierwszy wstawiony klucz na mapie. Znalezienie pierwszego klucza będzie w O (1). Problem polega na znalezieniu sposobu w O (1) na znalezienie ostatnio włożonego klucza.
Emad Aghayi
1

Polecam użycie ConcurrentSkipListMap, która ma firstKey()i lastKey()metody

Doua Beri
źródło
1
ConcurrentSkipListMap wymaga komparatora (lub komparatora naturalnego), więc musisz wykonać dodatkową pracę, aby zapisać kolejność umieszczania wpisów.
AlikElzin-kilaka
HashMap, a konkretnie LinkedHashMap, zapewnia dostęp o średniej wartości O (1) - w przeciwieństwie do SkipList, która zapewnia dostęp średnio o O (logn).
AlikElzin-kilaka
„Mapa jest sortowana zgodnie z naturalną kolejnością kluczy”
1

Do użycia pierwszego elementu entrySet().iterator().next()i zatrzymaj iterację po 1 iteracji. Ostatnim najłatwiejszym sposobem jest zachowanie klucza w zmiennej za każdym razem, gdy robisz map.put.

Arnab
źródło
0

Chociaż linkedHashMap nie zapewnia żadnej metody uzyskania pierwszego, ostatniego ani żadnego konkretnego obiektu.

Ale to dość trywialne, aby uzyskać:

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

teraz używam iteratora na obiekcie al; możesz dostać dowolny przedmiot.

rai.skumar
źródło
0

Tak, natrafiłem na ten sam problem, ale na szczęście potrzebuję tylko pierwszego elementu ... - Tak właśnie zrobiłem.

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

Jeśli potrzebujesz również ostatniego elementu - przyjrzałbym się, jak odwrócić kolejność twojej mapy - zapisz go w zmiennej tymczasowej, uzyskaj dostęp do pierwszego elementu w odwróconej mapie (dlatego byłby to twój ostatni element), zabij zmienna temp.

Oto kilka dobrych odpowiedzi, jak odwrócić kolejność haszowania:

Jak iterować hashmap w odwrotnej kolejności w Javie

Jeśli korzystasz z pomocy z powyższego linku, przekaż im pozytywne głosy :) Mam nadzieję, że to może komuś pomóc.

ryvianstyron
źródło
0

tak, musisz ręcznie wyliczyć zestaw kluczy do końca listy połączonej, a następnie pobrać wpis według klucza i zwrócić ten wpis.

nieznana wola
źródło
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;
}
Владислав Шестернин
źródło