我将如何散列一个矩形？ [英] How would I hash a rectangle?

问题描述

我有一个Rectangle类。它有一个长度，宽度和面积（所有整数）。我想对它进行散列，使每个具有相同长度和宽度的矩形散列为相同的值。什么是这样做的？

编辑：我理解它的一个广泛的问题。这就是为什么我要求一个的方式来做到这一点。不是最好的方法。

解决方案

一个简单而有效的方案是计算一对整数的哈希值，如下所示： p>

  hash =长度* CONSTANT +宽度
  

从经验上讲，如果 CONSTANT 是一个素数，你将得到最好的结果（即最少的碰撞数）。很多人 ¹ 建议使用像 31 这样的值，但最好的选择取决于最可能的范围 长度和宽度值。如果他们严格有限，并且足够小，那么你可以做得比 31 。

但是， 31 对于实际用途可能是足够好的 ² 。在这个级别的一些碰撞不太可能造成显着的性能差异，甚至一个完美的散列函数也不会消除散列表级别的冲突...在这里你使用散列值的模数。

---

^{1 - 我不确定这个数字来自哪里，或者是否有实证研究来支持它...在一般情况。我怀疑它来自（ASCII）字符串的散列。但是 31 是素数...而且它是梅森素数（ 2 ^ 7 - 1 ），这意味着它可以如果硬件倍数较慢，可以使用移位和减法来计算。} b
$ b

^{2 - 我排除了需要担心某人的情况故意创建哈希函数冲突，试图破坏某些东西。}

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.

解决方案

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.}

这篇关于我将如何散列一个矩形？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！