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

Depends on how much data and what the keys are. Hash tables work well for large amounts of data that would be difficult to compare (strings, complex data structures, ect). For smaller data sets with integer keys you can often get better performance with simple red-black trees. This is because good hash functions take time to execute.

In reality neither of those really meet what you're asking. O(1) access is only truly achievable in perfect hashes (and no hash is perfect) and arrays. Meanwhile O(1) insertion is only possible in queues, dequeues, stacks, linked lists, and perfect hashes (which again, no hash is perfect).

To give you a better answer we really need to know what you are trying to accomplish. Any more information on what you are using the data structure for would help

Answer 2

Why not just put them all in a file, mmap the file, and let the OS handle the caching?

Answer 3

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

Answer 4

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.