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

Question

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

我有一个物品清单。

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

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

我有一个基于优先级排序的 ArrayList（用于保持顺序），以及一个基于项目键排序的 ArrayList（用于快速查找）。

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

Answer 1

您要查找的内容在 RDBMS 中称为 compound key。如果使用复合键 (priority, key) 创建 ArrayList，您将拥有单一数据结构。

Answer 2

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

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

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

您必须实现比较器才能获得所需的排序。

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

例如如果您的地图如下所示：

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);
   }

Answer 3

我不确定单一数据结构，但您可以将 ArrayList<> 与 HashSet<>

结合使用

创建一个包装器 class 来包装一个 Item 和一个 priority，我假设它是一个 int 值。

class ItemWithPriority
{
    private Item item;
    private int priority;

    ItemWithPriority(Item item, int priority)
    {
      this.item = item;
      this.priority = priority;
    }
}

维护始终根据自定义 Comparator<ItemWithPriority> 排序的 ArrayList<ItemWithPriority>，该自定义 Comparator<ItemWithPriority> 根据 priority.

进行比较

另外维护一个 HashSet<Item> 包含给定时间点所有项目的集合。

插入：

itemWithPriorityList.add(new ItemWithPriority(item, priority));
Collections.sort(itemWithPriorityList, new PriorityBasedComparator());
itemSet.add(item);

删除：（基于索引）

Item itemToBeRemoved = itemWithPriorityList.get(index);
itemWithPriorityList.remove(index);
itemSet.remove(itemToBeRemoved);

查找：

itemSet.contains(item)

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

Which data structure for fast lookup, variable length, and order?

java

algorithm

sorting

lookup