抽象字典

import datetime, time
import warnings

warnings.filterwarnings("ignore")


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, key, M=13):
        if self.length >= 0.8 * len(self._table):
            self.rehash(len(self._table))
        index = hash(key) % M

        i = 1
        while True:
            while index >= len(self._table):
                self.rehash(len(self._table))

            if self._table[index] is not None:
                if self._table[index].key == key:
                    self.length -= 1
                    return index

            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)


class Hash_Dic(Hashtable):
    def __setitem__(self, key, value):
        time1 = time.clock()
        self.add(key, value, time1)

    def __getattr__(self, item):
        return self.get(item)

    def _iter_slot(self):
        array = Array(size=self.length)
        pr = 0
        k = False
        for slot in self._table:
            if slot is not None:
                if array[0] is None:
                    array[0] = slot
                    pr += 1
                else:
                    for i, s in enumerate(array):
                        if s is not None:
                            if s.time > slot.time:
                                if array[i + 1] is not None:
                                    continue
                                array[i] = slot
                                array[i + 1] = s
                                pr += 1
                                k = True
                                break

                            if not k:
                                array[pr] = slot
                                pr += 1
                                break
                        else:
                            array[pr] = slot
                            pr += 1
                            break

        for slot in array:
            yield slot

    def items(self):
        for slot in self._iter_slot():
            yield (slot.key, slot.value)

    def keys(self):
        for slot in self._iter_slot():
            yield slot.key

    def values(self):
        for slot in self._iter_slot():
            yield slot.value


a=set({1,2,3})

Dict = Hash_Dic()
Dict[‘a‘] = 1
Dict[‘b‘] = 2
Dict[‘c‘] = 3
Dict[‘a‘] = 4
for i in Dict.items():
    print(i)

for key in Dict.keys():
    print(key)

for value in Dict.values():
    print(value)

抽象字典

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