关于unordered_map

CPP

#include <bits/stdc++.h>
#define vt(x) vector <x>
#define it(x, n) x.begin() + 1, x.begin() + (n) + 1
#define int __int128
#define rep(i, s, t) for (int i = s; i <= t; i += 1)
#define func(type, para...) function <type(para)>
#define getchar getchar_unlocked
using namespace std;

#define isdight(x) ('0' <= (x) && (x) <= '9')
void read(int& x) {
	x = 0;
	bool p = 1;
	char c = 0;
	while (!isdight(c)) {
		c = getchar();
		if (c == '-')
			p = 0;
	}
	while (isdight(c)) {
		x = x * 10 + (c - '0');
		c = getchar();
	}
	x = p ? x : -x;
}
void print(int x, char d = ' ') {
	if (x < 0) {
		putchar('-');
		x = -x;
	}
	if (x > 9)
		print(x / 10, 0);
	putchar(x % 10 + '0');
	if (d != 0)
		putchar(d);
}
#undef isdight

#define Birth 20091225 // I love her forever
const int ansmod = (int)(1ULL << 32) * (int)(1ULL << 32);
signed main() {
	int n;
	read(n);
	struct Hash{
		int operator() (const int& x) const {
			return x;
		}
	};// 自定义哈希函数
	unordered_map <int, int, Hash> f;
	int ans = 0;
	rep(i, 1, n) {
		int x, y;
		read(x), read(y);
		ans = (ans + i * f[x]) % ansmod;
		f[x] = y;
	}
	print(ans, '\n');
	return 0;
}

关于这份代码，我的期望交上去是一片MLE的，但结果是60pts，最后几个点TLE了

我对 unordered_map 的底层实现不是很懂，我认为：
我这样的哈希函数，相当于直接开了一个

2^{64}

的数组，直接映射，应当一切操作都是严格

O(1)

的，但内存显然会爆

而结果并非如期望的那样

所以我好奇这个 unordered_map 是怎么样的实现方式。我问了AI，它说用桶+链表，我不是很理解这种实现

另外我问一下这个哈希函数有什么问题，为什么反而比上述的更慢了一点，我按照第一篇题解的思路，似乎没找到什么问题

CPP

struct Hash{
	int operator() (const int& x) const {
		return (x ^ Birth) % Birth;
	}
};

讨论操作

回复

相关推荐

关于unordered_map