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

Question

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?) 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?

Answer 1

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).