Python Data Structures – Space Complexity of a Python Dictionary

Hash is an extremely poorly named data structure where the programmer has confused the interface with implementation (and was too lazy to write the full name, i.e. HashTable instead resorting to an abbreviation, Hash).

Dictionary is the “correct” name of the interface (= the ADT), i.e. an associative container that maps (usually unique) keys to (not necessarily unique) values.

A hash table is one possible implementation of such a dictionary that provides quite good access characteristics (in terms of runtime) and is therefore often the default implementation.

Such an implementation has two important properties:

1. the keys have to be hashable and equality comparable.
2. the entries appear in no particular order in the dictionary.

(For a key to be hashable means that we can compute a numeric value from a key which is subsequently used as an index in an array.)

There exist alternative implementations of the dictionary data structure that impose an ordering on the keys – this is often called a sorted dictionary (and is usually implemented in terms of a search tree, though other efficient implementations exist).

To summarize: a dictionary is an ADT that maps keys to values. There are several possible implementations of this ADT, of which the hash table is one. Hash is a misnomer but in context it’s equivalent to a dictionary that is implemented in terms of a hash table.

http://wiki.python.org/moin/TimeComplexity

That should pretty much cover everything. What more do you need that's not already on this page?