0

I need a hash function for 3D vectors with no collisions between close key values.

The key is a 3d vector of integers. I want no collisions within roughly a 64 * 64 * 64 "area" or larger.

Does anyone know of any hashing functions suited for this purpose, or even better, how would you go about designing a hash for this?

If it's necessary to know, I will be implementing it in C++.

brettwhiteman
  • 4,210
  • 2
  • 29
  • 38
  • 2
    Why not create a `Map>>` for your objects? where each int is x,y,z or whatever you're labeling your axis. Or use `double` if you need float values. – Dan Apr 08 '14 at 23:39
  • Nice solution but it leads to some rather complicated code - this is how you insert an element: auto it1 = map.insert(std::make_pair(x, std::unordered_map>())).first; auto it2 = it1->second.insert(std::make_pair(y, std::unordered_map())).first; it2->second.insert(std::make_pair(z, Object())); – brettwhiteman Apr 09 '14 at 00:37
  • I would have done that a bit differently check the answer I added. – Dan Apr 09 '14 at 01:06

1 Answers1

2

Why not create a Map<int,Map<int,Map<int,Object>>> for your objects? Where each int is x,y,z or whatever you're labeling your axis.

Here's an example of how you could use it.

int x,y,z;
map<int,map<int,map<int,string>>> Vectors = map<int,map<int,map<int,string>>>();
/*give x, y and z a real value*/
Vectors[x][y][z] = "value";
/*more code*/
string ValueAtXYZ = Vectors[x][y][z];

Just to explain because its not super obvious.

The Vectors[x] returns a map<int,map<int,string>>.

I then immediately use that maps [] operator with [y].

That then returns (you guessed it) a map<int,string>.

I immediately use that maps [] operator with [z] and can now set the string.

Note: Just be sure to loop through it using iterates and not a for(int x = 0; /*bad code*/;x++) loop because [] adds an element at every location it's used to look up. Here's an example of a loop and Here's and example of an unexpected add.

Edit:

If you want to make sure that you're not overriding an existing value you could do this.

string saveOldValue;
if(Vectors[x][y][z] != ""/*this is the default value of a string*/)
{
    /*There was a string in that vector so store the old Value*/
    saveOldValue = Vectors[x][y][z];        
}

Vectors[x][y][z] = "Value";

If you use [] on a key that isn't in the map the map creates a default object there. For strings this would be the empty string "".

Or

if(     Vectors.find(x)!=Vectors.end() 
     && Vectors[x].find(y)!=Vectors[x].end() 
     && Vectors[x][y].find(z)!=Vectors[x][y].end())
{
   /* Vectors[x][y][z] has something in it*/
}else
{
   /*Theres nothing at Vectors[x][y][z] so go for it*/
   Vectors[x][y][z] ="value";

}

This uses the find(value) function which returns an iterator to the location of the key "value" OR and iterator that points to map::end() if that key is not int the current map.

If you don't have a default value for your thing being stored then use the second check to do your inserts. This greatly increases the useability of this answer and unclutters your code.

The insert function has it's place but in this example it would be very hard to use.

Community
  • 1
  • 1
Dan
  • 2,625
  • 7
  • 39
  • 52