Equivalence-based Sets & Maps

[gissuebot]

Original issue created by SeanPFloyd on 2011-03-21 at 11:17 AM

---

Given the Equivalence interface, which has these methods:

  boolean equivalent(@Nullable T a, @Nullable T b);

  int hash(@Nullable T t);

I am surprised that there aren't any Sets / Maps based on Equivalences.

It should be pretty simple to implement an Equivalence-based HashMap / LinkedHashMap / HashSet / LinkedHashSet, just replace all calls to

a) a.hashCode() with equivalence.hash(a)
b) a.equals(b) with equivalence.equivalent(a, b)

And I'd expect to see factory methods like this:

• Map<A,B> Maps.newEquivalenceHashMap(Equivalence<? super A>)
• Map<A,B> Maps.newEquivalenceLinkedHashMap(Equivalence<? super A>)
• Set<A> Sets.newEquivalenceHashSet(Equivalence<? super A>)
• Set<A> Sets.newEquivalenceLinkedHashSet(Equivalence<? super A>)

Or perhaps:

• Map<A,B> Equivalences.newHashMap(Equivalence<? super A>)
• Map<A,B> Equivalences.newLinkedHashMap(Equivalence<? super A>)
• Set<A> Equivalences.newHashSet(Equivalence<? super A>)
• Set<A> Equivalences.newLinkedHashSet(Equivalence<? super A>)

Obviously, the performance of these Classes would depend on the quality of the Equivalence implementation (Hash distribution etc), but without these Classes / Methods I don't really see the point in the Equivalence interface.

[gissuebot]

Original comment posted by kevinb9n on 2011-03-21 at 06:49 PM

---

The stuff that makes Equivalence more useful is still in the future, but it got released a little early just because we use it internally to MapMaker. So, sure, there isn't a whole lot of point in it right now (although if you're going to implement an equivalence for whatever reason, you still might as well use this interface rather than your own one-off, so the value is not exactly zero).

---

Status: Accepted

[gissuebot]

Original comment posted by kevinb9n on 2011-03-21 at 06:51 PM

---

(Issue 521 is an example of something that will make the Equivalence type more interesting.)

[gissuebot]

Original comment posted by ullenboom on 2011-03-23 at 09:54 PM

---

I use a wrapper to make Equivalence more useful for me:

import com.google.common.base.Equivalence;

public class EquivalenceDelegate<T> {
  private final T delegate;
  private final Equivalence<T> equivalence;

  public EquivalenceDelegate( T delegate, Equivalence<T> equivalence ) {
    this.delegate = delegate;
    this.equivalence = equivalence;
  }

  @SuppressWarnings( "unchecked" )
  @Override public boolean equals( Object that ) {
    return equivalence.equivalent( delegate, ((EquivalenceDelegate<T>) that).delegate );
  }

  @Override public int hashCode() {
    return equivalence.hash( delegate );
  }

  @Override public String toString() {
    return delegate.toString();
  }

  // don't care about finalize(), wait(), ...
}

An example:

public class EquivalenceDelegateDemo {
  public static void main( String[] args ) {
    Equivalence<StringBuilder> equal = new StringBuilderEquivalence();
    EquivalenceDelegate<StringBuilder> sb1 =
      new EquivalenceDelegate<StringBuilder>( new StringBuilder("maus"), equal );
    EquivalenceDelegate<StringBuilder> sb2 =
      new EquivalenceDelegate<StringBuilder>( new StringBuilder("juvy"), equal );
    HashSet<EquivalenceDelegate<StringBuilder>> set = Sets.newHashSet();
    set.add( sb1 );
    set.add( sb2 );
    boolean contains = set.contains( new EquivalenceDelegate<StringBuilder>( new StringBuilder("juvy"), equal ) );
    System.out.println( contains ); // true
  }
}

[gissuebot]

Original comment posted by kevinb9n on 2011-03-23 at 11:15 PM

---

Yup, we have been trying that out too.

EquivalenceWrapper<Foo> wrappedFoo = fooEquivalence.wrap(myFoo);

If it goes well, it should appear in r10.

Incidentally to original poster, I reviewed our internal-to-Google usage of these classes, and only 1/4 of them even use any of these other related utilities we're talking about. The rest are using just what you see.

[gissuebot]

Original comment posted by cgdecker on 2011-03-29 at 01:08 PM

---

Issue #582 has been merged into this issue.

[gissuebot]

Original comment posted by Maaartinus on 2011-04-20 at 10:26 PM

---

May I ask, what's still missing for the maps to use Equivalence (and when it's to be expected)? I see it gets used in CustomConcurrentHashMap, but the MapMaker has no public methods for this yet. I just wanted a ConcurrentIdentityMap (and found some on the Internet, but I'd prefer to stick with Guava).

[gissuebot]

Original comment posted by fry@google.com on 2011-04-21 at 02:17 PM

---

Note that MapMaker with weak/soft keys will use identity for equivalence. Do you have a use case where you need identity but can't use weak/soft keys?

[gissuebot]

Original comment posted by Maaartinus on 2011-04-25 at 10:23 PM

---

I know, but I really need no weak/soft keys here. Some objects are just more equal. :D I mean, in one place I need a (non-inherited) equals and in another I need identity. There's an easy workaround using a sort of EquivalenceWrapper, but it's a workaround (more objects, more typing, more chances to get it wrong). The use case is quite similar to working with strings in both case-sensitive and case-insensitive manner.

[gissuebot]

Original comment posted by ddlatham on 2011-05-15 at 10:35 PM

---

My use case is to use byte arrays, which use identity hashing as keys. Currently, I have to wrap each one in another object or resort to using a TreeSet with a custom comparator, neither of which is preferred in this performance sensitive code.

[gissuebot]

Original comment posted by kevinb9n on 2011-05-16 at 03:16 AM

---

This was exactly the case that made us first think maybe this was a good idea. But we don't seem to mind that we have so many "wrapped" character arrays (as Strings) in our system; why should byte arrays be any different?

You should use a class like ByteString:
http://code.google.com/p/protobuf/source/browse/trunk/java/src/main/java/com/google/protobuf/ByteString.java

[gissuebot]

Original comment posted by Maaartinus on 2011-05-16 at 09:03 PM

---

IMHO your question doesn't hit the point. Agreed, byte and char arrays are hardly different in this respect. And yes, there are many Strings in the system, which may cost some non-negligible performance and memory.

However, the Strings get used literally everywhere and there's no way to use char[] instead (since you really need immutability and because of all the libraries requiring strings). If there was a single place where you needed millions of strings, you could think about using char[] instead (or even byte[] in order to save memory).

[gissuebot]

Original comment posted by raymond.rishty on 2011-05-16 at 11:26 PM

---

My use case is domain objects with multiple complex unique keys. For example, a show can be looked up by channel and show code, or by channel, air date, and start time, or by ID (a technical key). The equals and hashcode are based on channel and show code, but there are cases where it is useful to look up a show by airing.

[gissuebot]

Original comment posted by cgdecker on 2011-05-17 at 12:00 AM

---

@raymond: Wouldn't you just use index maps/multimaps for that? Either using composite key maps like "(channel, show code) -> object" (could use a Table for that one, actually) or using multimap indexes like "channel -> object" and "show code -> object" and finding the intersection of their values for a particular pair?

[gissuebot]

Original comment posted by raymond.rishty on 2011-05-17 at 12:59 AM

---

Colin, not sure what you mean regarding composite key maps like "(channel, show code) -> object". This is one way I've solved the problem in the past--creating a new class that has the fields I want to be keys, and implements equals and hashcode accordingly. Is that what you have in mind?

Another way I've solved it has been the two-step map like you mentioned... and even (I hate to admit it) used strings as my map key, with the fields separated by some delimiter.

You're right that it's not insolvable without Guava. Our multi-billion dollar business has been handled through this Guava-less code. The library doesn't do anything that was previously impossible--it helps us do it faster, more expressively, more robustly, more maintainably... more better.