解析这段代码:int main() { // 生成随机数集合 unordered_set<int> numbers = generateRandomNumbers(1000); // 构建线性探测法散列表和链地址法散列表 for (int num : numbers) { // 线性探测法插入 int pos = num % 10000; int i = 0; while (linearHashTable[pos] != 0) { pos = (pos + i) % 10000; i++; } linearHashTable[pos] = num; // 链地址法插入 ListNode* node = new ListNode(num); node->next = chainHashTable[pos]; chainHashTable[pos] = node; } // 统计线性探测法不同数字的查找长度和平均查找长度 vector<int> linearProbeCounts(1000, 0); int linearProbeTotal = 0; for (int num : numbers) { int count = linearProbeSearch(num); linearProbeCounts[num % 1000] += count; linearProbeTotal += count; } linearProbeAvg = (double)linearProbeTotal / numbers.size(); for (int i = 0; i < 1000; i++) { if (linearProbeCounts[i] > 0) { cout << "数字 " << i << " 的查找长度: " << (double)linearProbeCounts[i] / (numbers.size() / 1000) << endl; } } // 统计链地址法不同数字的查找长度和平均查找长度 vector<int> chainCounts(1000, 0); int chainTotal = 0; for (int num : numbers) { int count = chainSearch(num); chainCounts[num % 1000] += count; chainTotal += count; } chainAvg = (double)chainTotal / numbers.size(); for (int i = 0; i < 1000; i++) { if (chainCounts[i] > 0) { cout << "数字 " << i << " 的查找长度: " << (double)chainCounts[i] / (numbers.size() / 1000) << endl; } } cout << "线性探测法总平均查找长度: " << linearProbeAvg << endl; cout << "链地址法总平均查找长度: " << chainAvg << endl; return 0; }
时间: 2024-01-10 21:02:48 浏览: 143
这段代码是主函数 `main`,主要实现以下功能:
1. 生成一个包含 1000 个随机数的 `unordered_set` 容器 `numbers`。
2. 使用这些随机数来构建线性探测法散列表和链地址法散列表,其中线性探测法散列表使用数组 `linearHashTable` 实现,链地址法散列表使用数组 `chainHashTable` 实现,数组长度都为 10000。
3. 统计线性探测法和链地址法在查找这些随机数时的不同数字的查找长度及平均查找长度。
4. 输出线性探测法和链地址法的总平均查找长度。
具体实现过程如下:
在构建线性探测法散列表和链地址法散列表时,对于每个随机数,先计算它在哈希表中的位置 `pos`,然后使用一个循环来进行插入。对于线性探测法散列表,如果当前位置 `pos` 上已经有其它元素,则将位置 `pos` 向后移动一个位置(即 `(pos+i)%10000`),直到找到空位置。对于链地址法散列表,将该随机数作为新节点插入到链表的头部即可。
在统计线性探测法和链地址法的查找长度时,对于每个随机数,分别使用 `linearProbeSearch` 和 `chainSearch` 函数来查找它在哈希表中的位置。然后将查找次数加入到对应数字在 `vector` 容器中的位置上,同时累加总查找次数。最后,分别计算线性探测法和链地址法的平均查找长度,并输出每个数字的查找长度及平均查找长度。
总的来说,该程序实现了用线性探测法和链地址法来解决哈希冲突的问题,并比较了它们在查找随机数时的效率,从而验证了哈希表的高效性。
相关问题
使用unordered_set
`unordered_set` 是 C++ 标准库中的关联容器,它是一个无序的、不重复元素的集合。与 `set` 类似,`unordered_set` 的主要优势在于查找速度极快,因为它的内部实现了哈希表,通过哈希函数直接定位元素位置,时间复杂度通常接近 O(1)。然而,由于它是无序的,所以不能保证元素的插入顺序,而且插入和删除操作的时间复杂度也不是 O(1),但在平均情况下它们仍然是很快的。
如果明明使用 `unordered_set`,他会这样做:
```cpp
#include <iostream>
#include <unordered_set>
int main() {
int N;
std::cin >> N;
std::unordered_set<int> unique_numbers; // 使用 unordered_set 存储唯一的随机数
for (int i = 0; i < N; ++i) {
int num;
std::cin >> num;
unique_numbers.insert(num); // 插入新值,自动去除重复
}
int M = unique_numbers.size();
std::cout << M << "\n";
for (const auto& num : unique_numbers) { // 遍历并打印
std::cout << num << " ";
}
std::cout << "\n";
return 0;
}
```
使用 `unordered_set` 的好处是插入操作更简单,因为它不需要维护原有的排序,但是查询操作可能会略慢于 `set`,取决于具体的哈希函数性能和容器大小。
如何优化这段代码以提高生成速度?
为了优化这段代码,减少查找重复数的操作可以显著提高生成速度。由于我们是在生成每个随机数之前检查其是否已存在,所以可以考虑预先把0到`max`的所有可能值存储在一个集合(如`std::unordered_set`),因为集合的查找操作时间复杂度为O(1),这比每次遍历向量快得多。
下面是优化后的代码示例:
```cpp
#include <iostream>
#include <random>
#include <unordered_set>
std::vector<int> generate_unique_random(int min, int max) {
std::default_random_engine generator(std::chrono::system_clock::now().time_since_epoch().count());
std::uniform_int_distribution<int> distribution(min, max);
std::unordered_set<int> used_numbers;
std::vector<int> unique_numbers;
while (unique_numbers.size() < 5) {
int random_num = distribution(generator);
if (used_numbers.insert(random_num).second) {
unique_numbers.push_back(random_num);
}
}
return unique_numbers;
}
int main() {
std::vector<int> unique_numbers = generate_unique_random(0, 99999); // 生成0-99999之间的五位数
for (const auto& num : unique_numbers) {
std::cout << num << " ";
}
std::cout << "\n";
return 0;
}
```
在这个版本中,我们使用`used_numbers.insert(random_num)`,如果插入成功(返回值为true),说明这个数还没被用过,将其加入向量`unique_numbers`。这样避免了每次生成都需要查找是否重复的过程。
阅读全文
相关推荐
















