3
[TestFixture]
class HashSetExample
{
    [Test]
    public void eg()
    {
        var comparer = new OddEvenBag();
        var hs = new HashSet<int>(comparer);

        hs.Add(1);

        Assert.IsTrue(hs.Contains(3));
        Assert.IsFalse(hs.Contains(0));

        // THIS LINE HERE
        var containedValue = hs.First(x => comparer.Equals(x, 3)); // i want something faster than this
        Assert.AreEqual(1, containedValue);
    }

    public class OddEvenBag : IEqualityComparer<int>
    {
        public bool Equals(int x, int y)
        {
            return x % 2 == y % 2;
        }

        public int GetHashCode(int obj)
        {
            return obj % 2;
        }
    }
}

As well as checking if hs contains an odd number, I want to know what odd number if contains. Obviously I want a method that scales reasonably and does not simply iterate-and-search over the entire collection.

Another way to rephrase the question is, I want to replace the line below THIS LINE HERE with something efficient (say O(1), instead of O(n)).

Towards what end? I'm trying to intern a laaaaaaaarge number of immutable reference objects similar in size to a Point3D. Seems like using a HashSet<Foo> instead of a Dictionary<Foo,Foo> saves about 10% in memory. No, obviously this isn't a game changer but I figured it would not hurt to try it for a quick win. Apologies if this has offended anybody.

Edit: Link to similar/identical post provided by Balazs Tihanyi in comments, put here for emphasis.

Community
  • 1
  • 1
fostandy
  • 4,282
  • 4
  • 37
  • 41
  • 2
    The concept of "retrieving" a value from a `HashSet` is nonsense, so I'm quite confused. – Kirk Woll Mar 29 '12 at 00:44
  • 1
    He means getting an element that's stored in the hashset. In the test method, the value is 1. – recursive Mar 29 '12 at 00:55
  • Could you use a `Dictionary` instead that maps from remainders to original values? – recursive Mar 29 '12 at 00:56
  • @recursive, to "get" an element stored in the `HashSet` -- *what does that mean*? Get it by index? That is nonsense because `HashSet` has no order. Get it by *key*? That is nonsense because a `HashSet` is not a key/value map. It's nonsense no matter how you slice it. – Kirk Woll Mar 29 '12 at 01:04
  • @KirkWoll: If you speak linq, then you can think of it this way: `hs.Single (x => predicate(x))`. It's not retrieving a value by index or key, but by predicate. – recursive Mar 29 '12 at 01:11
  • Is there a typo in the question? What is `y`? – Miserable Variable Mar 29 '12 at 02:26
  • Thanks Miserable Variable - corrected – fostandy Mar 29 '12 at 09:08
  • 1
    @KirkWoll It would be useful as memory optimization over using a dictionary where key and value are always identical. Unfortunately the interface of `HashSet` does not support this. One application of such a pattern is for getting a canonical instance of a type with custom equality. – CodesInChaos Mar 29 '12 at 09:15
  • 4
    This is a very good question, similar to this: [Why can't I retrieve an item from a HashSet without enumeration?](http://stackoverflow.com/questions/1494812/why-cant-i-retrieve-an-item-from-a-hashset-without-enumeration) – Balazs Tihanyi Mar 29 '12 at 09:32
  • 1
    possible duplicate of [How to access the reference values of a HashSet without enumeration?](http://stackoverflow.com/questions/7290443/how-to-access-the-reference-values-of-a-hashsettvalue-without-enumeration) – nawfal May 26 '14 at 10:38

1 Answers1

1

The simple answer is no, you can't.

If you want to retrieve the object you will need to use a HashSet. There just isn't any suitable method in the API to do what you are asking for otherwise.

One optimization you could make though if you must use a Set for this is to first do a contains check and then only iterate over the Set if the contains returns true. Still you would almost certainly find that the extra overhead for a HashMap is tiny (since essentially it's just another object reference).

Tim B
  • 40,716
  • 16
  • 83
  • 128