0

I know that dictionaries are a lot faster but I do not understand why.

I found the following description from Microsoft...

Each addition to the dictionary consists of a value and its associated key. Retrieving a value by using its key is very fast, close to O(1), because the Dictionary<TKey,TValue> class is implemented as a hash table.

...but that just raises the question as to why hash tables are so fast.

It feels like a free lunch to be able to save so much time using dictionaries, and unfortunately I've never seen a good (ELI5 or maybe ELI10) description.

Erik M
  • 185
  • 9
  • 1
    Does this answer your question? [How does a hash table work?](https://stackoverflow.com/questions/730620/how-does-a-hash-table-work) – Nathan Hughes Jun 13 '21 at 04:13
  • This is a duplicate of https://stackoverflow.com/questions/12020984/hash-table-why-is-it-faster-than-arrays – user10489 Jun 13 '21 at 04:14
  • 1
    The reason hash tables are fast is that, every key has a corresponding hash value generated. With this hash value, you know exactly where to look for the value of the key. Hence, the complexity is O(1). –  Jun 13 '21 at 04:20
  • @SanskarSingh Thanks. Wouldn’t this generation also need to be counted in the complexity? Or is that what the Microsoft docs are accounting for when they say “close to O(1)”? – Erik M Jun 13 '21 at 04:47
  • @ErikM the O(1) in this context makes no claim about how fast you can compute your hashes. It is just the complexity of finding a key with the specified hash value. –  Jun 13 '21 at 08:49

0 Answers0