eli5: How does dictionary work?

Question

Of course I mean data structure. From what I know, dictionary works as an array that uses hash methods to convert keys into indexes (thus O(1) time complexity). But to achieve that, data must be stored in one long chunk of memory. Therefore, if I have dictionary with, let’s say, ten values, I need indexes from range 0-9. How can hash method achieve that?

In: 0

Answer 1

A dictionary is an abstract concept, also called a map—a container that maps keys to values.

It *could* be (and often is) implemented as a hash table / hash map, in which case you could achieve amortized O(1) insertion / lookup times.