为班级30个人的姓名设计一个哈希表，平均查找长度的上限为2，完成相应的建表和查表。用除留余数法和线性探测再散列法

好的，我可以帮你解答这个问题。

首先，我们需要确定哈希表的大小。由于班级人数为30，为了保证平均查找长度的上限为2，我们可以将哈希表的大小设置为15，也就是说，每个人在哈希表中对应的位置可以是0到14之间的整数。

接下来，我们可以选择使用除留余数法或线性探测再散列法来建立哈希表。以下是两种方法的实现：

1. 除留余数法

除留余数法是最简单的哈希函数之一，它的计算公式为：

$h(k) = k \mod m$

其中，$k$是关键字，$m$是哈希表的大小。我们可以将每个人的姓名转换成一个整数，然后使用除留余数法计算出它在哈希表中的位置。

下面是使用除留余数法建立哈希表的示例代码：

class HashTable:
    def __init__(self, size):
        self.size = size
        self.table = [None] * size

    def hash(self, key):
        return key % self.size

    def insert(self, key, value):
        index = self.hash(key)
        if self.table[index] is None:
            self.table[index] = (key, value)
        else:
            i = (index + 1) % self.size
            while i != index:
                if self.table[i] is None:
                    self.table[i] = (key, value)
                    break
                i = (i + 1) % self.size

    def search(self, key):
        index = self.hash(key)
        if self.table[index] is None:
            return None
        elif self.table[index][0] == key:
            return self.table[index][1]
        else:
            i = (index + 1) % self.size
            while i != index:
                if self.table[i] is None:
                    return None
                elif self.table[i][0] == key:
                    return self.table[i][1]
                i = (i + 1) % self.size
            return None

在上面的代码中，我们使用了线性探测法来解决哈希冲突。如果某个位置已经被占用，我们就顺序往后查找，直到找到一个空位置为止。

2. 线性探测再散列法

线性探测再散列法是一种解决哈希冲突的方法，它的计算公式为：

$h(k, i) = (h'(k) + i) \mod m$

其中，$h'(k)$是第一次哈希函数的计算结果，$m$是哈希表的大小，$i$是一个变量，表示线性探测的步长。

下面是使用线性探测再散列法建立哈希表的示例代码：

class HashTable:
    def __init__(self, size):
        self.size = size
        self.table = [None] * size

    def hash(self, key):
        return key % self.size

    def rehash(self, key, i):
        return (self.hash(key) + i) % self.size

    def insert(self, key, value):
        i = 0
        while i < self.size:
            index = self.rehash(key, i)
            if self.table[index] is None:
                self.table[index] = (key, value)
                break
            i += 1

    def search(self, key):
        i = 0
        while i < self.size:
            index = self.rehash(key, i)
            if self.table[index] is None:
                return None
            elif self.table[index][0] == key:
                return self.table[index][1]
            i += 1
        return None

在上面的代码中，我们使用了线性探测再散列法来解决哈希冲突。如果某个位置已经被占用，我们就按照线性探测的步长依次往后查找，直到找到一个空位置为止。

现在，我们可以将班级30个人的姓名插入到哈希表中，并进行查找。下面是示例代码：

names = ['Alice', 'Bob', 'Charlie', 'David', 'Emily', 'Frank', 'Grace', 'Henry', 'Isaac', 'Jack', 'Kate', 'Lily', 'Megan', 'Nancy', 'Oliver', 'Peter', 'Queen', 'Rose', 'Sam', 'Tom', 'Ursula', 'Victor', 'Wendy', 'Xavier', 'Yvonne', 'Zoe', 'Adam', 'Ben', 'Cathy']

# 使用除留余数法建立哈希表
hash_table1 = HashTable(15)
for i, name in enumerate(names):
    hash_table1.insert(i, name)

# 使用线性探测再散列法建立哈希表
hash_table2 = HashTable(15)
for i, name in enumerate(names):
    hash_table2.insert(i, name)

# 查找哈希表中的元素
print(hash_table1.search(3))  # David
print(hash_table2.search(3))  # David

在上面的代码中，我们先定义了30个人的姓名，然后分别使用除留余数法和线性探测再散列法建立了两个哈希表。最后，我们分别查找了哈希表中关键字为3的元素，结果都是David。