题目

描述

对于存储由一对字符串键和整数值形成的元素的字典M, 执行下面给出的操作, 请注意, M中的每一个键必须是唯一的

(insert(key, x)): 插入一个由键和值组成的元素到M中

(get(key)): 输出一个指定的键对应的值, 如果没有那个元素则输出0

(delete(key)): 删除指定键对应的值

输入

输入以下列格式给出

(q)
(query_{1})
(query_{2})
(.)
(.)
(query_{n})

每一个(query_{i})都为:
(0) (key) (x)
或
(1) (key)
或
(2) (key)
其中第一个数字0, 1和2分别表示 insert, get, delete操作.

输出

对于每一个 get 操作, 在一行输出一个整数

限制条件

(1 leq q leq 200000)

(1 leq x leq 1000000000)

(1 leq) length of (key leq 20)

(key)全部由小写字母组成

样例输入

7
0 blue 4
0 red 1
0 white 5
1 red
1 blue
0 black 8
1 black

样例输出

求解

自己实现

分析

关于哈希表的经典练习题, 不做多的说明

设计

同上一次的设计流程, 不过新增了删除功能
针对本题可以直接修改, 如果com == 2, insert(key, 0); 直接将键对应的值修改为0就完了
不过为了通用以及清理出空间, 需要将被删除元素的键设置为一个特定值, 这个特定值在查找与删除中被认为是存在的一个元素, 只在添加元素中被认为是没有元素的, 不过添加元素时需要注意一点, 需要先判断有没有当前键对应的元素, 如果没有的话才可以将特定值视为空位. 否则可能会出现两个键对应不同值的情况.

编码

#include <iostream>
#include <string>
using namespace std;
#define MAX_Q 400005


struct Ele {
	string key;
	int value;
	Ele() {
		key = "";
		value = 0;
	}
	Ele(string str, int i) {
		key = str;
		value = i;
	}
};

Ele space[MAX_Q];

long get_key(string str) {
	long total = 0;
	for (int i = 0; i < str.length(); i++) {
		total = (total * 4 + str[i] - 'a' + 1) % 1000000007;
	}
	return total;
}

void insert(string key, int value) {
	int index = get_key(key) % MAX_Q;
	while (space[index].key != "" && space[index].key != key) {
		index = (index + 17541) % MAX_Q;
	}
	// 如果有的话直接更新
	if (space[index].key == key) {
		space[index].value = value;
		return;
	}
	// 没有的话再找空位进行插入
	index = get_key(key) % MAX_Q;
	while (space[index].key != "" && space[index].key != "{}") {
		index = (index + 17541) % MAX_Q;
	}
	Ele m(key, value);
	space[index] = m;
}

int search(string key) {
	int index = get_key(key) % MAX_Q;
	while (space[index].key != "" && space[index].key != key) {
		index = (index + 17541) % MAX_Q;
	}
	if (space[index].key == key) {
		return space[index].value;
	} else {
		return 0;
	}
} 

void remove(string key) {
	int index = get_key(key) % MAX_Q;
	while (space[index].key != "" && space[index].key != key) {
		index = (index + 17541) % MAX_Q;
	}
	if (space[index].key == key) {
		space[index].key = "{}";
	}
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);

	int q;
	cin >> q;
	int com, value;
	string key;
	while (q--) {
		cin >> com >> key;
		if (com == 0) {
			cin >> value;
			insert(key, value);
		} else if (com == 1) {
			cout << search(key) << endl;
		} else {
			remove(key);
		}
	}
}

结果

总结

额, 又错了好几次
第一次: 假如以1线性向后处理冲突, 两个键a, b都算出位置为0, a放入0号位置, b放入1号位置, 删除了a, 此时0号位置为特定值, 新增b元素时, 由于特定值在添加元素时视为空, 直接放入0号位置了, 之后删除b元素时, 只删除了0号位置的元素, get的时候会显示1号位置的元素, 导致出错, 在添加元素的时候, 先检查是否存在, 不存在再将特定值视为空添加新元素.
第二次: 在检查是否存在完了之后, 忘了将指针指回来...

STL

编码

#include <bits/stdc++.h>
using namespace std;

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);

	int q, com, x;
	string key;
	map<string, int> my_map;

	cin >> q;
	while (q--) {
		cin >> com >> key;
		if (com == 0) {
			cin >> x;
			my_map[key] = x;
		} else if(com == 1) {
			cout << my_map[key] << endl;
		} else {
			my_map[key] = 0;
		}
	}
}

结果

备注

无