1

I'm trying to understand why time complexity of accessing a value in a dictionary is O(1).

If I understand correctly, a dictionary is essentially an associative array, i.e. an array A of size n where each element consists of a pair (key, value).

If I give the computer a key, isn't it necessary (in general) to run across the array A in order to find the key and have access to its value? In that case, shouldn't time complexity be O(n)?

Moreover, if the time complexity is O(1) for any dictionary, what's the point of implementing sorted dictionaries (C#, for example)?

My first guess would be that sorted dictionaries make the access faster (by using binary search, for example), but everywhere I look people talk about O(1) in general, so obviously I'm missing something.

Renato Dias
  • 23
  • 5
  • 1
    https://en.wikipedia.org/wiki/Hash_map – DallogFheir Jul 30 '23 at 00:38
  • If you look at gcc it implemens C++ map using RBTree so the complexity is O(log n). – Shiv Jul 30 '23 at 00:44
  • @DallogFheir, the article says "If memory is infinite, the entire key can be used directly as an index to locate its value with a single memory access." I don't understand how the entire key can by used as an index. How can this be done exactly? – Renato Dias Jul 30 '23 at 00:53
  • @Shiv, O(log n) makes perfect sense to me. Why do people talk about O(1) in general? I still don't get it. – Renato Dias Jul 30 '23 at 00:57
  • @RenatoDias did you read the whole paragraph? *Hashing is an example of a space-time tradeoff. If memory is infinite, the entire key can be used directly as an index to locate its value with a single memory access. On the other hand, if infinite time is available, values can be stored without regard for their keys, and a binary search or linear search can be used to retrieve the element.* It's hypothetical, because memory is not infinite. – DallogFheir Jul 30 '23 at 00:58
  • @DallogFheir I understood "infinite memory/time" as "big enough memory/time available", not as an impossibility. Anyway, the article doesn't seem to answer how a hash map allows access in O(1) time. I'm sorry if this is too elementary, but it's an honest question I have. – Renato Dias Jul 30 '23 at 01:16
  • @RenatoDias imagine you have an array of length 10 and want to only store numbers from 0 to 9, you don't need duplicates and don't care about ordering. If you put the numbers in the first free space in the array, the lookup time will be O(n), as you know. But if you put the number at the index represented by that number, it becomes O(1) - for example, to know if 5 is in the array, you just check index 5. That's what a hash map essentially does. Now, if you want to store arbitrarily large numbers, you can just take that number modulo the size of the array. – DallogFheir Jul 30 '23 at 01:30
  • And to store any data type, you need to convert them to numbers first, and that's what a hash function does. – DallogFheir Jul 30 '23 at 01:31
  • @RenatoDias The problem is finding a hash function. It does not matter what hash function you choose, there will be collisions as long as memory is finite. Now this collision worsens the complexity. The O(1) talk is about an ideal, theoretical situation which does not work in practical situation. – Shiv Jul 30 '23 at 11:40
  • @RenatoDias If you really want to dig deep you can read a book called Design of Hashing Algorithms by Josef Pieprzyk and Babak Sadeghiyan. – Shiv Jul 30 '23 at 11:44

1 Answers1

1

If I understand correctly, a dictionary is essentially an associative array, i.e. an array A of size n where each element consists of a pair (key, value).

No. The associative array is typically (ie. almost always) implemented by a hash table. Not an array.

Moreover, if the time complexity is O(1) for any dictionary, what's the point of implementing sorted dictionaries (C#, for example)?

To have them sorted when you needed (hash tables are basically randomly sorted), and more importantly, to answer queries like "first element larger than X" efficiently (in O(log N)).

jpalecek
  • 47,058
  • 7
  • 102
  • 144