java - 哪种数据结构用于快速查找、可变长度和顺序？

Question

我会预先声明这不是家庭作业问题，而是我正在进行的业余爱好项目的一部分。我有一个可行的解决方案，但我觉得我的解决方案很乱而且空间效率低下。

我有一个项目列表。

• 列表的长度是可变的。项目按索引删除。项目被添加到列表的末尾。项目可以重复。
• 当查找一个项目时，只是检查它是否已经在列表中。每个项目都有一个项目唯一的“ key ”。
• 项目根据用户分配的优先级排序。

现在我正在使用两种数据结构来实现我的目标。

我有一个根据优先级排序的 ArrayList(为了保持顺序)，以及一个根据项目键排序的 ArrayList(为了快速查找)。

是否有一个单一的数据结构可以解决这个问题？如果重要的话，我正在用 Java 编码。排序集几乎是我想要的，但因为有重复，我认为这行不通

Answer 1

既然你想按键查找，你应该使用某种 map 。

由于您希望多个对象与同一个键相关联，因此您需要键映射到对象列表，而不是键映射到单个对象。

我会使用 TreeMap 以便对其进行排序，其中键是您的键，值是应该为该键返回的对象列表的 ArrayList。

您必须实现一个比较器才能获得您想要的排序。

使用列表 map 时要考虑的一件事是，当您要添加项目时，您需要检查 map 是否已包含该键的列表。

例如如果您的 map 如下所示:

Map<String, List<Object>> map = new TreeMap<String, ArrayList<Object>>();

添加对象如下所示:

   public void addObject(String key, Object object) {
       List<Object> objects = map.get(key);
       if (objects == null) {
           objects = new ArrayList<Object>();
           map.put(key, objects);
       }
       objects.add(object);
   }