Which datastructure is appropriate for this situation?

Question

I'm trying to decide which datastructure to use to store key-value pairs when only features needed are

• insertion
• lookup

Specifically, I don't need to be able to delete pairs, or iterate through keys/values/pairs.

The keys are integer tuples, the values are pointers (references, whatever). I'm only storing a couple million pairs spread out over (many) objects.

Currently I'm considering using either

• a hash table
• a kd-tree
• a b-tree

I'm leaning toward the hash table (for the O(1) insertion/lookup time), but I wanted to confirm my leanings.

Which structure (of those above or other) would you recommend and why? If you would recommend a hash table, should I create a separate table for each object, or just create a single table and use the object's id as part of the key tuple?

Answer 1

A hashtable will be the best choice here as all the operations that matter to you are O(1) (and as such you shouldn't need to worry about creating multiple hashtables).