Java LinkedHashMap получить первую или последнюю запись - PullRequest
Новая
       15

Java LinkedHashMap получить первую или последнюю запись

114 голосов
/ 20 декабря 2009

Я использовал LinkedHashMap, потому что важен порядок, в котором ключи вводятся на карте.

Но теперь я хочу получить значение ключа первым (первая введенная запись) или последним.

Должен ли быть метод, подобный first() и last() или что-то в этом роде?

Нужен ли мне итератор, чтобы просто получить первую запись ключа? Вот почему я использовал LinkedHashMap!

Спасибо!

Ответы [ 12 ]

134 голосов
/ 20 декабря 2009

Семантика LinkedHashMap все еще семантика карты, а не LinkedList. Да, он сохраняет порядок вставки, но это детали реализации, а не аспект его интерфейса.

Самый быстрый способ получить «первую» запись - это entrySet().iterator().next(). Получение «последней» записи возможно, но повлечет за собой итерации по всему набору записей, вызывая .next(), пока вы не достигнете последней. while (iterator.hasNext()) { lastElement = iterator.next() }

edit : Однако, если вы хотите выйти за рамки API JavaSE, Apache Commons Collections имеет свою собственную реализацию LinkedMap, которая имеет такие методы, как firstKey и lastKey, которые делают то, что вы ищете. Интерфейс значительно богаче.

18 голосов
/ 19 апреля 2016

Можете ли вы попробовать сделать что-то вроде (чтобы получить последнюю запись): 

linkedHashMap.entrySet().toArray()[linkedHashMap.size() -1];

это O (N):)

11 голосов
/ 27 ноября 2015

LinkedHashMap текущая реализация (Java 8) отслеживает свой хвост. Если производительность вызывает беспокойство и / или карта имеет большой размер, вы можете получить доступ к этому полю с помощью отражения.

Поскольку реализация может измениться, вероятно, также неплохо иметь запасную стратегию. Вы можете захотеть что-то зарегистрировать, если выдается исключение, чтобы вы знали, что реализация изменилась.

Это может выглядеть так: 

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);
}
10 голосов
/ 16 апреля 2018

Я знаю, что я пришел слишком поздно, но я хотел бы предложить несколько альтернатив, не что-то экстраординарное, но некоторые случаи, которые ни один не упомянут здесь. В случае, если кто-то не очень заботится об эффективности, но хочет чего-то более простого (возможно, найдет значение последней записи с одной строкой кода), все это будет довольно упрощено с появлением Java 8 . Я приведу несколько полезных сценариев.

Ради полноты я сравниваю эти альтернативы с решением массивов, которое уже упоминалось в этом посте другими пользователями. Я суммирую все случаи, и я думаю, что они будут полезны (когда производительность имеет значение или нет), особенно для новых разработчиков, всегда зависит от вопроса каждой проблемы

Возможные альтернативы

Использование метода массива

Я взял это из предыдущего ответа, чтобы сделать следующие сравнения. Это решение принадлежит @ feresr. 

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

Использование метода ArrayList

Аналогично первому решению с немного другой производительностью 

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 FindLasstEntryWithReduceMethod() {
        return linkedmap.entrySet().stream().reduce((first, second) -> second).orElse(null).getValue();
    }

Метод SkipFunction

Этот метод получит последний элемент потока, просто пропустив все элементы перед ним 

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

Итеративная альтернатива

Iterables.getLast от Google Guava. Есть некоторая оптимизация для Списки и SortedSets тоже 

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

Вот полный исходный код 

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

Вот вывод с производительностью каждого метода 

FindLasstEntryWithArrayListMethod : took 0.162 milliseconds
FindLasstEntryWithArrayMethod : took 0.025 milliseconds
FindLasstEntryWithReduceMethod : took 2.776 milliseconds
FindLasstEntryWithSkipFunctionMethod : took 3.396 milliseconds
FindLasstEntryWithGuavaIterable : took 11 milliseconds
6 голосов
/ 21 декабря 2009

Еще один способ получить первую и последнюю запись LinkedHashMap - использовать метод toArray интерфейса Set.

Но я думаю, что итерация записей в наборе записей и получение первой и последней записи - лучший подход.

Использование методов массива приводит к предупреждению в форме "... требуется непроверенное преобразование для соответствия ..." , которое нельзя исправить [но можно подавить только с помощью аннотации @ SuppressWarnings ( "непроверенные")].

Вот небольшой пример, демонстрирующий использование метода "toArray":

</p> <pre><code>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

3 голосов
/ 09 февраля 2016

Это немного грязно, но вы можете переопределить метод LinkedHashMap removeEldestEntry, который может подойти вам как частному анонимному члену: 

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

Таким образом, вы всегда сможете получить первую запись у вашего eldest участника. Он будет обновляться каждый раз, когда вы выполняете put.

Также должно быть легко переопределить put и установить youngest ... 

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

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

Все это ломается, когда вы начинаете удалять записи; Я не нашел способ запутаться в этом.

Очень раздражает, что вы не можете получить разумный доступ к голове или хвосту ...

2 голосов
/ 22 марта 2013

Возможно что-то вроде этого: 

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;
}
1 голос
/ 31 марта 2016

Предложение: 

map.remove(map.keySet().iterator().next());
1 голос
/ 20 сентября 2012

Я бы рекомендовал использовать ConcurrentSkipListMap , который имеет firstKey() и lastKey() методы

0 голосов
/ 18 августа 2018

верно, вы должны вручную перечислить набор ключей до конца связанного списка, затем получить запись по ключу и вернуть эту запись.

Страница:
...