On Jan 30, 7:02 pm, FireNWater <[EMAIL PROTECTED]> 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. -- http://mail.python.org/mailman/listinfo/python-list