Fast algorithm/data structure that allows linear layout?

Question

I'm trying to implement a system where I'll have key-value structure pairs. They will need to be held in some sort of linear manner (that is, they can be indexed), and once given a position can't be moved, so insertions can only append (and there can't really be much sorting.) Just as an example this is what is had in mind:

Data list:
    0: { "somekey", somevalue }
    1: { "someotherkey", someothervalue }
    ...
    n: { "justanotherkey", justanothervalue }

I've designed the system like this so that when a key is searched for, it's index can be cached and then accessed with constant time. Now, since I have no way to predict the order or volume of the data, and I can't sort it, I need ideas on algorithms or data structures that would be better than just a linear seach, but still keep the constraints I'd like.

Anyone got any ideas? I doubt I can speed it up much, but every little bit helps since this will be the core of my system. Thanks in advance!

==EDIT==

The idea of using two seperate structures (like a hash table and a dynamic array) was actually my first intention. Unfortunately, this won't work for me because I can't seperate the key and the value. The key will be used for errors and messages, so even once an index has been cached, the original key will still be needed to be accessed. Basically they have to just be an array structs, such as:

struct Entry {
    /* Key is actually a complex struct itself with string, and params */
    Key key;
    Data* data; 
}

Answer 1

How about a hashtable key -> index in array?

Answer 2

One option would be to use a combination of a hash table and a dynamic array. The idea is as follows - whenever you insert an element into the data structure, you append it to a dynamic array, then insert the key into a hash table associated with the index into the dynamic array at which the key/value pair resides. That way, to look up by index, you can just look in the dynamic array, and to look up by name, you look up the index in the hash table, then query at that index. This takes expected O(1) time for insertion, deletion, and access, which is much faster than a linear search.

Hope this helps!