Hashing integer coordinates of different sizes

Question

I'm trying to hash some 3D coordinates to a 16-bit integer. The coordinates have the following constraints:

x [0, 16]
y [0,256]
z [0, 16]

Is it possible to get O(1) access, zero collisions, and still fit it in a 16-bit word?

My thought was to shift the coordinates such that x takes up the first 4 bits, y the next 8 and z the last 4. After some iterations I came up with the following which shifts and masks the bits such that they shouldn't overlap and cause collisions:

unsigned int hash(unsigned char x, unsigned char y, unsigned char z) {
  return (x << 12) & 0xF000 |
         (y << 8)  & 0x0FF0 |
          z        & 0x000F;
}

However this does produce collisions somehow! I'm not sure why and would grateful if anyone could tell me.

In researching hashing I've found that z-order curves/morton encoding would be a good way to go but that assumes the range of the coordinates in each dimension is constant. Could an option be to morton encode x and z into 8 bits and somehow combine that with the y coordinate for a 16-bit word?

Answer 1

It might be because you’ve written

x        & 0x000F

when it should be

z        & 0x000F

The second shift count is also wrong, so try:

unsigned int hash(unsigned char x, unsigned char y, unsigned char z) {
  return (x << 12) & 0xF000 |
         (y << 4)  & 0x0FF0 |
          z        & 0x000F;
}

Answer 2

I tried instead mapping to a 32-bit integer with the following code.

return ((x) << 24)  & 0xFF000000 |
       ((y) << 16)  & 0x00FFFF00 |
       z            & 0x000000FF;

My unit tests passed and it seems to work however I fear that this may eat a lot more memory than a 16-bit hash.

I'll mark this as answered but the original question still stands if anyone can enlighten me.