"IndexedSet", "MapSet" or "SetMap" implementation in Java

Question

I'm looking for a Set implementation in Java that provides lookup based on elements properties. Thinking in Guava terms it could be constructed using a Function<Element, SearchKey> (expected to be unique across all set elements) and providing a method find(SearchKey key) returning an Element for which the function would return key.

Obvious assumptions that would need to be satisfied:

• Result of function(element) is constant for the whole lifetime of element in the set.
• function gives unique results for all set elements

Reason:
Sometimes there is a need for Set<Element> and the field type cannot be changed into a Map<SearchKey, Element> (like in JPA Entities or in case of 4rd party code). Still, when constructing such an object one could safely use their own Set implementation with Map-like capabilities.

Alternatives:

There are some alternatives I've already found, none of which seems perfect

• not having Map-like capabilities - using linear search for find(SearchKey) implementation (works with every Set implementation:)
• using TreeSet with Comparator comparing SearchKeys - a bit like a hack, especially that this no longer respects element equality
  the "find" method is called ceiling and requires that you construct artificial Element for lookup purposes (uogh...)
• "equivalence set" (http://code.google.com/p/guava-libraries/issues/detail?id=576) - but that is not implemented and does not seem to be going to be

(If you would like to answer that you don't know any more alternatives -- save your time and don't. This is something I already know, I will not be able to accept your answer.)

Answer 1

I'm looking for a Set implementation in Java that provides lookup based on elements properties.

This is what a Map is for and yes, you do need to build a key object to represent what if being looked up.

This is the simplest and more efficient solution in Java, so while it is slightly unpleasant, I wouldn't worry about it.

BTW: Sets are typically implemented as a layer over a Map in the JRE, which isn't ideal IMHO.

Answer 2

I must be missing something, otherwise it's pretty easy via ForwardingSet to HashBiMap.keySet(). My trivial implementation only cares about add and addAll, all the other stuff should work without any effort. There's no single test, I'd recommend to use Guava testlib for this.