What data structure for O(1) random insertion/deletion and O(1) random access?

Question

I don't know what data structure to use for this problem. I want the structure to have:

• Constant time insertion or deletion.
• Constant time retrieval by id.

The actual system is:

I've got a bunch of objects each with a unique id. My program will need to receive requests for an id and return the relevant object.

Whenever it receives a request I want it to: search the structure to see if it's there. If it is, return it. If it isn't, load it from the disk into memory (put it in the structure so that next time it is requested it doesn't have to use the disk) and then return it.

I'm using C.

Here's a similar question but I'm not sure how relevant it is.

Answer 1

A Hash table might be a pretty good solution in your case -- even if it's not in O(1) when there's a colision : it's a quite efficient solution.

Answer 2

The only structure that fits it is... C array. SomeObject arr[MAX_NUM_OBJECTS] handles this in fast and efficient way