c++ - 通过 local_it 遍历 bucket 时 unordered_multimap 中的碰撞

Question

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

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

我还 std::hash 每个键，一个在桶中，我发现“碰撞”中的键具有不同的哈希值。

因此，就好像碰撞正在发生，导致具有差异的值。同一个桶中的键，但矛盾的是，键散列到不同的值。他们是避免这种情况并根据存储桶中的键区分值的方法吗？还是我需要执行此操作？

#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;                                                                    
   }                                                                                          
 }     

Answer 1

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

您的问题的解决方案很简单，就是避免出现水桶。类 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;
}