How would I hash a rectangle? [closed]

问题:

I have a Rectangle class. It has a length, breadth and area (all ints). I want to hash it such that every rectangle with the same length and breadth hashes to the same value. What is a way to do this?

EDIT: I understand its a broad question. Thats why I asked for "a" way to do it. Not the best way.

回答1:

A good and simple scheme is to calculate the hash for a pair of integers as follows:

hash = length * CONSTANT + width

Empirically, you will get best results (i.e. the fewest number collisions) if CONSTANT is a prime number. A lot of people¹ recommend a value like 31, but the best choice depends on the most likely range of the length and width value. If they are strictly bounded, and small enough, then you could do better than 31.

However, 31 is probably good enough for practical purposes². A few collisions at this level is unlikely to make a significant performance difference, and even a perfect hashing function does not eliminate collisions at the hash table level ... where you use the modulus of the hash value.

---

^{1 - I'm not sure where this number comes from, or whether there are empirical studies to back it up ... in the general case. I suspect it comes from hashing of (ASCII) strings. But 31 is prime ... and it is a Mersenne prime (2^7 - 1) which means it could be computed using a shift and a subtraction if hardware multiple is slow.}

^{2 - I'm excluding cases where you need to worry about someone deliberately creating hash function collisions in an attempt to "break" something.}

回答2:

You can use the Apache Commons library, which has a HashCodeBuilder class. Assuming you have a Rectangle class with a width and a height, you can add the following method:

@Override
public int hashCode(){
  return new HashCodeBuilder().append(width).append(height).append(children).toHashCode();
}

回答3:

What you want (as clarified in your comment on the question) is not possible. There are N possible hashCodes, one for each int, where N is approximately 4.2 billion. Assuming rectangles must have positive dimensions, there are ((N * N) / 4) possible rectangles. How do you propose to make them fit into N hashCodes? When N is > 4, you have more possible rectangles than hashCodes.