sorting a dictionary

Duncan Booth duncan at
Wed Feb 5 15:33:15 CET 2003

Alex Martelli <aleax at> wrote in 
news:y490a.135838$0v.3813120 at

> d[k] is roughly constant time (dictionaries are hash tables) in
> terms of number of entries in the dictionary.  If the KEYS take
> non-O(1) time to hash, as I believe strings do [hash(x) is O(len(x))
> if x is a string -- I *think*], then that might be an issue, yes.

If I remember correctly, python stores the hash in each string, so if you 
have already used that string as a dictionary key the hash isn't 
recalculated. In this case the 'for k in d:' produces a sequence of keys 
that are guaranteed already pre-hashed.

Duncan Booth                                             duncan at
int month(char *p){return(124864/((p[0]+p[1]-p[2]&0x1f)+1)%12)["\5\x8\3"
"\6\7\xb\1\x9\xa\2\0\4"];} // Who said my code was obscure?

More information about the Python-list mailing list