pythondata-structureshashdictionaryhashtable

What is the true difference between a dictionary and a hash table?


I've always used dictionaries. I write in Python.


Solution

  • A dictionary is a general concept that maps keys to values. There are many ways to implement such a mapping.

    A hashtable is a specific way to implement a dictionary.

    Besides hashtables, another common way to implement dictionaries is red-black trees.

    Each method has its own pros and cons. A red-black tree can always perform a lookup in O(log N). A hashtable can perform a lookup in O(1) time although that can degrade to O(N) depending on the input.