1

在下面的代码中，我有一些字符串（DNA 序列）存储在一个向量中。我有一个struct,read_tag用来识别每个字符串；read_tag.read_id是字符串标识符。我取每个字符串的 30 个字符子字符串，并将其用作 an 中的键， unordered_multimap并将 theread_tag用作值；目的是对共享 30 个字符序列的字符串进行分组。自然地，相同的字符串将散列到相同的值，并最终在多映射中的同一个桶中。偏移量用于给出从 30 个字符标签的索引零开始的“移位”。

但是，当我运行此代码时，会遍历每个存储桶；我发现同一个桶中有多个不同的序列。我认为冲突已解决unordered_mutlimap，因此在存储桶中，它们应该只是一个键（字符串）。我知道可能会发生碰撞，但我认为链接、探测等都是在unordered_mutlimap. 您应该能够运行并检查输出以查看我在哪里感到困惑。

我也是std::hash每个键，一个桶中的一个，我发现“冲突”中的键具有不同的哈希值。

因此，就好像发生了冲突，导致值具有差异。同一桶中的密钥，但相反，密钥散列到不同的 val。他们是避免这种情况的一种方法，并根据桶中的键区分值吗？还是我需要执行此操作？

#include <iostream>                                                                                   
#include <string>                                                                                     
#include <unordered_map>                                                                              
#include <vector>                                                                                     
#include <functional>                                                                                 

using namespace std;                                                                                  


int main() {                                                                                          


  vector<string>  reads;                                                                              

  reads.push_back("CCAGCTGCTCTCACCCTGGGCAGGGTCCCTGCACACACTGTATCTTTTGAGGTCCCTTCAGGACCCCGGTTTGCTGCCTC");
  reads.push_back("CCAGCTGCTCTCACCCTGGGCAGGGTCCCTGCACACACTGTATCTTTTGAGGTCCCTTCAGGACCCCGGTTTGCTGCCTC");
  reads.push_back("GGCAGGGTCATACCCGATTAACTTGTTATAGAGTATGGGGCATCAACTTGGGCAGCAATGGGGAACGGTGTCTCTGGAAG");
  reads.push_back("CCAGCTGCTCTCACCCTGGGCAGGGTCCCTGCACACACTGTATCTTTTGAGGTCCCTTCAGGACCCCGGTTTGCTGCCTC");
  reads.push_back("GGCAGGGTCATACCCGATTAACTTGTTATAGAGTATGGGGCATCAACTTGGGCAGCAATGGGGAACGGTGTCTCTGGAAG");
  reads.push_back("GGCAGGGTCATACCCGATTAACTTGTTATAGAGTATGGGGCATCAACTTGGGCAGCAATGGGGAACGGTGTCTCTGGAAG");
  reads.push_back("GGCAGGGTCATACCCGATTAACTTGTTATAGAGTATGGGGCATCAACTTGGGCAGCAATGGGGAACGGTGTCTCTGGAAG");
  reads.push_back("CCGGGCGTGGTGGCGTGCACCTGTAATCCCAGCTACTTGGGATGTTCAGGCAGGAGACTCGCTTGATCCCCGGGGACGGA");
  reads.push_back("CCGGGCGTGGTGGCGTGCACCTGTAATCCCAGCTACTTGGGATGTTCAGGCAGGAGACTCGCTTGATCCCCGGGGACGGA");
  reads.push_back("CCGGGCGTGGTGGCGTGCACCTGTAATCCCAGCTACTTGGGATGTTCAGGCAGGAGACTCGCTTGATCCCCGGGGACGGA");
  reads.push_back("CCGGGCGTGGTGGCGTGCACCTGTAATCCCAGCTACTTGGGATGTTCAGGCAGGAGACTCGCTTGATCCCCGGGGACGGA");
  reads.push_back("CCAGCTGCTCTCACCCTGGGCAGGGTCCCTGCACACACTGTATCTTTTGAGGTCCCTTCAGGACCCCGGTTTGCTGCCTC");

  struct read_tag{                                                                                    
    unsigned int read_id;    // unique string identifier                                                                          
    int offset;              // shift of 30 character substring represented by tag                                                                                                                                            
  };                                                                                                  

  unordered_multimap<string, read_tag> mutation_grouper;                                              

  for(int read_id=0; read_id < reads.size(); read_id++) {                                             
    string read = reads[read_id];                                                                                              
    for(int i=0; i < read.size()-30; i++) {                                                                                                                            
      string sub_read = read.substr(i, 30);                                                           
      read_tag next_tag;                                                                              
      pair<string, read_tag> key_val;                                                                 

      next_tag.read_id = read_id;                                                                     
      next_tag.offset = i;                                                                                                                                             

      key_val.first = sub_read;                                                                       
      key_val.second = next_tag;                                                                      

      mutation_grouper.insert(key_val);                                                               
    }                                                                                                 
  }                                                                                                   

  cout << "mutation_grouper buckets" << endl;                                                         
  std::hash<std::string> hash_er;                                                                     

  for(unsigned int bucket = 0;  bucket < mutation_grouper.bucket_count(); bucket++) {

    cout << "Bucket: " << bucket << endl;                                                    
    for( auto local_it = mutation_grouper.begin(bucket);                                     
     local_it != mutation_grouper.end(bucket); ++local_it) {                             

      cout << local_it->first << " : " << local_it->second.read_id                           
      << ", " << local_it->second.offset << ", " << endl;                                               

      cout << "hash value: " << local_it->first <<"::: " << hash_er(local_it->first) << endl;

     }                                                                                        
     cout << endl << endl;                                                                    
   }                                                                                          
 }
4

2 回答 2

2

是的，你是对的。不能保证两个不同的项目落在两个不同的桶中。您只知道，两个相同的物品落在同一个桶中。

解决您的问题的方法就是避免使用水桶。类unordered_multimap（以及multimap）具有方法equal_range，它为您提供具有特定键的元素范围。因此，您只需要遍历所有键，并使用equal_range来遍历所有值。可悲的是，没有方法可以让您遍历键，因此您必须有点棘手。以下代码应为您提供所需的输出：

// iterate through all elements in the multimap
// don't worry, we'll skip a bunch
for (auto it = mutation_grouper.begin(); it != mutation_grouper.end(); )
{
    // Get the range of the current key
    auto range = mutation_grouper.equal_range(it->first);

    // Print all elements of the range
    cout << it->first << endl;
    for (auto local_it = range.first; local_it != range.second; ++local_it)
        std::cout << "   " << local_it->second.read_id << " " << local_it->second.offset << '\n';

    // Step to the end of the range
    it = range.second;
}
于 2016-07-23T10:02:38.733 回答
0

所以，对于任何有兴趣的人。我在标准中找到了这个

[C++11: 23.2.5/5]：如果容器的 key_equal 函数对象在传递这些值时返回 true，则认为 Key 类型的两个值 k1 和 k2 是等效的。如果 k1 和 k2 相等，则散列函数应为两者返回相同的值。[..]

[C++11: 23.2.5/8]：无序关联容器的元素被组织成桶。具有相同哈希码的键出现在同一个桶中。[..]

因此，具有相同键的两个值将始终位于同一个桶中，但具有不同值的键也可能最终位于这些桶中。所以，我认为实现可能更智能，并且实际上促进了这些情况；我可以想到减少存储桶数量的原因之一。您可以从输出中看到填充的桶是稀疏的；我们越接近直接地址表（向量数组，由哈希索引），我们最终会得到一个巨大的潜在键域，以及大量的空槽，哈希表可以防止这些空槽。因此，这似乎是一个合理的空间优化。

因此，我选择使用multimap。原因是，值multimap是基于键排序的，所以我可以通过基于键的分组值进行单次传递。一旦我到达一个桶（在unordered_multimapO(1) 中，因为它是一个哈希表），就没有基于键的排序，所以我不能通过桶进行线性传递来对序列进行分组。

于 2016-07-23T09:36:01.710 回答