Dictionary Keys question

[Dustan]

On Jan 30, 7:02 pm, FireNWater <kho... at gmail.com> wrote:
> Thank you for the explanation. . . I think I now have a (foggy)
> understanding of hash tables.  It seems to be a way to create order
> (an index) out of disorder (random numbers or characters) behind the
> scenes. .

The key thing to realize is, quite simply, don't rely on order in a
dictionary. If you do, bad things can happen. The underlying
implementation is not important to know.

But if you really do want to know, let me correct you here, and give a
perhaps clearer explanation (if not, there's no need to read any
further):

The 'order' that your speaking of is not implemented by the hash
*table*, per se, but rather by the hash function, which returns an
integer (the hash code).

The hash table takes the hash code and calculates where in its list to
place the object (as explained before, using modulo to shrink the
integer into the range of the list). If multiple items end up in the
same list, they are placed into a kind of linked list, with each node
containing an object and pointing to the next. Of course, if too many
objects end up in the same bucket, the efficiency of finding an object
in the hash table reduces to that of a linked list, so hash functions
are generally implemented to ensure a unique number (or as unique as
possible) to every object.

Python dictionaries are hash tables that automatically grow as space
is needed. While integers in the range of the list will never change
location unless the list shrinks, larger hash codes can move around
quite apparently randomly. Space available is also a factor, as others
have found out on this list. The order of a dictionary *is*
determined, but factors involved in deciding that order may appear
surprisingly mundane, and certainly variable across runs of your
program.