运用除余法构造散列函数，并用拉链法解决地址冲突的散列表构造及其检索算法。

### 回答1：
散列函数是一种将任意长度的输入数据映射到固定长度输出数据的函数。除余法是一种常用的散列函数构造方法，它将输入数据除以一个固定的数，然后取余数作为输出数据。例如，如果我们要将一个整数 x 散列到一个长度为 n 的散列表中，可以使用除余法构造散列函数 h(x) = x mod n。

然而，即使使用了好的散列函数，仍然可能会发生地址冲突，即两个不同的输入数据被映射到了同一个散列表地址上。为了解决地址冲突，可以使用拉链法。具体来说，对于每个散列表地址，我们维护一个链表，将所有映射到该地址上的数据都存储在链表中。当需要查找一个数据时，我们首先计算出它的散列值，然后在对应的链表中查找。

散列表的构造和检索算法如下：

构造散列表：
1. 初始化一个长度为 n 的散列表，每个地址对应一个空链表。
2. 对于每个输入数据 x，计算它的散列值 h(x)。
3. 将 x 插入到散列表中对应的链表中。

查找数据：
1. 计算要查找的数据的散列值 h。
2. 在散列表中找到对应的链表。
3. 在链表中查找要查找的数据，如果找到了就返回它，否则返回空。

需要注意的是，散列表的性能取决于散列函数的好坏和地址冲突的程度。如果散列函数不好或者地址冲突太多，散列表的性能会变得很差。因此，在实际应用中，需要根据具体情况选择合适的散列函数和解决地址冲突的方法。

### 回答2：
散列表（Hash Table）是一种高效的数据结构，可以在O(1)的时间内进行搜索、插入和删除操作。其中，散列函数（Hash Function）是散列表实现的关键，它将数据的键（Key）转换成数组下标，以便将数据存储到散列表中的对应位置。除余法（Division Method）是一种简单有效的散列函数构造方法，它的步骤如下：

1. 选择散列表大小m，通常取一个质数或者接近2的整数幂的数。
2. 对于每个键k，计算它的散列值h(k)=k mod m，其中mod表示取模运算。
3. 将具有相同散列值的键存储在同一个链表中，称为同义词链（Synonym Chain）或者桶（Bucket）。

例如，对于一个大小为7的散列表，如果有5个键分别为10、22、37、45和55，那么它们的散列值分别为3、1、2、3和6。根据拉链法（Chaining），可以将它们存储到如下的链表中：

0：
1： 22
2： 37
3： 10 -> 45
4：
5：
6： 55

其中，箭头表示链表的指针。如果要插入一个新键，只需要计算它的散列值，然后将它添加到对应的链表末尾即可。如果要查找一个键，也只需要计算它的散列值，然后在对应的链表中顺序查找即可。这种方法的时间复杂度与链表的长度有关，但通常每个链表的长度比较小，因此效率比较高。

对于散列表的构造和检索算法，其代码实现如下：

class LinkedListNode:
    def __init__(self, key=None, value=None, next=None):
        self.key = key
        self.value = value
        self.next = next

class HashTable:
    def __init__(self, size=997):
        self.size = size
        self.table = [None] * self.size
    
    def hash(self, key):
        return key % self.size
    
    def insert(self, key, value):
        h = self.hash(key)
        if self.table[h] is None:
            self.table[h] = LinkedListNode(key, value)
        else:
            curr = self.table[h]
            while curr.next is not None:
                if curr.key == key:
                    curr.value = value
                    return
                curr = curr.next
            if curr.key == key:
                curr.value = value
            else:
                curr.next = LinkedListNode(key, value)
    
    def search(self, key):
        h = self.hash(key)
        curr = self.table[h]
        while curr is not None:
            if curr.key == key:
                return curr.value
            curr = curr.next
        return None

其中，LinkedListNode表示链表节点，它包含键、值和指向下一个节点的指针；HashTable表示散列表，它包含散列表大小和散列表数组，以及散列函数、插入和查找操作。对于插入操作，如果对应的链表为空，则创建一个新节点作为链表的头节点；否则从头节点开始遍历链表，如果找到键相同的节点，则更新它的值；如果遍历到链表末尾还没有找到，则创建一个新节点添加到链表末尾。对于查找操作，也是从对应的链表头节点开始遍历，直到找到键相同的节点或者遍历到链表末尾。如果找到，则返回节点的值；否则返回None。

总之，运用除余法构造散列函数，并用拉链法解决地址冲突的散列表构造及其检索算法是一种简单有效的数据结构，可以高效地进行搜索、插入和删除操作。需要注意的是，散列表的大小越大，冲突发生的概率越小，但消耗的内存也越大。因此，需要根据实际情况进行优化和平衡。

### 回答3：
散列表是一种高效的数据结构，它通过散列函数将数据直接映射到数组中，实现了常数时间复杂度的数据访问。而散列函数就是将不同的数据映射到不同的地址上，如果两个不同的数据映射到同一个地址上，则产生了地址冲突。为了解决地址冲突，我们可以使用拉链法，即将同一个地址上的多个数据存储在一个链表中。

散列函数可以采用除余法构造，即将关键字k对一个质数m取余，即h(k)=k mod m。这种方法简单易用，具有一定的随机性，但可能会产生冲突。我们可以采用一些技巧来减少冲突的发生，如选取合适的质数m，使其远远大于可能存储的元素数目。还可以在散列函数中加入一些额外的运算，如乘数法、斐波那契法等，以增加随机性。

拉链法就是将同一个散列地址上的多个元素存储在一个链表中，这个链表就是函数值相同的所有关键字的组合。链表的头指针存放在散列表中，每个结点包含一个关键字及其对应的记录。当发生冲突时，新加入的元素直接插入到链表头部，查找时遍历链表，直到找到目标元素或者到达链表尾部。

在散列表的检索算法中，首先通过散列函数将关键字映射到散列表中的某个地址上。如果地址中已经有了关键字，则直接返回。如果地址中没有关键字，则遍历其链表，直到找到目标元素或者到达链表尾部。如果找到了目标元素，则返回其对应的记录；如果没有找到，则说明该元素不存在于散列表中。

总之，运用除余法构造散列函数，并用拉链法解决地址冲突，可以实现高效的散列表构造及其检索算法。当然，散列表的构造与使用需要结合具体的数据情况进行优化，以达到最优的效果。