通过 local_it 遍历存储桶时在 unordered_multimap 中发生冲突

Question

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

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

我还 std::hash 每个键，一个存储桶中的一个，我发现 "collisions" 中的键具有不同的哈希值。

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

#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

所以，对于任何感兴趣的人。我在标准

中找到了这个

[C++11: 23.2.5/5]：如果容器的 key_equal 函数对象 return 在传递这些值时为真，则 Key 类型的两个值 k1 和 k2 被认为是等价的.如果 k1 和 k2 相等，则哈希函数应 return 两者的相同值。 [..]

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

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

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

Answer 2

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

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

通过 local_it 遍历存储桶时在 unordered_multimap 中发生冲突

Collisions in unordered_multimap when iterating through bucket via local_it

c++

string

hash

unordered-map

unordered-multimap