logo标签列表

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

javadictionarylinkedhashmap
184

我使用了LinkedHashMap，因为在该映射表中，键的输入顺序很重要。

但现在，我想得到第一个（最先输入的）或最后一个键的值。

是否需要像first()和last()这样的方法？

我是否需要一个迭代器来获取第一个键入口？这就是我使用LinkedHashMap的原因！

谢谢！

6
情况确实很不幸。这是一个（低优先级的）功能请求，将提供您所需的内容：http://bugs.sun.com/view_bug.do?bug_id=6266354 - Kevin Bourrillion
1
这个链接 https://dev59.com/hG865IYBdhLWcg3wIa7M#30984049 可能会对你有所帮助。 - Ayaz Alifov
我不明白为什么 LinkedHashMap 没有实现 Deque。它完全可以这样做。 - forresthopkinsa
3
为了跟进@KevinBourrillion 13年前的评论，这个功能终于在Java 21中被添加了，通过序列化集合特性（JDK-8280836）。我已经将此作为答案添加了（https://dev59.com/cHI-5IYBdhLWcg3wR2Jr#76461679）。 - M. Justin
17个回答
196
LinkedHashMap的语义仍然是Map，而不是LinkedList。它保留插入顺序，但这是实现细节，而不是其接口的一部分。获得“第一个”条目的最快方法仍然是entrySet().iterator().next()。获取“最后一个”条目是可能的，但需要通过调用.next()迭代整个条目集来实现，直到到达最后一个。 while(iterator.hasNext()) { lastElement = iterator.next() }编辑：但是，如果您愿意超越JavaSE API，Apache Commons Collections有自己的LinkedMap实现，具有像firstKey和lastKey这样的方法，可以满足您的需求。界面更加丰富。
我需要将entry(key, value)作为链式Map的第一项插入；或者是类似基于索引的插入。使用Apache集合库能够实现吗？ - Kanagavelu Sugumar
2
“LinkedMap”，“firstKey”和“lastKey”链接已经失效，请知悉。 - Josh
结果导致无限循环，因为lastentry.next返回第一个条目。 - Jason
2
@skaffman，您能帮忙解答一下吗：mylinkedmap.entrySet().iterator().next() 的时间复杂度是多少？是O(1)吗？ - tkrishtop
1
@tkrishtop 晚回答了，但我认为它应该是O(1)，因为LinkedHashMap有一个指向队列头部的指针。 - Ricola
显示剩余3条评论
30

你可以尝试类似这样的方法（获取最后一个条目）：

linkedHashMap.entrySet().toArray()[linkedHashMap.size() -1];
8
迭代并保留最后一个元素仍然更快。例如： T last = null ; for( T item : linkedHashMap.values() ) last = item; 尽管时间复杂度为O(N)，但空间复杂度为O(1)。 - Florian F
@FlorianF 所以这取决于你的列表有多大。如果集合不是很大，那么数组解决方案会更快，并且不会占用太多内存，否则最好花更长时间来迭代它... 我想知道是否有一些既能用数组又能迭代的解决方案，特别是在Java 8之后。 - skinny_jones
2
@skinny_jones：为什么数组解决方案会更快？它仍然涉及在整个映射中进行迭代，只是现在迭代是在JDK方法内部而不是显式地进行。 - ruakh
28

我知道我来晚了，但我想提供一些替代方案，不是什么特别的东西，而是一些在这里没有提到的情况。如果有人不太在意效率，但希望拥有更简单的东西（也许可以用一行代码找到最后一个条目值），所有这些都将随着 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();
    }

Reduce 方法

该方法会将一组元素缩减至流的最后一个元素。此外，它只会返回确定性结果。

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。它也对列表和排序集进行了一些优化。

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
13

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);
}
1
我认为最好在catch中添加ClassCastException，以防tail不是子类（或未来实现）中的Entry。 - Paul Boddington
@PaulBoddington，我已经用一个全捕获替换了它-一般情况下不建议这样做，但在这种情况下可能比较适合。 - assylias
7
啊哈，“肮脏”的回答 :) - rogerdpack
6

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

但我认为迭代entry set并获取第一个和最后一个条目是更好的方法。

使用数组方法会导致警告形式的"...需要未经检查的转换以符合..."，这无法修复[但可以通过使用注释@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
4
toArray方法本身会再次遍历哈希表 :) 因此，由于需要创建数组并分配空间，会浪费额外的一些周期，因此效率相对较低。 - Durin
5

虽然有点不太规范，但你可以重写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);
    }

然而，当你开始删除条目时，一切都会破碎；我还没有想出一种解决方法。

很让人恼火的是，除此之外，你无法以明智的方式访问头部或尾部...

不错的尝试，但是当调用map.get时，最老的条目会被更新。因此，在这些情况下，除非调用put，否则eldestEntry将不会被更新。 - vishr
@vishr 当调用put方法时，最老的条目将被更新。(对于访问顺序的LinkedHashMap使用get和put) - Shiji.J
4
也许可以这样做：

可能像这样：

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;
}
3
使用 Java8流 很容易地完成此操作：
LinkedHashMap<String, Integer> linkedHashMap = new LinkedHashMap<>();
linkedHashMap.put("A", 1);
linkedHashMap.put("B", 2);
linkedHashMap.put("C", 3);
linkedHashMap.put("D", 4);

//First entry
Map.Entry<String, Integer> firstEntry = linkedHashMap.entrySet().stream().findFirst().get();

//Last entry
Map.Entry<String, Integer> lastEntry = linkedHashMap.entrySet().stream().skip(linkedHashMap.size() - 1).findFirst().get();
3
第一个和最后一个条目可以通过在Java 21中作为序列化集合增强的一部分添加的firstEntry()和lastEntry()方法轻松访问。
LinkedHashMap<Integer, String> linkedHashMap = // ...

Entry<Integer, String> firstEntry = linkedHashMap.firstEntry();
Entry<Integer, String> lastValue = linkedHashMap.lastEntry();

Integer firstKey = firstEntry.getKey();
Integer lastKey = lastEntry.getKey();
String firstValue = firstEntry.getValue();
String lastValue = lastEntry.getValue();
2

建议：

map.remove(map.keySet().iterator().next());
它给出了映射中第一个插入的键。找到第一个键将是O(1)的。这里的问题是找到一种在O(1)时间内找到最后插入的键的方法。 - Emad Aghaei
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接