title: Are there O(1) random access data structures that don't rely on contiguous storage?
body: <p>The classic O(1) random access data structure is the array. But an array relies on the programming language being used supporting guaranteed continuous memory allocation (since the array relies on being able to take a simple offset of the base to find any element). </p>
  
  <p>This means that the language must have semantics regarding whether or not memory is continuous, rather than leaving this as an implementation detail. Thus it could be desirable to have a data structure that has O(1) random access, yet doesn't rely on continuous storage.</p>
  
  <p>Is there such a thing?</p>