Lots of good answers.
Warning: *this answer is ultra simplistic one to explain the implementation
succinctly*.
A little more from an implementation perspective dict operations usually
involve converting a dict into a hash. This hash is then converted into a
bucket. And sometimes when one gets into a collision, an alternative bucket
may need to get selected. In a simplistic example lets say we have 100
buckets, the hash is computed by adding the ascii values of the bytes
comprising the key.
Now lets assume the the key is the character 'AB'
Since the ascii code of 'A' is 65, and 'B' is 66 and there are no other
characters, then given our hash algorithm the hash will work out to 65 + 66
= 131
A simple hash to bucket mapping model is to use mod / modulo. Since 131 mod
100 which leads us to 31.
Assuming there are no key collisions and the buckets are stored as an array,
the key will now be stored in bucket no. 31 (zero based index). If there is
a collision - the key will be stored in some other bucket based on the
resolution provided by the collision management algorithm
Usually when one invokes a ".keys()" method, the most efficient way is to
run through the buckets array and spit out the keys stored in each non empty
bucket.
That should hopefully clarify why ".keys()" generally does not return keys
ordered by the keys themselves, it often will return keys ordered by the
buckets they are stored into.
Also since changing the internal logic of the hash table with regards to key
-> hash -> bucket mapping and collision management, will change the internal
order for the same set of keys.
Similarly even if the same keys are inserted into the hash table in
different orders, the resultant order of keys can change if some of the keys
collide.
As a result hash tables will generally not issue any guarantee any ordering
on the keys since that would require additional efforts and the implied
performance loss - something thats often unnecessary for most typical dict
operations.
Dhananjay
On Wed, Aug 18, 2010 at 10:58 PM, Anand Shankar <anand_shan...@yahoo.com>wrote:
> During a tutorial python session with my colleagues I was presented with a
> basic
> question
>
> >>> d = {'apple':2,'banana':5, 'coke': 6}
> >>> print d.keys()
> ['coke', 'apple', 'banana']
>
>
> Question is why does it not return
>
> ['apple','banana','coke']
>
> Similarly:
>
> >>> d = {'a':2,'b':4,'c':5,'d':4,'e':3}
> >>> print d.keys()
> ['a', 'c', 'b', 'e', 'd']
>
> why not
>
> ['a', 'b', 'c', 'd', 'e']
>
> I have no clues. Any inputs??
>
> anand
>
>
>
>
> _______________________________________________
> BangPypers mailing list
> BangPypers@python.org
> http://mail.python.org/mailman/listinfo/bangpypers
>
--
--------------------------------------------------------
blog: http://blog.dhananjaynene.com
twitter: http://twitter.com/dnene
_______________________________________________
BangPypers mailing list
BangPypers@python.org
http://mail.python.org/mailman/listinfo/bangpypers
