哈希映射实现问题 [英] Hash map implementation problem

问题描述

我的问题是找到一个好的实现，一旦在哈希键中转换了字符串，就可以这样做，如果我在开始时这样做：

第1组：string12，string21

第2组：string364 string128

之后我这样做：

移动string128 string21

结果将是：

第1组：string12，string21，string128

第2组：string364

我知道，没有什么比这更复杂但我的实现仍然很慢，它应该更快。

我正在使用向量< vector< int>>，其中我保存了hash_key。

我应该使用什么？（我可以''使用c ++ 11的unordered_map！）

我必须在地图中保存哈希键吗？在向量中？或者我必须使用矢量< vector>或矢量< map> ???我很困惑，我希望有人可以帮助我，因为它对我来说非常重要。

My problem is to find a good implementation that will allow me, once transformed strings in hash keys, to do, if I had at the beginning this:
Group 1: string12, string21
Group 2: string364 string128
and after i do this:
move string128 string21
the result will be:
Group 1: string12, string21, string128
Group 2: string364
I know, nothing so complicated but my implementation is still slow, it should be faster.
I''m using a vector<vector<int>>, where i save the hash_key.
What should i use?(i can''t use unordered_map of c++11!)
I have to save the hash keys in a map?in a vector? or i have to use a vector<vector> or vector<map>??? I''m confused and I hope someone can help me because it''s very important for me.

推荐答案

如果您的哈希键在向量< vector< int> ;那么你需要迭代向量来找到向量< int>对于您正在查找的哈希键。


您是否尝试过地图< pair< int，vector< int> >？


您应该能够快速查找密钥，然后迭代向量< int>获取所有散列到键值的字符串。

If your hash keys are in vector<vector<int> then you need t iterate the vector to find the vector<int> for the hash key you are looking up.

Have you tried a map<pair <int, vector<int> >?

You should be able to quickly look up the key and then iterate vector<int> to fetch up all the strings that hashed to the key value.

我没有很好地解释这个问题，因为我也可以这样：


组1：string12，string21，string128

组2：string364

和我这样做之后：

移动string128 string364

结果将是：

第1组：string12，string21

第2组：string364 string128

所以我必须迭代搜索键的所有向量??

I have not explained the problem well because i can have also this case:

Group 1: string12, string21, string128
Group 2: string364
and after i do this:
move string128 string364
the result will be:
Group 1: string12, string21
Group 2: string364 string128
So i have to iterate over all vectors to search for the key??

想法是使用链式表。一种实现是数组和链表。在这种情况下，让我们假设您的哈希值介于0和1000之间。您创建一个数组，其中元素索引是哈希值。然后当你哈希到275时，你会转到数组的元素275，并且有一个链接列表的地址是所有项目的哈希值为275.然后你迭代链表找到你想要的那个。 />

我的建议是使用地图<>而不是数组并使用向量<> （或者可能是列表<>）用于链接列表。


在我的建议中，当你哈希到275时，你在地图中找到了对<>然后迭代向量<>在那对<> ;.您只需要迭代这一个向量<>。取决于地图中的键数<>和散列算法的效率，这个向量<>可能只有很少的元素。


C ++有新的哈希模板可能会对你有帮助。

The idea is to use a chain-link table. One implementation is an array and a linked list. In this scenario let''s assume your hash vales are between 0 and 1000. You create an array where the element index is the hash value. Then when you hash to, say,275 you go to element 275 of the array and there is the address of a linked list of all items that have hashed to 275. Then you iterate the linked list to find the one you want.

My suggestion was to use a map<> instead of an array and to use a vector<> (or perhaps a list<>) for the linked list.

In my suggestion when you hash to 275 you locate the pair in the map<> and then iterate the vector<> in that pair<>. You would need to iterate only this one vector<>. Depending upon how many keys are in the map<> and the efficiency of your hash algorithm, this vector<> may have very few elements.

There are new hash templates for C++ that might help you.

这篇关于哈希映射实现问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！