python实现散列表的链表法

　　在散列中，链接法是一种最简单的碰撞解决技术，这种方法的原理就是把散列到同一槽中的所有元素

都放在一个链表中。

　　链接法有两个定理，定理一：

　　在简单一致散列的假设下，一次不成功查找的期望时间为O(1 + n)

　　定理二：

　　在简单一致散列的假设下，平均情况下一次成功的查找需要的时间为O（1 + n）

　　该方法使用python的实现如下：

    # keys函数

#!/usr/bin/env python

# coding=utf-8

class Dict:

    def __init__(self, num):

        self.__solts__ = []

        self.num = num

        for _ in range(num):

            self.__solts__.append([])

    def hash_fun(self,key,num):

        hashval = 0

        x = key

        if x < 0:

                print "the key is low"

                return

        while x != 0:

                hashval = (hashval << 3) + x%10

                x /=10

        return hashval % num

    def put(self, key, value):

        i = self.hash_fun(key,self.num) % self.num

        for p, (k, v) in enumerate(self.__solts__[i]):

            if k == key:

                break

        else:

            self.__solts__[i].append((key, value))

            return

        self.__solts__[i][p] = (key, value)

    def get(self, key):

        i = self.hash_fun(key,self.num) % self.num

        for k, v in self.__solts__[i]:

            if k == key:

                return v

        raise KeyError(key)

    # keys函数

    def keys(self):

        ret = []

        for solt in self.__solts__:

            for k, _ in solt:

                ret.append(k)

        return ret

    def __getitem__(self,key):

        return self.get(key)

    def __setitem__(self,key,data):

        self.put(key,data)

H = Dict(13)

H[54] = "cat"

H[26] = "dog"

H[93] = "lion"

H[17] = "tiger"

H[77] = "bird"

H[31] = "cow"

H[44] = "goat"

H[55] = "pig"

H[20] = "chicken"

print H.get(54)

H.put(13,"duck")

print H.__solts__

print H.keys()

　　运行结果：

cat

[[], [], [(20, 'chicken')], [], [], [(17, 'tiger')], [(55, 'pig')], [(93, 'lion')], [], [], [(44, 'goat')], [(54, 'cat'), (26, 'dog'), (77, 'bird'), (31, 'cow')], [(13, 'duck')]]

[20, 17, 55, 93, 44, 54, 26, 77, 31, 13]

　　参考文档：算法导论