[aklug] Re: Lists

On Tue, Jul 26, 2011 at 12:17:02PM -0800, Tim Johnson wrote:
> > Python lists are really well implemented
> I haven't done any performance tests on lists vs dictionaries -
> it is really a bit like comparing apples and oranges -
> I believe python dictionaries are implemented from C linked lists.

dicts in Python are implemented as a hash structure; a given key is run
through a function to obtain an integer, and that integer is used to
index into a block of memory. A linked list would be wholly unsuited, as
lookup time would be horrible.

Like most languages implementing a hashing data structure there are
buckets; when two keys hash to the same value, you can't simply discard
them, so you make the value a bucket of all the hash collisions.
Buckets are sometimes implemented as linked lists, sometimes as just an
array; I'm not sure which Python uses.

--
Michael Fowler
www.shoebox.net
---------
To unsubscribe, send email to <aklug-request@aklug.org>
with 'unsubscribe' in the message body.