Color>>#hash

Joachim Durchholz joachim.durchholz at munich.netsurf.de
Sun Feb 28 17:51:31 UTC 1999


Andres Valloud wrote:
> 
> To determine such indexes, Dictionaries get the size of the key Array
> and then take the remainder of dividing the hash of the key by that
> size. Then what happens?
> 
> Colors are just hashed by their red component.
> 
> And that's bad.

One might interleave the bits acccording to an
  rgbrgbrgbrgbrgbrgbrgbrgbrgbrgb sign SmallInteger_mark
scheme; colors that are near in the RGB space will then also be near
numerically.

The same principle applies when one wants to index according to multiple
dimensions, e.g. in a geographical database.

Bit interleaving is an expensive operation. To improve speed without
losing all interleaving one could, for example, interleave less bits in
a blockwise manner:
  rrrrggggbbbbrrrrggggbbbbrrggbb sign SmallInteger_mark

If "nearness" of colors in RBG space doesn't matter (such as in
hashing), we just move the most significant bits of the Blue and Green
parts of the color into the most significant bits of the number, e.g. by
XORing them into the most significant bit of the total SmallInteger
object, like:

  rrrrrrrr rrgggggg ggggbbbb bbbbbbsS
     |         |        |
    XOR -------+        |
     |                  |
    XOR ----------------+
     |
 Hashcode result

This is not perfect (the Green and Blue bits are XORed into the high
byte at a lower significance than one would like), but the hash key
quality should be significantly better than when hashing just by the red
pixels.

Regards,
Joachim
-- 
Please don't send unsolicited ads.





More information about the Squeak-dev mailing list