通過local_it迭代桶時unordered_multimap中的衝突

Question

在下面的代碼中，我有一些字符串（DNA序列） ，我將其存儲在一個向量中。我有一個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; 
} 

Answer 2

因此，對於任何有興趣的人。我發現這個標準

[C++ 11：23.2.5/5]：兩個值k1和Key類型的K2是如果容器的key_equal功能對象時通過這些值返回真視爲等同。如果k1和k2是等價的，則散列函數將返回兩個相同的值。 [..]

[C++ 11：23.2.5/8]：無序關聯容器的元素被組織成桶。具有相同散列碼的密鑰出現在同一個存儲桶中。 [...]

因此，具有相同密鑰的兩個值總是會在同一個桶中結束，但具有不同值的密鑰也可能會在這些桶中結束。所以，我認爲實施可能更加智能化，並且實際上促進了這些情況;我能想到的一個原因是爲了保持桶的數量。你可以從輸出中看到填充的桶是稀疏的;而且我們越接近直接地址表（由散列索引的向量數組），我們最終將得到一個巨大的潛在關鍵字宇，其中有大量的空插槽，這些散列表可以防範。所以，這似乎是一個合理的空間優化。

因此，我選擇使用multimap來代替。 的原因是，multimap中的值是基於密鑰排序的，所以我可以通過基於密鑰對值進行分組。在unordered_multimap一旦我到達一個桶（在O（1），因爲它是一個散列表），沒有基於鍵的排序，所以我不能通過一個線性通過桶來組合序列。