python - 哈希表模拟

Question

我正在编写一个函数，它模拟按照哈希表中给定的顺序插入的键列表。输出应该是以列表形式表示的哈希表(值 None 用于表示未使用的位置)。

例如:list_of_values = [26, 54, 94, 17, 31, 77, 44, 51]

我已经编写了代码，但不断出现错误和问题，感谢您的帮助!

def hash_probe(size, key,):
    hash_key = key % len(size)   
    if size[hash_key] != None: 
        size[hash_key] = key 
    else: 
        while size[hash_key] == None: 
            if hash_key != len(size)- 1: 
                hash_key += 1 
            else:
                hash_key = 0 
        size[hash_key] = key
    return size

Answer 1

我假设您想要向给定代码中的哈希表添加新项并使用 linear probing 解决冲突.
在这种情况下，有一些问题:

• 在此部分 - if size[hash_key] != None: size[hash_key] = key, 您可能会将新值覆盖到旧值上。
• 在对列表进行第一次添加时，代码将进入 无限循环。
• 尽管与代码的功能无关，但列表 size 的名称似乎有点奇怪。

正确的代码应该是:

def hash_probe(keys, size):
    hash_table = [None] * size

    for key in keys:
        hash_key = key % size
        # If we find an empty position, insert it there
        if hash_table[hash_key] is None:
            hash_table[hash_key] = key
        else:
            i = (hash_key + 1) % size

            # Find an unused position
            count = 0
            while count < size and hash_table[i] is not None:
                i = (i + 1) % size
                count += 1

            # If it is an empty position, insert it
            if hash_table[i] is None:
                hash_table[i] = key
            else:
                print("No more space in the hash table!!")

    return hash_table


keys = [26, 54, 94, 17, 31, 77, 44, 51]
hash_table = hash_probe(keys, 13)
print(hash_table)