4

Is there a datastructure like a Dictionary that allows adding unique elements based on the .Equals() call defined for a given class rather than hash value.

In my case, I have a PointD class defining a point with decimal X and Y. Due to the nature of decimal types being a little inexact, creating a hash on the point is not possible, as a small error between two points that are essentially the same will cause major difference in hash value.

Basically, I want to be able to count the number of points of each x, y combination. Is there an existing mechanism for this, or do I need to implement this myself?

Improve this question
3
  • You can't override HashCode to provide a more appropriate solution in your case? Commented Jan 23, 2012 at 3:46
  • float types are inexact, decimal not. I think the only way to do this is rounding your numbers to check the equality. Commented Jan 23, 2012 at 3:49
  • 1
    @GustavoFreddo decimals and floats are both inexact. For example, neither type can represent 1/3 exactly. Commented Jan 23, 2012 at 3:56

5 Answers 5

Reset to default
5

Be careful. It sounds like you want to define Equals so that values within a certain tolerance are considered equal. If you do that, Equals will not be transitive, but it needs to be transitive for the dictionary to function.

Example: suppose x is smaller than y by 0.8 times the tolerance. They would be considered equal. Now consider the value z, which is larger than y by 0.8 times the tolerance. Therefore y and z are also equal. But x and z are not equal!

GetHashCode must return the same value for two equal objects. Since equality is not transitive in this system, you can prove that GetHashCode needs to return the same value for all objects, which causes your dictionary to act like a linked list (but with more storage overhead, that gets wasted).

You could solve this by rounding all the points to a certain degree of precision, and calculating both the hash code and equality from the rounded value. That approach may have pitfalls of its own, of course.

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

Hmm, forgot about the whole transitivity deal...hmm I think for my purposes, what you have said will work. I just defined GetHashCode to hash a string of the x and y values to 3 digits and concatenate. And then defined the Equals function with a rather small tolerance. For my application, I don't expect this to cause any issues.
1

yes, you can make your own IEqualityComparer and pass it to the dictionary when you construct it.... it doesn't use Equal, but you can make it do your own hash.

This will work a bit better if you want to preserve Hash on your actual Point class.

Improve this answer

Comments

0

Just override the GetHashCode method on your PointD class to suit your needs, no?

Improve this answer

Comments

0

You can't have a dictionary that does not use hashing. Dictionaries require both a hash function and an equality comparer. The hash code is used to get the bucket in the hash table, the equality comparer to check the value(s) in the bucket. The most important requirement is that values that compare equal must also have the same hash code.

What I would do in your case is standardize the points to only use a certain number of digits. You can do this with the Math.Round method. This way, you preserve all the necessary properties of your has/equality combination.

You can do the rounding either in the constructor or in your overrides of the Equals and GetHashCode methods (which you still need). The advantage of doing it in the constructor is that you do the calculation only once while still enforcing the requirement everywhere. If your class is mutable, then you'll also have to do this in the property setters and anywhere you modify the fields directly.

Improve this answer

Comments

0

If you have a large number of points, your best bet is probably to use something like a Dictionary<Point, List<PointD>>, turning each PointD into a Point. If the X value is such that is values within tolerance could round to different values, store both a rounded-up and rounded-down version in the Dictionary. When looking for a point, if the Y value is such that values within tolerance could round up to different values, look for both in the table.

Note that the Dictionary operations may return one or two instances of List<PointD> (two instances only in the case where Y rounding was ambiguous; it's possible that some or all of the PointD instances in those lists may not be good matches with the actual point of interest, but the number of instances that need to be inspected should be a small fraction of the total number in the Dictionary.

Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.