Kollisionen in unordered_multimap beim Iterieren durch Bucket über local_it

Question

Im folgenden Code habe ich eine Reihe von Strings (DNA-Sequenzen) , die ich in einem Vektor speichern. Ich habe eine struct, read_tag, die ich verwende, um jede Zeichenfolge zu identifizieren; read_tag.read_id ist die Zeichenfolge-ID. Ich nehme 30 Zeichen Teilzeichenfolgen jeder Zeichenfolge und verwende sie als Schlüssel in einer unordered_multimap mit der read_tag als Wert; Ziel ist es, Strings zu gruppieren, die sich eine 30-stellige Sequenz teilen. Natürlich wird identische Zeichenfolge auf den gleichen Wert Hash und in demselben Bucket in der Multi-Map enden. Offset wird verwendet, um die "Verschiebung" vom Index Null des 30-Zeichen-Tags zu geben.

Allerdings, wenn ich diesen Code ausführen, durchlaufen jeden Bucket; Ich finde, dass es mehrere verschiedene Sequenzen in demselben Eimer gibt. Ich dachte, dass Kollisionen in unordered_mutlimap aufgelöst wurden, und deshalb sollten sie in einem Eimer nur ein Schlüssel (String) sein. Ich verstehe, dass Kollision passieren kann, aber ich dachte, dass entweder Verkettung, Sondierung usw. in unordered_mutlimap implementiert wurde. Sie sollten in der Lage sein, die Ausgabe auszuführen und zu überprüfen, um zu sehen, wo ich verwirrt bin.

Ich auch std::hash der jeder Schlüssel, einer in einem Eimer, und ich finde, dass die Schlüssel in den "Kollisionen" einen anderen Hash-Wert haben.

Also, es ist, als ob Kollisionen passieren, was zu Werten mit Diff führt. Schlüssel im selben Bucket, aber im Widerspruch, die Schlüssel zu verschiedenen Werten hashed. Ist es eine Möglichkeit, dies zu vermeiden und Werte basierend auf Schlüsseln innerhalb von Buckets zu unterscheiden? Oder muss ich das umsetzen?

#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

Ja, Sie haben Recht. Es ist nicht garantiert, dass zwei verschiedene Gegenstände in zwei verschiedenen Eimern landen. Sie wissen nur, dass zwei gleiche Gegenstände in demselben Eimer landen.

Die Lösung für Ihr Problem besteht einfach darin, Eimer zu vermeiden.Die Klasse unordered_multimap (sowie multimap) hat die Methode equal_range, die Ihnen den Bereich der Elemente mit einem bestimmten Schlüssel angibt. Sie müssen also nur über alle Schlüssel iterieren und equal_range verwenden, um alle Werte zu durchlaufen. Leider gibt es keine Methode, mit der Sie über die Tasten iterieren können, also müssen Sie ein wenig knifflig sein. Der folgende Code sollte Ihnen die gewünschte Ausgabe geben:

Answer 2

Also, für jeden, der interessiert war. Ich fand dies im Standard

[C++ 11: 23.2.5/5]: Zwei Werte k1 und k2 vom Typ Schlüssel werden als gleichwertig betrachtet, wenn das key_equal-Funktionsobjekt des Containers true zurückgibt, wenn diese Werte übergeben werden. Wenn k1 und k2 gleichwertig sind, soll die Hash-Funktion für beide den gleichen Wert liefern. [..]

[C++ 11: 23.2.5/8]: Die Elemente eines ungeordneten assoziativen Containers sind in Buckets organisiert. Schlüssel mit demselben Hash-Code erscheinen im selben Bucket. [..]

Also werden zwei Werte mit demselben Schlüssel immer in demselben Bucket enden, aber auch Schlüssel mit anderen Werten könnten in diesen Buckets landen. Ich nehme an, dass die Implementierung intelligenter ist und diese Situationen tatsächlich fördert. Ein Grund, warum ich daran denken könnte, die Anzahl der Eimer niedrig zu halten. Sie können anhand der Ausgabe sehen, dass die befüllten Buckets spärlich sind. und je näher wir den direkten Adresstabellen kommen (Array von Vektoren, indiziert durch den Hash), werden wir mit einem riesigen Universum von potenziellen Schlüsseln enden, mit einer riesigen Anzahl von leeren Slots, gegen die Hash-Tabellen schützen. Es scheint also eine vernünftige Raumoptimierung zu sein.

Aus diesem Grund habe ich stattdessen multimap verwendet. Die Gründe sind, dass die Werte in multimap basierend auf Schlüssel sortiert sind, so dass ich einen einzigen Durchgang durch Gruppierung von Werten basierend auf Schlüsseln durchführen kann. In unordered_multimap sobald ich einen Eimer (in O (1), weil es eine Hash-Tabelle ist) gibt es keine Taste basierend Reihenfolge, so kann ich nicht einen linearen Durchlauf durch den Eimer, um Sequenzen zu gruppieren.