负载哈希

class Array:
    def __init__(self, size=8, init=None):
        self._size = size
        self._items = [init] * size

    def __getitem__(self, index):
        return self._items[index]

    def __setitem__(self, key, value):
        self._items[key] = value

    def __len__(self):
        return self._size

    def clear(self, value=None):
        for i in range(len(self._items)):
            self._items[i] = value

    def __iter__(self):
        for i in self._items:
            yield i


class Slot(object):
    def __init__(self, key, value,time=None):
        self.key, self.value, self.time = key, value, time


class Hashtable:
    UNUSED = None
    EMPTY = Slot(None, None)

    def __init__(self):
        self._table = Array(8, Hashtable.UNUSED)
        self.length = 0

    def __len__(self):
        return self.length

    def _hash(self, value, M=13):
        if self.length >= 0.8 * len(self._table):
            self.rehash(len(self._table))
        index = hash(value) % M
        i = 1
        while True:
            while index >= len(self._table):
                self.rehash(len(self._table))
            if self._table[index] is not None and self._table[index] != Hashtable.EMPTY:
                index = (index + i * i) % M
                i += 1
            else:
                return index

    def find_key(self, key):
        for index, i in enumerate(self._table):
            if i != Hashtable.EMPTY and i != Hashtable.UNUSED:
                if i.key == key:
                    return index
        return False

    def rehash(self, length):
        old_table = self._table
        self._table = Array(length * 2, Hashtable.UNUSED)
        for index, obj in enumerate(old_table, 0):
            self._table[index] = obj

    def add(self, key, value,time=None):
        index = self._hash(key)
        self._table[index] = Slot(key, value, time)
        self.length += 1

    def __iter__(self):
        for obj in self._table:
            if obj != Hashtable.UNUSED and obj != Hashtable.EMPTY:
                yield obj.key

    def remove(self, key):
        index = self.find_key(key)
        if not index:
            raise NameError
        self._table[index] = Hashtable.EMPTY
        self.length -= 1

    def clear(self):
        self.length = 0
        self._table = Array(8, Hashtable.UNUSED)

负载哈希

原文：https://www.cnblogs.com/xuxingping/p/10946335.html