我正在尝试解决算法任务：我需要使用哈希表创建MultiMap(键，(值))我不能使用Set和Map库。我把代码发送到测试系统，但我在测试20中得到了超过时间限制的错误。我不知道这个测试到底包含什么。代码必须执行以下任务：
put x y-add pair(x，y)。如果pair存在，则不执行任何操作。
delete x y-删除对(x，y)。若并没有配对，就什么也不做。
deleteall x-删除第一个元素x的所有对。
获取x-打印第一个元素x和第二个元素的对数。
操作量<=100000
时限-2s
示例：
multimap.in:
放置
放置b
放置一个c
获取
删除a b
获取
删除
获取
multimap.out:
3 b c a
2 c a
0
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
inline long long h1(const string& key) {
long long number = 0;
const int p = 31;
int pow = 1;
for(auto& x : key){
number += (x - 'a' + 1 ) * pow;
pow *= p;
}
return abs(number) % 1000003;
}
inline void Put(vector<vector<pair<string,string>>>& Hash_table,const long long& hash, const string& key, const string& value) {
int checker = 0;
for(int i = 0; i < Hash_table[hash].size();i++) {
if(Hash_table[hash][i].first == key && Hash_table[hash][i].second == value) {
checker = 1;
break;
}
}
if(checker == 0){
pair <string,string> key_value = make_pair(key,value);
Hash_table[hash].push_back(key_value);
}
}
inline void Delete(vector<vector<pair<string,string>>>& Hash_table,const long long& hash, const string& key, const string& value) {
for(int i = 0; i < Hash_table[hash].size();i++) {
if(Hash_table[hash][i].first == key && Hash_table[hash][i].second == value) {
Hash_table[hash].erase(Hash_table[hash].begin() + i);
break;
}
}
}
inline void Delete_All(vector<vector<pair<string,string>>>& Hash_table,const long long& hash,const string& key) {
for(int i = Hash_table[hash].size() - 1;i >= 0;i--){
if(Hash_table[hash][i].first == key){
Hash_table[hash].erase(Hash_table[hash].begin() + i);
}
}
}
inline string Get(const vector<vector<pair<string,string>>>& Hash_table,const long long& hash, const string& key) {
string result="";
int counter = 0;
for(int i = 0; i < Hash_table[hash].size();i++){
if(Hash_table[hash][i].first == key){
counter++;
result += Hash_table[hash][i].second + " ";
}
}
if(counter != 0)
return to_string(counter) + " " + result + "n";
else
return "0n";
}
int main() {
vector<vector<pair<string,string>>> Hash_table;
Hash_table.resize(1000003);
ifstream input("multimap.in");
ofstream output("multimap.out");
string command;
string key;
int k = 0;
string value;
while(true) {
input >> command;
if(input.eof())
break;
if(command == "put") {
input >> key;
long long hash = h1(key);
input >> value;
Put(Hash_table,hash,key,value);
}
if(command == "delete") {
input >> key;
input >> value;
long long hash = h1(key);
Delete(Hash_table,hash,key,value);
}
if(command == "get") {
input >> key;
long long hash = h1(key);
output << Get(Hash_table,hash,key);
}
if(command == "deleteall"){
input >> key;
long long hash = h1(key);
Delete_All(Hash_table,hash,key);
}
}
}
如何更快地完成代码工作？
首先，设计问题是：通常情况下，只将密钥传递给函数，并在其中计算哈希。您的变体允许用户在哈希表中的任何位置放置元素(使用错误的哈希值)，这样用户就可以很容易地破坏它
例如put:
using HashTable = std::vector<std::vector<std::pair<std::string, std::string>>>;
void put(HashTable& table, std::string& key, std::string const& value)
{
auto hash = h1(key);
// ...
}
如果有的话，散列函数可以被参数化，但你应该为写一个单独的类(包装向量的向量)，并在构造函数中提供散列函数，这样用户就不能随意交换它(并再次破坏散列表)。一个类会带来额外的好处，最重要的是：更好的封装(隐藏向量，这样用户就不能用向量自己的界面来更改它)：
class HashTable
{
public:
// IF you want to provide hash function:
template <typename Hash>
HashTable(Hash hash) : hash(hash) { }
void put(std::string const& key, std::string const& value);
void remove(std::string const& key, std::string const& value); //(delete is keyword!)
// ...
private:
std::vector<std::vector<std::pair<std::string, std::string>>> data;
// if hash function parametrized:
std::function<size_t(std::string)> hash; // #include <functional> for
};
我不能100%确定std::function的效率到底有多高，所以对于高性能代码，您最好直接使用哈希函数h1(而不是像上面所示那样实现构造函数)。
优化：
对于哈希键，我更喜欢无符号值：负索引毫无意义，为什么要允许它们呢？如果测试系统是一个32位系统(可能不太可能，但仍然…)，那么long-long(有符号或无符号)可能是一个糟糕的选择。size_t同时涵盖了这两个问题：它是无符号的，并且它的大小是为给定的系统选择的(如果对细节感兴趣：实际上是根据地址总线大小调整的，但在现代系统上，这也等于寄存器大小，这正是我们所需要的)。选择pow的类型以使其相同。
deleteAll的实现效率很低：当你擦除每个元素时，你会将所有后续元素向前移动一个位置。如果删除多个元素，则重复执行此操作，因此一个元素可以多次移动。更好：
auto pos = vector.begin();
for(auto& pair : vector)
{
if(pair.first != keyToDelete)
*pos++ = std::move(s); // move semantics: faster than copying!
}
vector.erase(pos, vector.end());
这将使每个元素最多移动一次，一次性擦除所有多余的元素。从最后的擦除开始(你必须明确地进行)，这或多或少也是算法库中的std::remove和std::remove_if所做的。你可以使用它吗？那么你的代码可能看起来像这样：
auto condition = [&keyToDelete](std::pair<std::string, std::string> const& p)
{ return p.first == keyToDelete; };
vector.erase(std::remove_if(vector.begin(), vector.end(), condition), vector.end());
并且您可以从已经高度优化的算法中获利。
这只是一个小的性能增益，但仍然：如果您只是在找到元素时返回，则可以在put中省去变量初始化、赋值和条件分支(后一个在某些系统上可能是相对昂贵的操作)：
//int checker = 0;
for(auto& pair : hashTable[hash]) // just a little more comfortable to write...
{
if(pair.first == key && pair.second == value)
return;
}
auto key_value = std::make_pair(key, value);
hashTable[hash].push_back(key_value);
再次，使用算法库：
auto key_value = std::make_pair(key, value);
// same condition as above!
if(std::find_if(vector.begin(), vector.end(), condition) == vector.end();
{
vector.push_back(key_value);
}
那么少于100000个操作并不意味着每个操作都需要一个单独的键/值对。我们可能会期望添加、删除、重新添加密钥。。。，所以你很可能不需要处理100000个不同的值。我认为你的地图太大了(请注意，它也需要初始化100000个矢量)。我认为一个小得多的应该已经足够了(可能是1009或10007？你可能需要做一点实验…)。
保持内部向量的排序可能也会给你带来一些性能提升：
put：您可以使用二进制搜索来查找要插入的新元素之间的两个元素(当然，如果这两个元素中的一个等于给定的一个，则不插入)delete：使用二进制搜索来查找要删除的元素deleteAll：查找要删除的元素的上下限，并一次擦除整个范围get：找到下限和上限对于deleteAll，元素之间的距离(元素数量)是一个简单的减法，你可以直接打印出文本(而不是首先构建一个长字符串)。然而，直接输出和创建字符串中哪一个更有效还有待研究，因为输出直接涉及多个系统调用，最终可能会再次损失先前获得的性能
考虑您的输入循环：
检查eof()(仅限)至关重要！如果文件中有错误，您将陷入一个无休止的循环，因为设置了失败位，operator>>实际上根本不会再读取任何内容，也永远不会到达文件的末尾。这甚至可能是你第20次考试失败的原因。
此外：您有基于行的输入(每个命令都在一个单独的行上)，因此一次读取整行并仅在之后解析它将省去一些系统调用。如果某个参数丢失，您将正确检测到它，而不是(非法)将下一个命令(例如put)读取为参数，同样，您也不会将多余的参数解释为下一个指令。如果一行由于任何原因(如上所述的参数数量不正确或命令未知)而无效，则可以单独决定要做什么(只需忽略该行或完全中止处理)。因此：
std::string line;
while(std::getline(std::cin, line))
{
// parse the string; if line is invalid, appropriate error handling
// (ignoring the line, exiting from loop, ...)
}
if(!std::cin.eof())
{
// some error occured, print error message!
}