java 中的复杂集合

Question

我需要使用以下访问方法定义用户定义对象的集合：

通过对象的主键访问（唯一）
按次键（非唯一）排序的集合的索引访问

每个对象都有一个主键和一个辅助键（不保证唯一）。当一个对象被添加到集合中时，它应该被插入到一个位置，以便对辅助键值进行排序。应使用主键或集合中的位置提取或删除每个对象。

实现此集合的最佳方法是什么？（主键和对象的映射将提供一半的访问权限，而排序列表将提供另一半。如何将它们组合起来满足我的要求？）

Answer 1

(a map of the primary key and object would provide half of the access, and a sorted list would provide the other half. How can these be combined for my requirement?)

public class YourCollection{
   private Map<UserObject> yourMap;
   private List<UserObject> yourList;

   public void add(UserObject obj){
      yourMap.put(obj.primaryKey, obj);
      yourList.add(obj);
      //sort list on secondaryKey
   }

   public UserObject get(String key){
      return yourMap.get(key);
   }

   public UserObject get(int index){
      return yourList.get(index);
   }
}

这只是基本的shell，但想法是有的。您选择哪种类型的列表和哪种类型的地图由您决定。您 could/should 还向此 class 添加泛型。

编辑 - 此外，对于给定的问题没有最佳方法。您必须考虑不同方法的利弊，并根据您的目标权衡它们。例如，你需要这个占用最少的内存吗？您需要它来使用最少的 CPU 周期吗？您需要它成为最容易编写和维护的代码吗？或者你只是想把一些有用的东西放在一起？我实际上并不是要你回答这些问题，但你在考虑这类问题时应该考虑到它们。

Answer 2

您可以轻松地自己编写这样一个集合，其中您有一个（普通的）HashMap 值的主键，然后是 PriorityQueue 对辅助键中的另一个到主键（因为辅助键并不总是唯一的，所以你不能为此使用 Map 类型）。

解决方案：

这是一个完整的工作示例：

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;

public class MyCollection<T, TPrimaryKey, TSecondaryKey extends Comparable<TSecondaryKey>> {
    private HashMap<TPrimaryKey, T> primaryKeyMap;
    private List<PrimarySecondaryKeyPair> primarySecondaryKeyList;

    public MyCollection() {
        primaryKeyMap = new HashMap<TPrimaryKey, T>();
        primarySecondaryKeyList = new ArrayList<PrimarySecondaryKeyPair>();
    }

    public MyCollection(int initialCapacity) {
        primaryKeyMap = new HashMap<TPrimaryKey, T>(initialCapacity);
        primarySecondaryKeyList = new ArrayList<PrimarySecondaryKeyPair>(initialCapacity);
    }

    private class PrimarySecondaryKeyPair implements Comparable<PrimarySecondaryKeyPair> {
        public TPrimaryKey primaryKey;
        public TSecondaryKey secondaryKey;

        public PrimarySecondaryKeyPair(TPrimaryKey primaryKey, TSecondaryKey secondaryKey) {
            this.primaryKey = primaryKey;
            this.secondaryKey = secondaryKey;
        }

        @Override
        public int compareTo(MyCollection<T, TPrimaryKey, TSecondaryKey>.PrimarySecondaryKeyPair o) {
            return secondaryKey.compareTo(o.secondaryKey);
        }
    }

    public void put(T object, TPrimaryKey primaryKey, TSecondaryKey secondaryKey) { // put by primaryKey
        primaryKeyMap.put(primaryKey, object);
        PrimarySecondaryKeyPair keyPair = new PrimarySecondaryKeyPair(primaryKey, secondaryKey);
        int insertionPoint = Collections.binarySearch(primarySecondaryKeyList, keyPair);
        primarySecondaryKeyList.add((insertionPoint > -1) ? insertionPoint : (-insertionPoint) - 1, keyPair);
    }

    public T getByPrimaryKey(TPrimaryKey primaryKey) {
        return primaryKeyMap.get(primaryKey);
    }

    public T getByIndex(int index) {
        return getByPrimaryKey(primarySecondaryKeyList.get(index).primaryKey);
    }

    public void deleteByPrimaryKey(TPrimaryKey primaryKey) {
        primaryKeyMap.remove(primaryKey);
        for (int i = 0; i < primarySecondaryKeyList.size(); i++) {
            if (primarySecondaryKeyList.get(i).primaryKey.equals(primaryKey)) {
                primarySecondaryKeyList.remove(i);
            }
        }
    }

    public void deleteByIndex(int index) {
        primaryKeyMap.remove(primarySecondaryKeyList.remove(index).primaryKey);
    }
}

这个class（我认为）做你想做的，它不会存储任何不必要的东西。

时间复杂度：

O(log n) put() 的时间（以便按辅助键排序）。

来自 [=47 上的 JavaDoc =] 这个使用的方法：

This method runs in log(n) time for a "random access" list (which provides near-constant-time positional access).

^{（primarySecondaryKeyList 是一个 "random access" 列表，因为它使用 ArrayList）。}
主键获取 object 的平均 O(1) 时间（如果您的主键类型有 worst-case 变为 O(n) =81=]真的糟糕的哈希函数）。
^{（见https://en.wikipedia.org/wiki/Hash_table）}
平均 O(1) 获取按次键排序的索引的时间，因为这是基于获取主键（必须这样做，除非您想将每个 object 存储在collection 两次，这将占用 space).
常量 O(1) 按次键排序的索引删除的时间。
O(n) worst-case 用于通过主键删除（从主键映射中删除很容易，但必须迭代 secondary-to-primary 键列表）

但是，请注意，如果您的主键只是一个 Integer 或 Long，最坏的情况 O(n) 将永远不会发生，因为它们的哈希函数只是它们的数值，使它们非常准确（通常会导致 get() 秒的 O(1) 时间）。

用法：

以下示例假设您正在存储 Strings，其中 Longs 作为主键，并使用 Integers 作为辅助键 。然而，class 是通用的，因此您可以存储任何类型的 object 和任何类型的主键（只要确保它具有合适的 hashCode() 函数！）和任何辅助键是 Comparable 自身（所有原始 Number 包装器，如 Integer、Long、Short 等已经是 Comparable 自身） .

以默认初始容量初始化：

MyCollection<String, Long, Integer> myCollection = new MyCollection<String, Long, Integer>();

初始容量50:

MyCollection<String, Long, Integer> myCollection = new MyCollection<String, Long, Integer>(50);

将字符串 "hello" 与主键 937234L 和辅助键 2:

myCollection.put("hello", 937234L, 2);

...其他一切都应该是不言自明的；）

这应该符合要求和您想要的 collection 类型。
希望对您有所帮助。 :)

java 中的复杂集合

complex collection in java

java

collections

解决方案：

时间复杂度：

用法：