Mi történik ütközés esetén, amikor kulcsot szerezünk egy C++-ban lévő konténerhez?

Amikor ütközés történik egy C++-ban (például std::unordered_map, std::unordered_set) asszociatív tárolókban a kulcs megszerzésekor, a következő történik:

1. A kulcs hash értékét számítják ki.
2. A hash alapján meghatározzák a "korsó" (bucket) számát, ahová az elem potenciálisan kerül.
3. Ha ebben a korsóban már vannak azonos hash értékű elemek (azaz ütközés történt), akkor a tároló elkezdi végignézni a korsóban lévő elemeket.
4. Minden elem esetében összehasonlítja a keresett elem kulcsát az aktuális elem kulcsával az egyenlőség operátor (operator==) segítségével.
5. Ha az összehasonlítás eredménye pozitív, megtalálta a keresett elemet.
6. Ha az összes elem végignézése után sem talál egyezést, akkor az adott kulcsú elem hiányzik a tárolóból.

Különböző ütközéskezelési stratégiák léteznek:

• Láncolási módszer (Separate Chaining): Minden korsóban egy lista (például egys linked list) tárolja az azonos hash értékű elemeket. Ütközés esetén az új elemet hozzáadják ehhez a listához.

  // Egy egyszerű láncolási módszer vázlatos példája
  struct Node {
      Key key;
      Value value;
      Node* next;
  };
  
  struct Bucket {
      Node* head = nullptr; // A korsóban lévő elemek listája
  };
  
  Bucket buckets[NUM_BUCKETS];
  
  // Ütés/keresés esetén
  // A listát végignézzük: head -> node1 -> node2 -> ...
  

• Nyitott címzéses módszer (Open Addressing): Minden elem közvetlenül a hash táblában tárolódik. Ütközés esetén a következő szabad helyet keresi a meghatározott stratégia szerint:
  • Lineáris zárójel (Linear Probing): Ellenőrzi a következő cellákat (+1, +2, +3 ... az eredeti indextől)

    // Egy egyszerű lineáris zárójel vázlatos példája
    struct Slot {
        Key key;
        Value value;
        bool occupied = false;
        bool deleted = false; // A törlés utáni helyes kereséshez
    };
    
    Slot table[TABLE_SIZE];
    
    // Beillesztés/keresés esetén, ha table[hash] foglalt
    // Ellenőrizzük a table[(hash + 1) % TABLE_SIZE], table[(hash + 2) % TABLE_SIZE], ...
    

  • Kvadratikus zárójel (Quadratic Probing): A cellák kvadratikus eltolással ellenőrződnek (+1², +2², +3² ... az eredeti indextől)
  • Kettős hash-elés (Double Hashing): A második hash függvény határozza meg a zárójel lépését.

A C++ szabványos tárolói (std::unordered_map, std::unordered_set) általában a láncolási módszert valósítják meg. Nagy ütközésszám esetén a műveletek (keresés, beszúrás, törlés) hatékonysága romolhat, közelítve a lineáris függést a legrosszabb esetben a "töltött" korsóban lévő elemek számától, de átlagosan közel áll a konstanshoz jó hash függvény esetén.