Should "Set" have a Get method?

Question

Let's have this C# class (it would be almost the same in Java)

public class MyClass {
   public string A {get; set;}
   public string B {get; set;}

   public override bool Equals(object obj) {
        var item = obj as MyClass;

        if (item == null || this.A == null || item.A == null)
        {
            return false;
        }
        return this.A.equals(item.A);
   }

   public override int GetHashCode() {
        return A != null ? A.GetHashCode() : 0;
   }
}

As you can see, equality of two instances of MyClass depends on A only. So there can be two instances that are equal, but holding different piece of information in their B property.

In a standard collection library of many languages (including C# and Java, of course) there is a Set (HashSet in C#), which a collection, which can hold at most one item from each set of equal instances.

One can add items, remove items and check if the set contains an item. But why is it impossible to get a particular item from the set?

HashSet<MyClass> mset = new HashSet<MyClass>();
mset.Add(new MyClass {A = "Hello", B = "Bye"});

//I can do this
if (mset.Contains(new MyClass {A = "Hello", B = "See you"})) {
    //something
}

//But I cannot do this, because Get does not exist!!!
MyClass item = mset.Get(new MyClass {A = "Hello", B = "See you"});
Console.WriteLine(item.B); //should print Bye

The only way to retrieve my item is to iterate over the whole collection and check all items for equality. However, this takes O(n) time instead of O(1)!

I haven't found any language that supports get from a set so far. All "common" languages I know (Java, C#, Python, Scala, Haskell...) seem to be designed in the same way: you can add items, but you cannot retrieve them. Is there any good reason why all these languages do not support something that easy and obviously useful? They cannot be just all wrong, right? Are there any languages that do support it? Maybe retreiving a particular item from a set is wrong, but why?

---

There are a few related SO questions:

https://stackoverflow.com/questions/7283338/getting-an-element-from-a-set

https://stackoverflow.com/questions/7760364/how-to-retrieve-actual-item-from-hashsett

Answer 1

The problem here isn't that HashSet lacks a Get method, it's that your code makes no sense from the perspective of the HashSet type.

That Get method is effectively, "get me this value , please", to which the .NET framework folk would sensibly reply, "eh? You already have that value <confused face />".

If you want to store items and then retrieve them based on matching another slightly different value, then use Dictionary<String, MyClass> as you can then do:

var mset = new Dictionary<String, MyClass>();
mset.Add("Hello", new MyClass {A = "Hello", B = "Bye"});

var item = mset["Hello"];
Console.WriteLine(item.B); // will print Bye

The information of equality leaks from the encapsulated class. If I wanted to change the set of properties involved in Equals, I would have to change the code outside MyClass...

Well yes, but that's because MyClass runs amok with the principle of least astonishment (POLA). With that equality functionality encapsulated, it is completely reasonable to assume that the following code is valid:

HashSet<MyClass> mset = new HashSet<MyClass>();
mset.Add(new MyClass {A = "Hello", B = "Bye"});

if (mset.Contains(new MyClass {A = "Hello", B = "See you"})) 
{
    // this code is unreachable.
}

To prevent this, MyClass needs to be clearly documented as to its odd form of equality. Having done that, it's no longer encapsulated and changing how that equality works would break the open/closed principle. Ergo, it shouldn't change and therefore Dictionary<String, MyClass> is a good solution for this odd requirement.

Answer 2

You already have the item that is "in" the set - you passed it as the key.

"But it isn't the instance that I called Add with" - Yes, but you specifically claimed that they were equal.

A Set is also a special case of a Map|Dictionary, with void as the value type (well the useless methods are not defined, but that doesn't matter).

The data structure you are looking for is a Dictionary<X, MyClass> where X somehow gets the As out of the MyClasses.

The C# Dictionary type is nice in this regard, as it allows you to supply an IEqualityComparer for the keys.

For the example given, I would have the following:

public class MyClass {
   public string A {get; set;}
   public string B {get; set;}
}

public class MyClassEquivalentAs : IEqualityComparer<MyClass>{
   public override bool Equals(MyClass left, MyClass right) {
        if (Object.ReferenceEquals(left, null) && Object.ReferenceEquals(right, null))
        {
            return true;
        }
        else if (Object.ReferenceEquals(left, null) || Object.ReferenceEquals(right, null))
        {
            return false;
        }
        return left.A == right.A;
   }

   public override int GetHashCode(MyClass obj) {
        return obj?.A != null ? obj.A.GetHashCode() : 0;
   }
}

Used thusly:

var mset = new Dictionary<MyClass, MyClass>(new MyClassEquivalentAs());
var bye = new MyClass {A = "Hello", B = "Bye"};
var seeyou = new MyClass {A = "Hello", B = "See you"};
mset.Add(bye);

if (mset.Contains(seeyou)) {
    //something
}

MyClass item = mset[seeyou];
Console.WriteLine(item.B); // prints Bye

Answer 3

Your problem is that you have two contradictory concepts of equality:

• actual equality, where all fields are equal
• set membership equality, where only A is equal

If you would use the actual equality relation in your set, the problem of retrieving a particular item from the set doesn't arise – to check whether an object is in the set, you already have that object. It is therefore never necessary to retrieve a particular instance from a set, assuming you are using the correct equality relation.

We could also argue that a set is an abstract data type that is defined purely by the S contains x or x is-element-of S relation (“characteristic function”). If you want other operations, you're not actually looking for a set.

What happens quite often – but what is not a set – is that we group all objects into distinct equivalence classes. The objects in each such class or subset are only equivalent, not equal. We can represent each equivalence class through any member of that subset, and it then becomes desirable to retrieve that representing element. This would be a mapping from the equivalence class to the representative element.

In C#, a dictionary can use an explicit equality relation, I think. Otherwise, such a relation can be implemented by writing a quick wrapper class. Pseudocode:

// The type you actually want to store
class MyClass { ... }

// A equivalence class of MyClass objects,
// with regards to a particular equivalence relation.
// This relation is implemented in EquivalenceClass.Equals()
class EquivalenceClass {
  public MyClass instance { get; }
  public override bool Equals(object o) { ... } // compare instance.A
  public override int GetHashCode() { ... } // hash instance.A
  public static EquivalenceClass of(MyClass o) { return new EquivalenceClass { instance = o }; }
}

// The set-like object mapping equivalence classes
// to a particular representing element.
class EquivalenceHashSet {
  private Dictionary<EquivalenceClass, MyClass> dict = ...;
  public void Add(MyClass o) { dict.Add(EquivalenceClass.of(o), o)}
  public bool Contains(MyClass o) { return dict.Contains(EquivalenceClass.of(o)); }
  public MyClass Get(MyClass o) { return dict.Get(EquivalenceClass.of(o)); }
}

Answer 4

But why is it impossible to get a particular item from the set?

Because that's not what sets are for.

Let me rephrase the example.

"I have a HashSet that I want store MyClass objects in and I want to be able to get them by using the property A that equals the object's property A".

If replace "HashSet" with "Collection", "objects" with "Values" and "property A" with "Key", the sentence becomes:

"I have a Collection that I want to store MyClass Values in and I want to be able to get them by using the Key that equals the object's Key".

What's being described is a Dictionary. The actual question being asked is "Why can't I treat HashSet as a Dictionary?"

The answer is that they are not used for the same thing. The reason to use a set is to guarantee the uniqueness of it's individual contents, otherwise you could just a use a List or an array. The behavior being described in the question is what a Dictionary is for. All the language designers didn't screw up. They don't provide a get method because if you have the object and it's in the set, they are equivalent, which means you would be "getting" an equivalent object. Arguing that HashSet should be implemented in such a manner that you can "get" non-equivalent objects that you've defined to be equal is a non-starter when the languages provide other data structures that allow you to do that.

A note on the OOP and equality comments/answers. It's okay to have the key of the mapping be a property/member of the stored value in a Dictionary. For example: having a Guid as the key and also the property that is used for the equals method is perfectly reasonable. What's not reasonable is having different values for the rest of the properties. I find that if I'm heading in that direction, I probably need to rethink my class structure.

Answer 5

As soon as you override equals you better override hashcode. As soon as you have done this your "instance" should never change internal state again.

If you do not override equals and hashcode VM object identity is used to determine equality. If you put this object into a Set you are able to find it again.

Changing a value of an object that is used to determine equality will lead to untraceability of this object in hash based structures.

So a Setter on A is dangerous.

Now you do not have B that does not participate in equality. The problem here is semantically not technically. Because technically changing B is neutral to the fact of equality. Semantically B has to be something like a "version" flag.

The point is:

If you have two objects that equal A but not B you have a assumption that one of these objects is newer than the other one. If B has no version information this assumption is hidden in your algorithm WHEN you decide to "overwrite/update" this object in a Set. This source code location where this happens may not be obvious so a developer will have a hard time to identify the relation between object X and object Y that differs from X in B.

If B has version information you expose the assumption that previously was only implicitly derivable from the code. Now you can see, that object Y is a newer version of X.

Think about yourself: Your identity remains your whole life, maybe some properties change (e.g. color of your hair ;-)). Sure you can assume that if you have two photos, one with brown hair one with grey hair, that you may be younger on the photo with brown hair. But maybe you have colored your hair? The problem is: YOU may know that you colored your hair. May others? To put this into a valid context you have to introduce the property age (version). Then you you are semantically explicit and unambigious.

To avoid the hidden operation "replacing old against new object" a Set should not have a get-Method. If you want a behaviour like this, you have to make it explicit by removing the old object and adding the new object.

BTW: What should it mean if you pass in an object that equals the object you want to get? That does not make sense. Keep your semantics clean and don't do this although technically nobody will hinder you.

Answer 6

Specifically in Java, HashSet was initially implemented using a HashMap anyway, and just ignoring the value. So the initial design didn't anticipate any advantage in providing a get method to HashSet. If you want to store and retrieve a canonical value among various objects that are equal, then you just use a HashMap yourself.

I haven't kept up to date with such implementation details, so I can't say whether this reasoning still applies in full in Java, let alone in C# etc. But even if HashSet were reimplemented to use less memory than HashMap, in any case it would be a breaking change to add a new method to the Set interface. So it's quite a lot of pain for a gain not everyone sees as worth having.

Answer 7

There is a major language whose set has the property you want.

In C++, std::set is an ordered set. It has a .find method that looks for the element based on the ordering operator < or binary bool(T,T) function you provide. You can use find to implement the get operation you want.

In fact, if the bool(T,T) function you provide has a specific flag on it (is_transparent), you can pass in objects of a different type for which the function has overloads for. That means you do not have to stick the "dummy" data intomtye second field, just ensure the ordering operation you use can order between the lookup and set-contained types.

This permits an efficient:

std::set< std::string, my_string_compare > strings;
strings.find( 7 );

where my_string_compare understands how to order integers and strings without first converting the integer to a string (at a potential cost).

For unordered_set (the hash set of C++), there is no equivalent transparent flag (yet). You must pass in a T to an unordered_set<T>.find method. It could be added, but hashes require == and a hasher, unlike ordered sets which just require an ordering.

The general pattern is that the container will do the lookup, then give you an "iterator" to that element within the container. At which point you can get the element within the set, or delete it, etc.

In short, not all languages' standard containers have the flaws you describe. The C++ standard library's iterator-based containers do not, and at least some of the containers existed before any of the other languages you described, and the ability to do a get even more efficiently than how you describe has even been added. There is nothing wrong with your design, or wanting that operation; the designers of the Sets you are using simply did not provide that interface.

C++ standard containers where designed to cleanly wrap the low-level operations of the equivalent hand-rolled C code, which was designed to match how you might write it efficiently in assembly. Its iterators are an abstraction of C-style pointers. The languages you mention have all moved away from pointers as a concept, so they did not use the iterator abstraction.

It is possible that the fact that C++ does not have this flaw is an accident of design. The iterator-centric path means that to interact with an item in an associative container you first get an iterator to the element, then you use that iterator to talk about the entry in the container.

The cost is that there are iteration invalidation rules that you have to track, and some operations require 2 steps instead of one (which makes client code noisier). The benefit is that the robust abstraction permits more advanced use than the ones the API designers had in mind originally.