On Thursday, July 16, 2015 at 2:59:02 PM UTC-4, Skip Montanaro wrote: > On Thu, Jul 16, 2015 at 1:36 PM, yoursurrogate...@gmail.com > <yoursurrogate...@gmail.com> wrote: > > If I understand correctly, lookup would not be a constant, yes? > > On the contrary, that's what you desire, nearly constant time > execution. To the greatest extent possible, you want the linked lists > to be of length zero or one. Part of the magic is in figuring out good > places to expand the size of the hash array. You don't want it to grow > too big, but you still want most linked lists to be very short. The > resize operation isn't done too often because it itself is expensive. > I believe Python dicts start out with an overly large initial hash > array (again, dredging up old memories of threads on python-dev) as an > optimization to avoid lots of early resize operations. > > Skip
Maybe people are reading a different implementation than I am. Python's dict object doesn't use linked lists to deal with hash collisions, it probes other slots instead. Brandon Rhodes did a great talk about how dicts work: http://pyvideo.org/video/276/the-mighty-dictionary-55 BTW: The Python 3 implementation is more complicated than in Python 2, I think to deal with sharing keys among dictionaries that have the same set of keys. --Ned. -- https://mail.python.org/mailman/listinfo/python-list
