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

python data-structures hash dictionary hashtable
TIMEX picture TIMEX · Jan 14, 2010 · Viewed 35k times · Source

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

Answer

R Samuel Klatchko picture R Samuel Klatchko · Jan 14, 2010

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 it's 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.

Related questions

Hashable, immutable

From a recent SO question (see Create a dictionary in python which is indexed by lists) I realized I probably had a wrong conception of the meaning of hashable and immutable objects in python. What does hashable mean in practice? …

Read More
What is the difference between Python's list methods append and extend?

What's the difference between the list methods append() and extend()?

Read More
How to remove a key from a Python dictionary?

When deleting a key from a dictionary, I use: if 'key' in my_dict: del my_dict['key'] Is there a one line way of doing this?

Read More