2.基于散列表的工作原理，采用除留余数法H(key) = key % p (p<m) 作为散列函数，采用线性探测法处理冲突，实现散列查找算法，根据随机生成的正整数集合构造散列表，测量不同规模散列表的平均查找长度；

散列表是一种常见的数据结构，用于实现快速查找和插入操作。其基本原理是将待查找的关键字（key）通过散列函数映射到一个数组下标，将关键字存储在对应的数组位置中。当需要查找某个关键字时，先通过散列函数计算出其对应的数组下标，然后在该位置上查找关键字。如果该位置上没有该关键字，则通过探测算法（如线性探测法）向后寻找，直到找到该关键字或者找到一个空位置为止。

除留余数法是一种简单的散列函数，根据给定的散列表大小p和关键字key，取key%p作为其对应的数组下标。线性探测法是一种解决冲突的方法，当散列表中某个位置已经被占用时，向后寻找下一个空位置，直到找到该关键字或者找到一个空位置为止。

下面是基于散列表的查找算法的实现过程：

1. 初始化散列表为全部为空。
2. 对于每个关键字key，计算其散列值H(key)。
3. 如果散列表中H(key)位置为空，则将key插入该位置，结束查找过程。
4. 如果散列表中H(key)位置已经被占用，则使用线性探测法寻找下一个空位置，直到找到该关键字或者找到一个空位置为止。
5. 如果找到该关键字，则结束查找过程；否则将key插入该空位置，结束查找过程。

下面是根据随机生成的正整数集合构造散列表，并测量不同规模散列表的平均查找长度的代码实现：

import random

def hash_func(key, size):
    return key % size

def insert(hash_table, key):
    size = len(hash_table)
    index = hash_func(key, size)
    if hash_table[index] == None:
        hash_table[index] = key
    else:
        i = 1
        while True:
            new_index = (index + i) % size
            if hash_table[new_index] == None:
                hash_table[new_index] = key
                break
            i += 1

def search(hash_table, key):
    size = len(hash_table)
    index = hash_func(key, size)
    if hash_table[index] == key:
        return index
    else:
        i = 1
        while True:
            new_index = (index + i) % size
            if hash_table[new_index] == key:
                return new_index
            elif hash_table[new_index] == None:
                return -1
            i += 1
            if i == size:
                return -1

def avg_search_len(hash_table):
    size = len(hash_table)
    total_len = 0
    for key in range(size):
        index = search(hash_table, key)
        if index != -1:
            total_len += index + 1
    return total_len / size

# 生成随机正整数集合
data = [random.randint(1, 1000) for i in range(100)]

# 构造散列表
hash_table = [None] * 200
for key in data:
    insert(hash_table, key)

# 测量平均查找长度
avg_len = avg_search_len(hash_table)
print("散列表大小：200，平均查找长度：", avg_len)

hash_table = [None] * 500
for key in data:
    insert(hash_table, key)

avg_len = avg_search_len(hash_table)
print("散列表大小：500，平均查找长度：", avg_len)

hash_table = [None] * 1000
for key in data:
    insert(hash_table, key)

avg_len = avg_search_len(hash_table)
print("散列表大小：1000，平均查找长度：", avg_len)

以上代码中，我们先生成了一个包含100个随机正整数的集合，然后分别构造了大小为200、500和1000的散列表，并测量了其平均查找长度。实际应用中，散列表大小的选择需要根据具体的数据集和性能要求进行优化。