数据结构像Map一样工作，但允许随机更改键的顺序

Question

我读过很多关于数据结构实现Map和List接口的主题。LinkedHashMap或SortedMap就足够了。
但我的情况略有不同，因为我不仅需要保持键的插入顺序或排序映射，还需要执行键顺序的随机更改。
List允许使用add(int index, E element)方法这样做，但Map的没有实现不支持这样的方法。应该提到的是，我需要的数据结构将主要用作映射。例如map是这样的:

1. 键1 ->值1
2. 键2 ->值2
3. 键3 ->值3
4. 键4 ->值4

我可能需要将第I对移动到第j个位置，这取决于用户的操作:

1. 键1 ->值1
2. 键4 ->值4 [j]
3. 键3 ->值3
4. 键2 ->值2 [i]

我有一个想法结合LinkedList和HashMap并同步它们之间的插入和删除。Map可以按任意顺序存储元素，同时List中的元素可以按我想要的顺序存储。但是我觉得它不好。这种结构需要近两倍的内存，并且在Collection Framework中集成得很差，因为名称冲突会阻止List和Map通过单个类实现。所以我的问题是:在Java中实现具有描述功能的数据结构的最佳方法是什么?

Answer 1

如果您既需要键值映射的O(1)查找，又需要不支持SortedMap等不支持不可变性的可自定义排序顺序，则只需创建一个使用Map和List的包装器类，如下所示:

    class MapList {
        Map<K,V> map = new HashMap<K,V>();
        List<K> keysList = new ArrayList<K>();
        public void put(K key, V val) {
            if (!map.contains(key)) {
                keysList.add(key);
            }
            map.put(key, val);
        }
        public void swap(int key1pos, int key2pos) {
            keysList.set(key1pos, keysList.set(key2pos, keysList.get(key1po)));
        }
        // Getter methods, size, etc...
    }

我不认为你可以绕过需要自定义类与一组这样的需求。在集合api中，键通常是不可变的

Answer 2

如果排序很重要，那么创建一个带有排序字段的通用键对象类如何，例如:

public class MyKey<K> implements Comparable {
  private int order;
  private K key;
  /* getters & setters */
  /* compareTo() */
}

compareTo()方法按顺序字段值排序。然后把这个包在键的周围。例如:如果你存储一个Integer -> Integer映射:

Map<MyKey<Integer>,Integer> myMap = /*.. */;

那么任何时候你需要重新排序你的键，只需改变顺序字段值。然后，您可以使用map keySet() + Collections.sort()或TreeSet

获得排序键集。

无论如何这都不是一个有效的解决方案——但也许它符合您的目的