data structure

I reckon a chained hash table would be your best bet. Basically you have a hash function that converts a key into an integer that is within a certain range. This integer indexs into an array and in the case of chained hash tables it''s an array of linked lists. You then search through the linked list and get the data you want. If you choose an appropiate array size for the linked list and have a decent hash function it''s basically O(1) look up, insert and delete.

You want to hash the u,v,w coordinates together into one "key" value and use an STL map to store/retrieve/delete objects:

#include <map>

using namespace std;

map<float, Item*> m_uvwmap;

item* get_item(int u, int v, int w)
{
//Hashing code, not perfect

float key = u + v*63656 + w*63656*63656;

return m_uvwmap[key];
}

bool add_item(item*)
{
//Our hashing should be the same as retrieve

float key = u + v*63656 + w*63656*63656;
m_uvwmap[key] = item;

return true;
}

Of course, the hashing algo used up there is not perfect, which means you might get some collisions. Collisions are bad. Look up hashing and think about your data ranges when you create you own hashing code

Ideally each slot or bucket in the hash table should contain around 2 or 3 elements, so a balanced binary tree is hardly nessecary.

Thanks, let me see if i get this right.

About 2 objects in each bucket with 100k objects total needs an array size of 50k or ~200kB.

Now I need to find a hashing functions that distributes clusters of keys evenly over 50k buckets ... no clue about that (yet).

And a binary tree for each bucket would only be usefull if i dont get the hashing function right.

Is the "map" include a standard? Why does it use a float value?


Edit: It probably would be good to change the number of buckets to 2^x, eg 65535?

[edited by - Ketzer on May 13, 2004 3:47:53 AM]

With std::map you can create your own comparator, which allows for the use of more complex objects as the key.

Here is one I wrote recently which works with a two-dimensional Position object (struct actually)

struct Position {
	int x,y;
	bool operator == (const Position &other) const {
		return ((x == other.x) && (y == other.y));
	}
};

// Comparator for objects of type Position

struct LtPosition {
	bool operator()(const Position p1, const Position p2) const {
		if (p1.x == p2.x)
			return (p1.y < p2.y);
		return p1.x < p2.x;
	}
};

Then we declare the std::map as (a typedef in this case)

typedef std::map<Position, Node *, LtPosition> AllNodesType;

So we have a Position struct as the key, a Node * as the value, and use the LtPosition function as a comparator.

It is hopefully easy to see how to adapt this to an arbitarily complex struct as a key.

Not a hash table in sight.

As far as I''m aware std::map uses a balanced tree algorithm (AVL or red-black or something), which means that a lookup is going to be O(log n) forever.

Mark

Thanks, easy enough to expand this to a third value.

And Ill try a hashtable too for comparison.