Description

采用除留余数法（H（key）=key %n）建立长度为n的哈希表，处理冲突用开放定址法的线性探测，有冲突时：其中n=1,2,3,4，…,n-1

Input 第一行为哈希表的长度n；第二行为关键字集合；第三行为要查找的数据。

Output 第一行输出建立的哈希表；

如果查找成功，在第二行输出关键字在哈希表中的比较次数；如果查找不成功，输出-1。

Sample Input 1

7 67 84 18 26 34 28 84 Sample Output 1

[84, 34, 28, None, 67, 18, 26] 1 Sample Input 2

11 19 01 23 14 55 68 11 82 36 36 Sample Output 2

[55, 1, 23, 14, 68, 11, 82, 36, 19, None, None] 5 Sample Input 3

13 16 74 60 43 54 90 46 31 29 88 77 16 Sample Output 3

[77, None, 54, 16, 43, 31, 29, 46, 60, 74, 88, None, 90] 1 Sample Input 4

11 47 7 29 11 9 84 54 20 30 30 Sample Output 4

[11, 54, 20, 47, 30, None, None, 7, 29, 9, 84] 8 Sample Input 5

13 555 89 56 41 2 3 58 96 54 52 23 56 85 85 Sample Output 5

[52, 85, 41, 2, 56, 3, 58, 96, 54, 555, 23, 89, 56] 8

分析: 解决冲突要求用开放定址法里的线性探测再散列法，不熟悉的同学可以自行百度。这里提一下几个细节问题： 1.di取多少可以从测试用例里看出来 2.注意重复元素都要存 3. 这里不存在存不下的情况，但是若要考虑，需要一个记录哈希表已用空间的变量，满了要扩容 4. 不明白property啥意思的同学，可以看我哈希—宝石的博客，也可以自行百度，简单说就是把函数变成属性，是一种装饰器

Coding

class HashTable(object):
    def __init__(self, size: object = 10) -> object:
        self.size = size
        self._table = [None] * size

    def find_key(self, key):
        index = key % self.size
        while self._table[index] is not None:
            index = (index + 1) % self.size
        return index

    def append(self, key):
        index = self.find_key(key)
        if index is not None:
            self._table[index] = key
            return True
        else:
            return False

    def check_key(self, key):
        t = 1
        index = key % self.size
        while self._table[index] is not None and key != self._table[index]:
            t += 1
            index = (index + 1) % self.size
        if self._table[index] is not None and key == self._table[index]:
            print(t)
            return True
        else:
            print(-1)
            return False

    @property
    def table(self):
        return self._table

n = int(input())
h = HashTable(n)
k = list(map(int, input().split()))
for i in range(len(k)):
    h.append(k[i])
print(h.table)
h.check_key(int(input()))