如何在LinkedHashMap中指定位置添加元素？

Question

如何在LinkedHashMap中指定位置添加元素？

javacollectionslinkedhashmap

64

我有一个有序的LinkedHashMap，希望在指定的位置添加元素，例如在地图中的第一个或最后一个位置。如何在LinkedHashMap中添加元素到特定位置？

即使只能将元素添加到LinkedHashMap的第一个或最后一个位置也可以！

- supernova

从文档中可以看到：“请注意，如果将键重新插入映射，则不会影响插入顺序。（如果在调用m.containsKey(k)返回true之前立即调用m.put(k, v)，则将键k重新插入映射m。）” - Andrew

10个回答

27

您无法更改顺序。它是insert-order（默认）或access-order与此构造函数：

public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder)

构造一个带有指定初始容量、负载因子和排序模式的空LinkedHashMap实例。

参数： initialCapacity - 初始容量 loadFactor - 负载因子 accessOrder - 排序模式 - true为访问顺序，false为插入顺序

抛出： IllegalArgumentException - 如果初始容量为负数或负载因子为非正数

请参阅：LinkedHashMap

- Tobias

1

谢谢。它的意思是我只能在最后一个位置添加元素。由于您提到它会维护顺序，所以我认为它会将任何新元素添加到最后一个索引！实际上，我只需要在第一或最后一个位置添加元素。我可以得到最后一个位置，但要在第一个位置添加可能需要将其添加到其他映射中的末尾？ - supernova

1

你可以使用addAll()方法创建一个包含新元素和完整列表的新列表，但这会浪费内存，而且Map并不是为此目的而创建的。 - Tobias

谢谢。这似乎是使用LinkedHashMap的唯一解决方案。 - supernova

1

@supernova，你总是可以自己构建一个，这不是LinkedHashMap的限制，而是Java LinkedHashMap实现的限制。 - Pacerier

17

Apache Commons解决方案：ListOrderedMap

由于JDK的LinkedHashMap只能保证按照插入顺序检索，如果我们想要按照索引插入，我们可以使用Apache Commons的ListOrderedMap作为替代方案。它的实现原理很简单 - 通过维护列表来保持插入顺序并赋予相应的索引，同时也像通常一样插入普通映射。这是文档中所述：

public class ListOrderedMap<K,V>
extends AbstractMapDecorator<K,V>
implements OrderedMap<K,V>, Serializable
使用列表来保持顺序，装饰一个Map以确保添加顺序得以保留。

顺序将通过迭代器和视图中的toArray方法使用。顺序也由MapIterator返回。orderedMapIterator()方法访问一个可以前后遍历映射的迭代器。此外，提供了非接口方法以通过索引访问映射。

如果一个对象第二次被添加到Map中，它将保留在迭代中的原始位置。

请注意，ListOrderedMap不是同步的，也不是线程安全的。如果您希望从多个线程同时使用此Map，必须使用适当的同步。最简单的方法是使用Collections.synchronizedMap(Map)包装此Map。当未同步地访问此类时，可能会抛出异常。

请注意，ListOrderedMap不能与IdentityHashMap、CaseInsensitiveMap或违反Map通用合同的类似映射一起使用。ListOrderedMap（更精确地说是其基础List）依赖于equals()。只要修饰的Map也是基于equals()和hashCode()的，这是可行的，而IdentityHashMap和CaseInsensitiveMap则不是：前者使用==，后者在小写键上使用equals()。

下面是将元素添加到特定位置的实现：
        /**
428     * Puts a key-value mapping into the map at the specified index.
429     * <p>
430     * If the map already contains the key, then the original mapping
431     * is removed and the new mapping added at the specified index.
432     * The remove may change the effect of the index. The index is
433     * always calculated relative to the original state of the map.
434     * <p>
435     * Thus the steps are: (1) remove the existing key-value mapping,
436     * then (2) insert the new key-value mapping at the position it
437     * would have been inserted had the remove not occurred.
438     *
439     * @param index  the index at which the mapping should be inserted
440     * @param key  the key
441     * @param value  the value
442     * @return the value previously mapped to the key
443     * @throws IndexOutOfBoundsException if the index is out of range [0, size]
444     * @since 3.2
445     */
446    public V put(int index, final K key, final V value) {
447        if (index < 0 || index > insertOrder.size()) {
448            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + insertOrder.size());
449        }
450
451        final Map<K, V> m = decorated();
452        if (m.containsKey(key)) {
453            final V result = m.remove(key);
454            final int pos = insertOrder.indexOf(key);
455            insertOrder.remove(pos);
456            if (pos < index) {
457                index--;
458            }
459            insertOrder.add(index, key);
460            m.put(key, value);
461            return result;
462        }
463        insertOrder.add(index, key);
464        m.put(key, value);
465        return null;
466    }

- Manish Kumar Sharma

7

public static <K, V> void add(LinkedHashMap<K, V> map, int index, K key, V value) {
  assert (map != null);
  assert !map.containsKey(key);
  assert (index >= 0) && (index < map.size());

  int i = 0;
  List<Entry<K, V>> rest = new ArrayList<Entry<K, V>>();
  for (Entry<K, V> entry : map.entrySet()) {
    if (i++ >= index) {
      rest.add(entry);
    }
  }
  map.put(key, value);
  for (int j = 0; j < rest.size(); j++) {
    Entry<K, V> entry = rest.get(j);
    map.remove(entry.getKey());
    map.put(entry.getKey(), entry.getValue());
  }
}

- tamalet

6

只需将你的LinkedHashMap分成两个数组。第一个数组的大小为index - 1，并在末尾放入新的Entry。然后用第二个数组中的条目填充第一个数组。

- rock_walker

1

...

LinkedHashMap<String, StringExtension> map = new LinkedHashMap<>();

map.put("4", new StringExtension("4", "a"));
map.put("1", new StringExtension("1", "b"));
map.put("3", new StringExtension("3", "c"));
map.put("2", new StringExtension("2", "d"));

for (Map.Entry<String, StringExtension> entry : map.entrySet()) {
    Log.e("Test", "" + entry.getKey() + " - "+ entry.getValue().value);
}


Collection<StringExtension> temp = new ArrayList<>(map.values());
StringExtension value = map.remove("3");
map.clear();
map.put(value.key, value);

for (StringExtension val : temp) {
    map.put(val.key, val);
}

Log.e("Test", "---");

for (Map.Entry<String, StringExtension> entry : map.entrySet()) {
    Log.e("Test", "" + entry.getKey() + " - "+ entry.getValue().value);
}

...

private class StringExtension
{
    String key;
    String value;

    public StringExtension(String key, String value) {
        this.key = key;
        this.value = value;
    }
}

- Nauman Aejaz

这个问题太简单了，回答那么长有点过了。 - Alexander

同意。我也遇到了同样的问题，没有找到更好的解决办法。 - Nauman Aejaz

1

这是一个Map，它没有索引。它有桶(bucket)。它的工作原理是当您执行put(key, val)时，它会对键进行哈希处理以查找要将val放入哪个桶中。

LinkedHashMap维护一个双向链表，因此可以记录插入（或访问）条目的顺序，具体取决于如何实例化地图。在Map API上没有方法将键值对插入到链表的特定索引处，因为这不是它的目的。

- hvgotcodes

7

由于Map在迭代时没有定义条目的顺序，因此LinkedHashMap是对该合同的一种面向对象的正确实现和完善。所提出的问题是该合同是否扩展到将插入项插入链表的其他位置。因此，声称Map不应允许控制插入位置的论点无效。 - Dilum Ranatunga

1

@dilum，我完全不同意你最后一句话。OP说：“我有一个有序的LinkedHashMap，我想在特定的索引处添加元素。”这没有意义。Map没有索引，它们有键，这些键具有完全不同的语义。此外，我并没有争论“... Map不应该允许控制插入位置”。我只是说它不使用索引。事实上，您可以通过键来控制插入位置。 - hvgotcodes

1

我理解你的意思。当我读取“index”时，我没有将其视为数字，而是视为位置指针（例如其他键，众所周知的头/尾或半消耗的迭代器）。同时，使用基于哈希的组合结构可以实现基于键的O(1)查找和基于索引的O(log n)查找/插入。 - Dilum Ranatunga

@hvgotcodes，地图通常不应该有索引。然而，LinkedHashMap支持按插入顺序排序的索引和键，正如javadoc所描述的。http://docs.oracle.com/javase/1.4.2/docs/api/java/util/LinkedHashMap.html - minmaxavg

1

正如其他答案所建议的那样，通过插入一个值来修改LinkedHashMap并不是推荐的做法。

为什么？
因为LinkedHashMap由HashMap和LinkedList支持。
后者用于保留插入顺序。
很显然，LinkedList在插入到头部和尾部（双向链接）方面非常好。它提供了O(1)的时间复杂度。
然而，将元素插入到特定位置会非常慢，因为你需要遍历整个列表才能找到这个位置，在最坏的情况下需要O(n)的时间复杂度，对于大型数据集来说代价相当高。

我个人不建议这样做，因为它效率低下，但如果你理解了缺点并且确实需要这样做，
你可以使用这个扩展函数，以将键值对插入到特定位置。

fun <K, V> LinkedHashMap<K, V>.insertAtIndex(key: K, value: V, index: Int) {
    if (index < 0) {
        throw IllegalArgumentException("Cannot insert into negative index")
    }
    if (index > size) {
        put(key, value)
        return
    }
    val holderMap = LinkedHashMap<K, V>(size + 1)
    entries.forEachIndexed { i, entry->
        if (i == index) {
            holderMap.put(key, value)
        }
        holderMap.put(entry.key, entry.value)
    }
    clear()
    putAll(holderMap)
}

它将花费O(n)的时间和O(n)的空间。

- Leo DroidCoder

0

假设应用于Map的数据来自List（集合），那么您应该创建一个反向的循环，从该列表的末尾开始读取，直到它到达第一个，如下所示： for (int key = collection.size()-1; key > map.size(); key--) { Data data = collection.get(key); map.put(key, data); }

- Moz

0

可以使用 putFirst() 和 putLast() 方法将元素添加为第一个或最后一个元素，这些方法将在 Java 21 中作为顺序集合增强功能被添加到 LinkedHashMap 中。

LinkedHashMap<String, Integer> linkedHashMap = // ...

linkedHashMap.put("A", 1);
linkedHashMap.putLast("B", 2);
linkedHashMap.putFirst("C", 3);

// linkedHashMap is now [C=3, A=1, B=2]

- M. Justin

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- gyurix · Accepted Answer

您可以将此元素添加到1或最后位置：

添加到最后位置 ► 您只需像这样从地图中删除前一个条目：

map.remove(key);
map.put(key,value);

将值添加到第一位 ► 这有点复杂，你需要克隆地图、清空它、将1. 值放入其中，并将新地图放入其中，就像这样：

我使用的是字符串键和组（我的自定义类）值的地图：

LinkedHashMap<String, Group> newMap=(LinkedHashMap<String, Group>) map.clone();
map.clear();
map.put(key, value);
map.putAll(newMap);

如您所见，使用这些方法您可以将无限数量的元素添加到地图的开头和结尾。