通过hashtable实现dic

# -*- encoding: utf-8 -*-
"""
@File    : 123.py
@Time    : 2021-10-07 18:11
@Author  : XD
@Email   : gudianpai@qq.com
@Software: PyCharm
"""
#实现ADT Map （字典）
class HashTable:
    def __init__(self):
        self.size = 11  # 可以任意设置，但为了便于求解，应该设为素数
        self.slots = [None] * self.size
        self.data = [None] * self.size

    # 定义散列函数
    def hashfunction(self, key):
        return key % self.size

    # 定义冲突解决方法，简单线性加一
    def rehash(self, oldhash):
        return (oldhash + 1) % self.size

    def put(self, key, data):
        hashvalue = self.hashfunction(key)
        # key不存在
        if self.slots[hashvalue] == None:
            self.slots[hashvalue] = key
            self.data[hashvalue] = data
        # key已存在
        else:
            # 未发生冲突
            if self.slots[hashvalue] == key:
                self.data[hashvalue] = data
            else:  # 发生散列冲突
                nextslot = self.rehash(hashvalue)
                while self.slots[nextslot] != None and self.slots[nextslot] != key:
                    nextslot = self.rehash(nextslot)
                if self.slots[nextslot] == None:
                    self.slots[nextslot] = key
                    self.data[nextslot] = data
                else:
                    self.data[nextslot] = data

    def get(self, key):
        startslot = self.hashfunction(key)
        pos = startslot
        # 空槽时则表示找不到key
        while self.slots[pos] != None:
            if self.slots[pos] == key:  # 找到key
                return self.data[pos]
            else:
                pos = self.rehash(pos)  # 没找到key，找下一个
                if pos == startslot:  # 回到起点表示没找到key
                    return None
        return None

    # 通过设置__getitem__和__setitem__就可以实现形如H[key]的取值和赋值
    def __getitem__(self, key):
        return self.get(key)

    def __setitem__(self, key, data):
        self.put(key, data)


if __name__ == '__main__':
    H = HashTable()
    H[1] = 'cat'
    H[5] = 'piajun'
    print(H[1])
    print(H[5])
    print(H[2])