Databases
StackOverflow2013
Postsdbo
POhash function providing unique uint from an integer coordinate pair
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POhash function providing unique uint from an integer coordinate pair
    primarykey
    data
    text
    <p><strong>The problem in general:</strong> I have a big 2d point space, sparsely populated with dots. Think of it as a big white canvas sprinkled with black dots. I have to iterate over and search through these dots a lot. The Canvas (point space) can be huge, bordering on the limits of int and its size is unknown before setting points in there.</p> <p>That brought me to the idea of hashing:</p> <p><strong>Ideal:</strong> I need a hash function taking a 2D point, returning a unique uint32. So that no collisions can occur. <em>You can assume that the number of dots on the Canvas is easily countable by uint32.</em></p> <p><strong>IMPORTANT:</strong> It is impossible to know the size of the canvas beforehand (it may even change), so things like </p> <p>canvaswidth * y + x</p> <p>are sadly out of the question.</p> <p>I also tried a very naive </p> <p>abs(x) + abs(y) </p> <p>but that produces too many collisions.</p> <p><strong>Compromise:</strong> A hash function that provides keys with a <em>very</em> low probability of collision.</p> <p>Any ideas anybody? Thanks for any help.</p> <p>Best regards, Andreas T.</p> <p>Edit: I had to change something in the question text: I changed the assumption "able to count the number of points of the canvas with uint32" into "able to count the dots on the canvas (or the number of coordinate pairs to store" by uint32. My original question didn't make much sense, because I would have had a sqrt(max(uint32))xsqrt(max(uint32)) sized canvas, which is uniquely representable by a 16 bit shift and OR. </p> <p>I hope this is ok, since all answers still make most sense with the updated assumptions</p> <p>Sorry for that.</p>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USAndreasT
    1. USAndreasT
    plurals
    1. PL
      singulars
      1. LTLinked
    2. PL
      singulars
      1. LTLinked
    3. PL
      singulars
      1. LTLinked
    1. PL
      singulars
      1. LTLinked
    2. PL
      singulars
      1. LTLinked
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    3. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POhash function providing unique uint from an integer coordinate pair
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. POhash function providing unique uint from an integer coordinate pair
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. POhash function providing unique uint from an integer coordinate pair
      1. USVasilis
      1. VTFavorite
    1. COAlso, for reference, see @JonSkeet's answer to similar: http://stackoverflow.com/a/892640/210709
      singulars
      1. POhash function providing unique uint from an integer coordinate pair
      1. USIAbstract
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload