On Jan 30, 3:09 pm, Berteun Damman <[EMAIL PROTECTED]> wrote: > On Wed, 30 Jan 2008 14:47:36 -0800 (PST), FireNWater <[EMAIL PROTECTED]> > wrote: > > I'm curious why the different outputs of this code. If I make the > > dictionary with letters as the keys, they are not listed in the > > dictionary in alphabetical order, but if I use the integers then the > > keys are in numerical order. > > > I know that the order of the keys is not important in a dictionary, > > but I was just curious about what causes the differences. Thanks!! > > I don't know the exact way Python's hash function works, but I can take > a guess. I'm sorry if I explain something you already know. > > A hash is for quickly looking up data. Yet, you don't want to waste too > much memory. So there is a limit number of spaces allocated, in which to > store objects. This number of spaces can be thought of as a list. Then, > if you put something into the dict, Python computes the 'hash' of this > object, which basically forms the index in the list where to store it. > So every object should be mapped onto some index within the list. (If > you retrieve it, the hash is computed again, and the value on that index > is looked up, like list indexing, these are fast operations.) > > Say, if you have 100 spaces, and someone puts in integer in the list, > the hashfunction used might be % 100. So the first 100 integers would > always be placed at consecutive places. For strings however, a more > complicated hash-function would be used, which takes into account more > characters, so strings don't end up in order. > > For integers, if you put in integers that are spread very widely apart, > they won't end up in order either (see the mod 100 example, 104 will > come before 10). > > If you replace the list2 in your example by: > list2 = [10000 * x for x in range(1,9)] > > You will see that this one doesn't end up in order either. So, there's > no exception for integers when it comes to the order, yet the particular > properties of the hash function will cause sequential integers to end up > in order under some circumstances. > > Berteun > > PS: > What happens if two values map onto the same space is of course an > obvious question, and the trick is choosing your hashfunction so this > occurs not very often on average. If it happens there are several > strategies. Wikipedia probably has an explanation of how hash-functions > can work in such a case.
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. . -- http://mail.python.org/mailman/listinfo/python-list