Dictionary in Python

[Fredrik Lundh]

Jijun Wang <jwang at new-access.com> wrote:
> Does anyone know how dictionary is implemented in Python
> (such as hash table, heap, linked list)?

hash tables:

http://www.python.org/doc/FAQ.html#6.17

> If my dictionary increases in size, how much is the
> impact on performace?

none, except for a) the work needed to resize the
dictionary as it fills up, and b) collisions caused by
bad hash algorithms (see footnotes 1 and 2).

</F>

1) bad algorithm:

class BadKey:
    def __init__(self, s):
        self.s = s
    def __hash__(self):
        print "hash", self.s
        return 1
    def __cmp__(self, other):
        print "cmp", self.s, other.s
        return cmp(self.s, other.s)

dict = {}
dict[BadKey("a")] = None
dict[BadKey("b")] = None
dict[BadKey("c")] = None
dict[BadKey("d")] = None
dict[BadKey("e")] = None

prints:

hash a
hash b
cmp a b
hash c
cmp a c
cmp b c
hash d
cmp c a
cmp c b
cmp a b
cmp c d
cmp a d
cmp b d
hash e
cmp c e
cmp a e
cmp b e
cmp d e

(note the extra comparisions caused
when "d" was inserted -- it's where
the dictionary is first resized)

2) good algorithm:

class GoodKey:
    def __init__(self, s):
        self.s = s
    def __hash__(self):
        print "hash", self.s
        return hash(self.s)
    def __cmp__(self, other):
        print "cmp", self.s, other.s
        return cmp(self.s, other.s)

dict = {}
dict[GoodKey("a")] = None
dict[GoodKey("b")] = None
dict[GoodKey("c")] = None
dict[GoodKey("d")] = None
dict[GoodKey("e")] = None

prints:

hash a
hash b
hash c
hash d
hash e

(no collisions at all, in other words)