# 不使用字典构造的分离连接法版哈希表

class HashList():

    """  Simple hash function(seperate list table) by python list  """

    def __init__(self, table_size = 457):

        self.usage = 0             # 已用

        self.table_size = table_size  # max size of hash table

        # initial list table and the count num of table's list

        self.hash_table = [[] for i in range(self.table_size)]

        self.flags = [0 for i in range(self.table_size)]   # the num of element store in each cell list

    def __len__(self):

        return self.usage

    def __getitem__(self, key):

        return self.get(key)

    def __setitem__(self, key, value):

        return self.insert(key, value)

    def __contain__(self, key):

        if self.get(key) is None:

            return False

        else:

            return True

    def hash(self, key):

        return (key + 27) % self.table_size    # simple hash

    def check(self, key):

    # handle nums(int) and chars

        flag = False  # [], "", 0 == False

        if key is not None:

            if isinstance(key, int) or isinstance(key, str):

                flag = True

            else:

                print("Can't handle other datatype!")

        else:

            print("Key is None!")

        return flag

    def get_pos(self, key):

        # 每个函数只做自己该做的事

        pos = 0

        if isinstance(key, int):

            pos = self.hash(key)       # [[], [], ... , [[k1, v1], [k2, v2]], ..., []]

        elif isinstance(key, str):

            pos = self.hash(sum(map(lambda x: ord(x), key)))

        return pos

    def get(self, key):

        value = None

        if self.check(key):

            pos = self.get_pos(key) # 遍历key对应列表

            for i in range(self.flags[pos]):

                if self.hash_table[pos][i][0] == key:

                    # 对应pos的list上存在key   print("\nfinding  key:{}, pos:{}, idx:{}".format(key, pos, i))

                    value = self.hash_table[pos][i][1]

                    break

        return value           # invalid key

    def insert(self, key, value):

        # Support key datatype: integer and string

        flag = False

        if self.check(key):

            if self.__contain__(key):

                print("Key:{} exsit!".format(key))  # 真存在key

            else:

                pos = self.get_pos(key)          # key合法但是不存在

                print("Insert key:{}, value:{}, pos:{}".format(key, value, pos))

                if len(self.hash_table[pos]) == 0:

                    self.usage += 1          # if it's empty key, add usage num

                self.hash_table[pos].append([key, value])   # 需存储键和值（对于id password很危险）

                self.flags[pos] += 1     # num of element on this key

                flag = True

        return flag

    def clear(self):

        self.usage = 0             # 已用

        self.table_size = table_size  # max size of hash table

        self.flags = [0 for i in range(self.table_size)]

        self.hash_table = [[] for i in range(self.table_size)]
 

def main():

    table = HashList()

    table["shopping"] = "8008208820"

    table["12312qweq"] =  [12312,123]

    table[12312] = [12, 2, 123]

    table.insert("helloworld", 12312)

    table.insert("1888888888", "My brother")

    table.insert("1518089898", "No problem")

    table.insert([], 12312)

    table.insert("", 12312)

    table.insert(None, 12312)  

    print()

    table.insert(12312, [12, 2, 123])

    table.insert("hash is hash", 110)

    table["FirePolice"] = 119

    print('\n',12312, table.get(12312))

    print("12312qweq", table.get("12312qweq"))

    print("hash is hash", table["hash is hash"])

    print("1888888888", table["1888888888"])

    t = HashList()

    [t.insert(chr(ord('a') + i), i) for i in range(26)]

if __name__ == "__main__":

    main()