Is a data structure implementation with O(1) search possible without using arrays?

I am currently taking a university course in data structures, and this topic has been bothering me for a while now (this is not a homework assignment, just a purely theoretical question).

Let's assume you want to implement a dictionary. The dictionary should, of course, have a search function, accepting a key and returning a value.

Right now, I can only imagine 2 very general methods of implementing such a thing:

• Using some kind of search tree, which would (always开发者_JS百科?) give an O(log n) worst case running time for finding the value by the key, or,
• Hashing the key, which essentially returns a natural number which corresponds to an index in an array of values, giving an O(1) worst case running time.

Is O(1) worst case running time possible for a search function, without the use of arrays?

Is random access available only through the use of arrays?

Is it possible through the use of a pointer-based data structure (such as linked lists, search trees, etc.)?

Is it possible when making some specific assumptions, for example, the keys being in some order?

In other words, can you think of an implementation (if one is possible) for the search function and the dictionary that will receive any key in the dictionary and return its value in O(1) time, without using arrays for random access?

---

Here's another answer I made on that general subject. Essentially, algorithms reach their results by processing a certain number of bits of information. The length of time they take depends on how quickly they can do that.

A decision point having only 2 branches cannot process more than 1 bit of information. However, a decision point having n branches can process up to log(n) bits (base 2).

The only mechanism I'm aware of, in computers, that can process more than 1 bit of information, in a single operation, is indexing, whether it is indexing an array or executing a jump table (which is indexing an array).

---

It is not the use of an array that makes the lookup O(1), it's the fact that the lookup time is not dependent upon the size of the data storage. Hence any method that accesses data directly, without a search proportional in some way to the data sotrage size, would be O(1).

---

you could have a hash implemented with a trie tree. The complexity is O(max(length(string))), if you have strings of limited size, then you could say it runs in O(1), it doesn't depend on the number of strings you have in the structure. http://en.wikipedia.org/wiki/Trie