CODEWITHSUNDEEP
javahashmaphashset
piedpiper
piedpiper

Reputation: 1360

Can I retrieve a key stored in a Hashset in java in some way?

I am trying to perform bi directional A star search, where in I encountered this issue.

Suppose I have an object A in a hashset H. Suppose there is another object B, such that A.equals(B) is true (and their hash values are also the same), though A and B point to different objects. Now, when I check if object B is in hashset H, it returns true, as expected. However, suppose now, I want to access some attribute in object A based on this, I then need to access object A. Note that accessing the same attribute in B will not work since they are equal only under the equals method, but do not point to the same object. How can I achieve this?

One way is to use a Hashmap, such that the value type is the same as the key type, and every time I store some key in the hashmap, I store along with it the same object as its value. But this incurs extra memory overhead of storing the value, when what I really need is a copy of the key itself. Is there any other way to achieve this?

Upvotes: 1

Views: 1781

Answers (3)

Stephen C
Stephen C

Reputation: 718826

One way is to use a Hashmap, such that the value type is the same as the key type, and every time I store some key in the hashmap, I store along with it the same object as its value. But this incurs extra memory overhead of storing the value, when what I really need is a copy of the key itself.

In actual fact, the implementation of HashSet in (at least) the Oracle Java SE Library in Java 7 has a HashMap inside it. So your concern about the extra memory usage of HashMap is unwarranted.

Here is a link to the source code: http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/7u40-b43/java/util/HashSet.java/

Incidentally, the internal map is declared as HashMap<E, Object> rather than HashMap<E, E>. Thought exercise for the reader: why did they do that?

The only other reasonable alternative (using HashSet) would be to iterate over the set elements, testing each one to see if it is equal to the one you are looking for. That is obviously very (time) inefficient.

Upvotes: 2

Steven Pessall
Steven Pessall

Reputation: 993

You could iterate over all values in the HashSet and check the equals method of B. If the iterator returns an object which is equal to B you have found A.

Upvotes: 0

Jon Skeet
Jon Skeet

Reputation: 1500665

I don't believe there's any way of doing this efficiently using HashSet<E>. (You could list all the keys and check them for equality, of course.)

However, although the HashMap approach would be irritating, it wouldn't actually take any more memory. HashSet is implemented using HashMap (at least in the stock JDK 7) so there's a full map entry for each set entry anyway... and no extra memory is taken to store the value, because they'd both just be references to the same object.

Upvotes: 4

Related Questions