Hash Table - Multiple Keys for the same Data

[allanmulin]

Hello,

I have been searching on the Internet for a Hash Table (C++) which admits that a Data has multiple Keys, but I have only seen hash tables that admits only one key for a data. (SGI, BOOST, etc)

My problem is the generation of triangular mesh for the solution of partial differential equations. My Data is a Triangle and each triangle has three Keys. Each Key is a vertex of the triangle. So, I need that the follow queries be answered easily and fast:

1) Given a Vertex, return a list of Triangles which share this Vertex.
2) Given three Vertexes, return the Triangle which is formed by those vertexes.

I have implemented a template class HashTable which makes these queries possible, but I'm wondering if the name of such data structure is Hash Table because I have not seen nothing similar.

[pm_kirkham]

It's certainly a map of some time, and if it's implemented using hashing then it's a hash table. I'm not sure whether the advantage of your structure over either having a map/hash table of vertex to list of triangles, and then either intersecting the results of doing three look-ups or scanning the result of one look-up to find matching triangles (if there only a few triangles for each vertex), or having one table for the vertex -> list of triangles mapping and another table of tuple(vertex,vertex,vertex) -> triangle mapping. Implementing custom maps can be efficient, but can also be complicated for the performance (space or speed) gained.

[TheCPUWizard]

A big question is the relative rate of insertion/deletion to lookup. In general performance using a given datstructure is optimized for one or the other (or balanced - providing good, but sub-optimal performance for both).

The second biggest question, is the SIZE of the collection. If the collection is small (relative to the capabilities of the system), then duplication of information can significantly speed up performance. On the other hand, HUGE collections (or extremely limited systems) may mandate slower performance to conserve memory.

Until these are resolved, there is little more that can be said (except the elimination of alternatives which are poor under ALL conditions).