LinkedHashMap中特定对象的迭代器

Question

我有一个LinkedHashMap，我的键是一个ID，我想要实现的是能够查找一个ID，如果存在，则从该条目到地图末尾拥有一个迭代器。我到目前为止尝试过的方法：

Map<String, Obj> map = new LinkedHashMap<>();
Iterator it = map.entrySet().iterator();

但是，有没有办法使迭代器从特定对象开始而不进行线性搜索并自己找到它？

- Aadi Droid

Answer 1

没有这样的功能在LinkedHashMap中。但是您可以通过使用List模拟它，只需一次遍历即可实现。

    Map<String, Object> map = new LinkedHashMap<>();
    Map<String, Integer> indexesMap = new HashMap<>(map.size());

    int index = 0;
    for (String key : map.keySet()) {
        indexesMap.put(key, index++);
    }

    List<Entry<String, Object>> entries = new ArrayList<>(map.entrySet());

    // ...

    String key = ...

    Iterator<Entry<String, Object>> iterator = entries.listIterator(indexesMap.get(key));

每次调用entries.listIterator时，您都将获得具有O(1)复杂度的迭代器。

编辑

如果您还想使删除操作的复杂度为O(1)，那么您不应该使用LinkedHashMap。

您可以实现自己的双向链表，并将其节点存储在HashMap中。然后通过从映射中查找键来搜索节点。当您获取节点时，您可以从链接列表中遍历其余的后续条目，或者您可以通过从映射和链接列表中同时删除它来在O(1)中删除它。

- Dragan Bozanovic

---

这是我目前正在使用的解决方案，但当我在列表中间进行删除时，我需要从该位置更新映射！我经常进行编辑和删除。我知道这听起来像是我要求太多了，但确保没有现成的解决方案可用。 - Aadi Droid

@AadiDroid 好的，我之前不知道。请看我的修改后的答案。 - Dragan Bozanovic

Answer 2

不，对于LinkedHashMap来说这是不可能的。在NavigableMap接口中有一个方法tailMap可以帮助你实现这个功能（map.tailMap(key).iterator()），但是这个接口并没有被LinkedHashMap实现。如果TreeMap（可能需要自定义比较器）是你的情况下适当的替代品，请考虑使用它。

- Tagir Valeev

---

我需要保持插入顺序，但我不确定TreeMap是否能实现。我正在了解它。 - Aadi Droid