案例5-1.3 整型关键字的散列映射

2024-10-18 07:04:44

案例5-1.3 整型关键字的散列映射

分数 25

全屏浏览

切换布局

作者 DS课程组

单位浙江大学

给定一系列整型关键字和素数 p，用除留余数法定义的散列函数 H(key)=key%p 将关键字映射到长度为 p 的散列表中。用线性探测法解决冲突。

输入格式:

输入第一行首先给出两个正整数 n（≤1000）和 p（≥n 的最小素数），分别为待插入的关键字总数、以及散列表的长度。第二行给出 n 个整型关键字。数字间以空格分隔。

输出格式:

在一行内输出每个整型关键字在散列表中的位置。数字间以空格分隔，但行末尾不得有多余空格。

输入样例:

4 5
24 15 61 88

输出样例:

4 0 1 3

代码长度限制

16 KB

时间限制

400 ms

内存限制

64 MB

栈限制

8192 KB

思路

散列函数和线性探测法仍然用于处理关键字的插入。
处理重复关键字：使用一个哈希表（或字典）来记录每个关键字的第一次插入位置。如果关键字已经存在于该记录中，直接输出其记录的插入位置，而不再进行新的插入和探测。
输出格式控制：输出每个关键字（包括重复的）的散列表位置。

代码

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

int main() {
    int n, p;
    cin >> n >> p;  // 输入关键字数量n和散列表长度p
    vector<int> hashTable(p, -1);  // 初始化散列表，-1表示空位
    unordered_map<int, int> positionMap;  // 记录每个关键字的插入位置
    vector<int> keys(n);  // 存储输入的关键字
    
    // 输入所有关键字
    for (int i = 0; i < n; ++i) {
        cin >> keys[i];
    }

    // 处理每个关键字
    for (int i = 0; i < n; ++i) {
        int key = keys[i];

        // 检查是否已经记录过该关键字的位置
        if (positionMap.find(key) != positionMap.end()) {
            // 如果该关键字已经被插入过，直接输出之前的位置
            if (i != 0) cout << " ";  // 控制输出格式，避免多余空格
            cout << positionMap[key];
            continue;
        }

        // 计算初始散列位置
        int pos = key % p;
        int originalPos = pos;
        int step = 0;

        // 线性探测处理冲突
        while (hashTable[pos] != -1 && step < p) {
            step++;
            pos = (originalPos + step) % p;
        }

        // 记录该关键字的插入位置
        hashTable[pos] = key;
        positionMap[key] = pos;  // 保存该关键字的插入位置

        // 输出结果
        if (i != 0) cout << " ";  // 控制输出格式，避免多余空格
        cout << pos;
    }

    return 0;
}

代码说明：

unordered_map 记录位置：用 unordered_map<int, int> positionMap 来记录每个关键字第一次插入的位置。key 是关键字，value 是它第一次插入到散列表中的位置。
检查重复关键字：在处理每个关键字时，先检查它是否已经存在于 positionMap 中。如果存在，直接输出之前记录的插入位置；否则执行正常的插入逻辑，并记录该位置。
线性探测法处理冲突：只有在关键字第一次插入时，才会使用线性探测法来处理冲突。
输出格式控制：每次输出前通过检查，确保没有多余空格。

unordered_map 和 map 都是 C++ 标准库中的关联容器，它们都用于存储键值对，但它们的底层实现、性能以及使用场景有所不同

区别：

底层实现：
- map：基于 红黑树（自平衡二叉搜索树）实现，键值对存储在树的节点中。键值对是有序的，即键按升序排列。
- unordered_map：基于 哈希表 实现。键值对是无序的，即不按键的大小顺序排列，而是按哈希函数决定的位置存储。
访问和插入的时间复杂度：
- map：因为是基于平衡二叉树的实现，查找、插入和删除的时间复杂度是 O(log n)。
- unordered_map：因为是基于哈希表实现，查找、插入和删除的时间复杂度平均为 O(1)。但在极端情况下（哈希冲突较多），复杂度可能退化到 O(n)。
键的有序性：
- map：存储的键是有序的，适合需要按照键顺序进行操作的场景。
- unordered_map：键是无序的，适合不关心键的顺序，只关心快速查找和插入的场景。
内存使用：
- map：由于基于树的实现，内存开销较大，因为每个节点要额外存储指针来维护树结构。
- unordered_map：由于使用哈希表和可能的冲突处理机制（如开放寻址或链地址法），在需要扩展哈希表时内存使用量可能会增大。
更快的查找速度：unordered_map 的查找、插入和删除的时间复杂度平均为 O(1)，相比于 map 的 O(log n)，使用 unordered_map 可以显著提高性能，尤其是在关键字数量较多时（n 接近 1000）。
无需排序：我们不需要按顺序输出或访问插入的关键字，因此 unordered_map 提供了更好的性能，而不需要 map 的有序性功能。
map：当你需要按照键的顺序进行遍历、操作或者需要二分查找时，适合使用 map。例如，如果你需要按键的大小顺序输出数据，那么 map 会更合适。
unordered_map：当你只需要快速的查找、插入或删除操作，并不关心键的顺序时，unordered_map 会是更好的选择。由于题目要求的是重复关键字的存储与查找，这里用 unordered_map 能提供更快的性能。

码农公寓

输入格式:

输出格式:

输入样例:

输出样例:

代码说明：

区别：

相关文章