HashedDict

自定义字典

	
class HashedDict(object):
    '''
        自定义hashtable
    '''
    def __init__(self, size=10):
        self.hash_list = [list() for _ in range(size)]
        self.size = size
        self.length = 0

    def __setitem__(self, key, value):
        hash_key = hash(key) % self.size
        sub_list = self.hash_list[hash_key]
        if sub_list:
        		# hash冲突时使用list向后追加元素 
            matched=False
            for item in sub_list:
                if item[0] == key:
                    item[1] = value
                    matched=True

            if not matched:
                sub_list.append([key, value])
                self.length += 1
        else:
            sub_list.append([key, value])
            self.length += 1

    def __getitem__(self, key):
        sub_list = self.hash_list[hash(key) % self.size]
        if sub_list:
            for item in sub_list:
                if item[0] == key:
                    return item[1]
        raise KeyError(key)

    def __contains__(self, key):
        sub_list = self.hash_list[hash(key) % self.size]
        for item in sub_list:
            if item[0] == key:
                return True
        return False

    def __repr__(self):
        result = []
        for sub_list in self.hash_list:
            for item in sub_list:
                result.append(str(item[0] + ":" + str(item[1])))

        return ",".join(result)

    def items(self):
        for sub_list in self.hash_list:
            if not sub_list:
                continue
            for innitem in sub_list:
                yield innitem

    def values(self):
        for sub_list in self.hash_list:
            if not sub_list:
                continue
            for innitem in sub_list:
                yield innitem[1]

    def __len__(self):
        return self.length

    def __str__(self):
        return self.__repr__()

test

	
def test_it():
    print('test begin')
    dd = HashedDict()
    dd['a'] = 1
    dd['b'] = 2
    print(dd)
    print(len(dd))
    print(repr(dd))
    print(list(dd.items()))
    print(list(dd.values()))
    print('test end')