CODEWITHSUNDEEP
data-structuresfunctional-programming
Nomad010
Nomad010

Reputation: 283

Static functional data structure with O(1) amortised associative lookup

I'm looking for a static data structure with amortised constant time associative lookup. The only operations I want to perform are lookup and construction. Also being functional is a must. I've had a look at finger trees, but I can't seem to wrap my head round them. Are there any good docs on them or, better yet, a simpler static functional data structure?

Upvotes: 1

Views: 192

Answers (2)

Lii
Lii

Reputation: 12112

I assume that by "functional" and "static" you mean an immutable structure, which can not be modified after its construction, by "lookup" you mean a dictionary-like, key-value lookup and by "construction" you mean the initial construction of the datastructure from a given set of elements.

In that case an immutable, hashtable based dictionary would work. The disadvantage with that is that insertions and removals are O(N), but you state that this is acceptable in your case.

Depending on what programming language you are using a datatype that could be used to implement this might or might not be available. In Erlang a tuple could be used. Haskell has an immutable array in Data.Array.IArray.

Upvotes: 1

Marcus Müller
Marcus Müller

Reputation: 36337

You'd have to look at this from an information-theoretical point of view: The more key/value pairs you store, the more keys you'd have to recognize on an associative lookup. Thus, no matter what you do, the more keys you have, the more complex your lookup will be.

Constant time lookup is only possible when your key directly gives you the address (or something equivalent) of the element you want to look up.

Upvotes: 0

Related Questions