Java LinkedHashMap获取第一个或最后一个条目

Question

我使用过,LinkedHashMap因为重要的是键在地图中输入的顺序.

但现在我想首先获得key的值(第一个输入的条目)或最后一个.

如果有喜欢的方法first()和last()或类似的东西？

我是否需要一个迭代器才能获得第一个键入口？这就是我使用的原因LinkedHashMap!

谢谢!

Answer 1

语义LinkedHashMap仍然是Map 的语义,而不是a 的语义LinkedList.它保留了插入顺序,是的,但这是一个实现细节,而不是其界面的一个方面.

获得"第一"条目的最快方法仍然是entrySet().iterator().next().获取"最后"条目是可能的,但需要通过调用迭代整个条目集,.next()直到到达最后一个. while (iterator.hasNext()) { lastElement = iterator.next() }

编辑:但是,如果你愿意超越JavaSE的API,Apache的Commons Collections中都有自己的LinkedMap实现,它具有类似的方法firstKey和lastKey,这你在找什么.界面相当丰富.

Answer 2

你可以尝试做类似的事情(获得最后一个条目):

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

这是O(N):)

Answer 3

我知道我来得太晚了,但是我想提供一些替代方案,而不是一些特别的东西,但有些案例没有提到这里.如果有人不太关心效率,但他想要更简单的东西(也许用一行代码找到最后的入口值),随着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();
    }

可替换的替代方案

来自Google Guava的Iterables.getLast.它对Lists和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

Answer 4

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

Answer 5

获取LinkedHashMap的第一个和最后一个条目的另一种方法是使用Set接口的"toArray"方法.

但我认为迭代条目集中的条目并获得第一个和最后一个条目是一种更好的方法.

数组方法的使用导致警告形式"......需要未经检查的转换以符合..."这是无法修复的[但只能通过使用注释来抑制@SuppressWarnings("unchecked")].

这是一个演示"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

Answer 6

这有点脏，但是您可以覆盖removeEldestEntryLinkedHashMap的方法，它可能适合您作为私有匿名成员执行：

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

但是，当您开始删除条目时，一切都会崩溃；还没有想出一种方法来解决这个问题。

非常烦人的是，您无法以合理的方式访问头部或尾部......