HashSet.contains() 返回一个对象

Question

假设我在集合中使用类型 A。

class A {
    ThisType thisField; 
    ThatType thatField; 
    String otherField; 
}

只有 thisField 和 thatField 与识别 A 的实例相关——所以它的 equals() 和 hashCode() 方法被覆盖因此。这样，在 HashSet<A> setOfAs 中，A 的对象在其 (thisField,thatField) 值对中是唯一的。

在应用程序的某处，我需要查找 Set 以获取 A 的实例，如果它存在，则打印其 otherField-- 元信息。

我可以

i.) 在 setOfAs 上获取迭代器，查看每个条目的 thisField 和 thatField 值，如果它们都匹配，则打印其 otherField

ii.) 使用自映射，HashMap<A,A> selfMapA，其中键和值是每个条目中的相同对象。使用 (thisField,thatField) 值对实例化 A 以查找 selfMapA 并按原样获取其匹配条目（如果它存在）。

(i) 是 O(n)-- 虽然它在恒定时间内找到了对象，但它没有在恒定时间内获得对象。

(ii) 在恒定时间内获取对象，是我们在系统中一直使用的对象。但是，它使用了两倍的内存。

我正在寻找的是一个集合结构，它获取在恒定时间内找到的对象条目。例如，一个 contains(Object) 方法返回一个 Object，它找到的对象（如果存在），而不是 HashSet.contains() 那样的 boolean。

有更好的替代品吗？有办法解决这个问题吗？

Answer 1

HashSet 是使用 HashMap 实现的，所有值都设置为虚拟对象，因此选项 2 实际上应该使用比 HashSet 稍微少的内存。我会选择选项 2。

Answer 2

正如 User235... 所说，HashSet 是使用 HashMap 实现的，因此两者之间的内存使用差异可以忽略不计。这有恒定的时间加法和查找，所以时间复杂度明智你不能做得更好。因此，考虑到这一点，使用哈希图可能是最好的答案。

public class Database<A>{
    private HashMap<A,A> db = new HashMap<A,A>();

    /** Adds a to this database. If there was already a in this database,
     * overwrites the old a - updates the metaData 
     */
    public void add(A a){
        db.put(a,a);
    }

    /** Removes a from this database, if present */
    public void remove(A a){
        db.remove(a);
    }

    /** Returns the metadata associated with a in this database.
     * As instances of A hash on thisField and thatField, this
     * may be a different string than a.otherField.
     * Returns null if a is not present in this database.
     */
    public String getMetaData(A a){
        A dat = db.get(a);
        return dat != null ? dat.otherField : null;
    }
}

HashSet.contains() 返回一个对象

a HashSet.contains() returning an Object

java

performance

collections

hashset

asymptotic-complexity