python实现字典（带hash考虑hash碰撞）

class Hashtable:
    class Node:
        def __init__(self,key,val,next=None):
            self.key=key
            self.val=val
            self.next=next


    def __init__(self,n_buckets=1000):
        self.n_buckets=[None]*n_buckets

    def __setitem__(self, key, value):
        bidx=hash(key)%len(self.n_buckets)
        # self.n_buckets[bidx]=[key,value]
        n=self.n_buckets[bidx]
        while n:
            if n.key==key:
                n.val=value
                return
            else:
                n=n.next
        else:
            self.n_buckets[bidx]=Hashtable.Node(key,value,next=self.n_buckets[bidx])

    def __getitem__(self, key):
        bidx=hash(key)%len(self.n_buckets)
        n=self.n_buckets[bidx]
        while n:
            if n.key==key:
                return n.val
            else:
                n=n.next
        else:
            raise KeyError()

    def __contains__(self, key):
        try:
            _=self[key]
            return True
        except:
            return False

    def __iter__(self):
        for n in self.n_buckets:
            while n:
                yield n.key
                n=n.next