0

我已经阅读了很多关于实现Map和List接口的数据结构的主题。在任何地方 LinkedHashMap 或 SortedMap 就足够了。
但我的情况略有不同，因为我不仅需要保持键的插入顺序或排序映射，还需要执行键顺序的随机更改。
List允许使用方法做到这一点add(int index, E element)，但没有实现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 描述的特性实现数据结构的最佳方法是什么？

4

2 回答 2

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 中是不可变的

于 2013-04-10T22:52:27.970 回答
0

如果 ordering 很重要，如何创建一个带有 order 字段的通用键对象类，例如：

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

该compareTo()方法按订单字段值排序。然后把它放在你的密钥类型周围。例如：如果您要存储 Integer -> Integer 映射：

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

然后，只要您需要重新排序密钥，只需更改 order 字段值即可。然后，您可以使用 map keySet()plusCollections.sort()或TreeSet

这绝不是一个有效的解决方案 - 但也许它符合您的目的

于 2013-04-10T22:52:35.357 回答