StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POAre there O(1) random access data structures that don't rely on contiguous storage?
primarykey
Id
455781
data
AcceptedAnswerId
0
AnswerCount
11
ClosedDate
CommentCount
2
CommunityOwnedDate
CreationDate
2009-01-18T19:51:58.823
FavoriteCount
5
LastActivityDate
2018-07-10T22:24:39.423
LastEditDate
2009-01-18T20:01:47.290
LastEditorUserId
3055
OwnerUserId
50385
ParentId
0
PostTypeId
1
Score
10
ViewCount
5252
LastEditorDisplayName
chakrit
text
Body
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). 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. Is there such a thing?
Tags
<algorithm><arrays><memory><data-structures><complexity-theory>
Title
Are there O(1) random access data structures that don't rely on contiguous storage?
singulars
PostAcceptedAnswerId
1. This table or related slice is empty.
PostParentId
1. This table or related slice is empty.
PostTypePostTypeId
1. PTQuestion
UserLastEditorUserId
1. USchakrit
UserOwnerUserId
1. USJoseph Garvin
plurals
PostLinksPostIdRelatedPostId
1. This table or related slice is empty.
PostLinksRelatedPostIdPostId
1. This table or related slice is empty.
PostsAcceptedAnswerId
1. This table or related slice is empty.
PostsParentIdCreationDate
1. PO
 singulars
 PostTypePostTypeId
 PTAnswer
2. PO
 singulars
 PostTypePostTypeId
 PTAnswer
3. PO
 singulars
 PostTypePostTypeId
 PTAnswer
VotesPostIdCreationDate
1. VO
 singulars
 PostPostId
 POAre there O(1) random access data structures that don't rely on contiguous storage?
 UserUserId
 This table or related slice is empty.
 VoteTypeVoteTypeId
 VTUpMod
2. VO
 singulars
 PostPostId
 POAre there O(1) random access data structures that don't rely on contiguous storage?
 UserUserId
 This table or related slice is empty.
 VoteTypeVoteTypeId
 VTUpMod
3. VO
 singulars
 PostPostId
 POAre there O(1) random access data structures that don't rely on contiguous storage?
 UserUserId
 USJoseph Garvin
 VoteTypeVoteTypeId
 VTFavorite
CommentsPostId
1. COCool question. Like everyone else, I immediately thought hash table and then, of course, realized that's just an array of buckets. hmmm.
 singulars
 PostPostId
 POAre there O(1) random access data structures that don't rely on contiguous storage?
 UserUserId
 USDave Ray
2. COI thought of it because I'm interested in PL design, and was thinking about how some languages have very precise and obvious space semantics (e.g. C) and how others don't (I was thinking of Haskell and space leaks -- but I don't know if Haskell doesn't specify or if it's just unintuitive/hard)
 singulars
 PostPostId
 POAre there O(1) random access data structures that don't rely on contiguous storage?
 UserUserId
 USJoseph Garvin

Querying!

Guidance

A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.