CODEWITHSUNDEEP
javaperformancecollectionshashsetasymptotic-complexity
Roam
Roam

Reputation: 4949

a HashSet.contains() returning an Object

Suppose i'm working a type A in Collections. 

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

Only thisField and thatField are relevant to identify the instances of A-- so its equals() and along with it hashCode() methods are overridden accordingly. With this, in a HashSet<A> setOfAs, the objects of A are unique across their (thisField,thatField) value pair.

Somewhere in the application, i need to look up the Set for an instance of A and if it exists, print its otherField-- the meta-info.

i can

i.) get an iterator on setOfAs, see each entry for its thisField and thatField values, and if they both match, print its otherField

ii.) use a self-map, HashMap<A,A> selfMapA, where key and value are the same objects in each entry. instantiate A with (thisField,thatField) value pair to look-up selfMapA and get its matching entry as is if it's there.

(i) is O(n)-- doesn't get the object in constant time although it finds it in constant time.

(ii) gets the object in constant time and is what we keep using in the system. however, it's using twice the memory.

what i'm looking for is a set structure getting the object entry that it finds in constant time. for instance, one with a contains(Object) method returning an Object, the object it found if it exists, rather than boolean as HashSet.contains() does.

are there better alternatives to these? is there a way to get around this?

Upvotes: 3

Views: 118

Answers (2)

Mshnik
Mshnik

Reputation: 7032

As User235... says, HashSet is implemented using a HashMap so the memory use difference between the two is negligible. This has constant time addition and lookup, so time complexity wise you can't do better. So with that in mind, using a hashmap is probably the best answer.

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

Upvotes: 0

user2357112
user2357112

Reputation: 280182

HashSet is implemented using a HashMap with all values set to a dummy object, so option 2 should actually use slightly less memory than a HashSet. I would go with option 2.

Upvotes: 2

Related Questions