Πώς λειτουργεί το Map στο Go;

Ο χάρτης σε Go υλοποιείται ως πίνακας κατακερματισμού.

Τα βασικά στοιχεία της δομής map:

• Λειτουργία κατακερματισμού: Χαρτογραφεί τα κλειδιά σε τιμές κατακερματισμού (ακέραιοι αριθμοί).
• Πίνακας κάδων (buckets): Συλλογή από λίστες ή πίνακες όπου αποθηκεύονται τα ζεύγη κλειδιού-τιμής. Ο δείκτης του κάδου καθορίζεται από την τιμή κατακερματισμού του κλειδιού.
• Διαχείριση συγκρούσεων: Όταν διαφορετικά κλειδιά έχουν τον ίδιο κατακερματισμό (σύγκρουση), τα στοιχεία με αυτά τα κλειδιά αποθηκεύονται στον ίδιο κάδο, συνήθως με μορφή συνδεδεμένης λίστας ή κάδου υπερχείλισης.
• Παράγοντας φόρτωσης: Αναλογία μεταξύ του αριθμού των στοιχείων και του αριθμού των κάδων. Όταν ξεπεραστεί ένα όριο, πραγματοποιείται επανακατακερματισμός: δημιουργείται ένας νέος μεγαλύτερος πίνακας κάδων και μετακινούνται όλα τα στοιχεία από τους παλιούς κάδους στους νέους.

Η δομή map σε Go αντιπροσωπεύεται από τον τύπο hmap:

 type hmap struct {
    count     int // Αριθμός στοιχείων
    flags     uint8 // Σημαίες κατάστασης
    B         uint8 // log_2 του αριθμού των κάδων (αριθμός κάδων είναι 2^B)
    noverflow uint16 // Αριθμός κάδων με υπερχείλιση (μόνο για στατιστικά)
    hash0     uint32 // Αρχική τιμή της λειτουργίας κατακερματισμού

    buckets    unsafe.Pointer // Δείκτης στον πίνακα κάδων (κύριοι και υπερχείλισης)
    oldbuckets unsafe.Pointer // Δείκτης στον παλιό πίνακα κάδων κατά τη διάρκεια μετανάστευσης
    nevacuate  uintptr // Δείχνει μέχρι ποιον παλιό κάδο έχει ολοκληρωθεί η μετανάστευση

    extra *mapextra // Επιπλέον πληροφορίες (προαιρετικό)
}

 type mapextra struct {
    overflow    *[2]*[]*bmap // Δείκτες σε πίνακες υπερχείλισης
    oldoverflow *[2]*[]*bmap // Δείκτες σε παλιούς πίνακες υπερχείλισης
    nextOverflow *bmap // Επόμενος ελεύθερος κάδος υπερχείλισης
}

 type bmap struct {
    tophash [8]uint8 // Top hash (ανώτερα bits του hash) για επιτάχυνση της αναζήτησης στον κάδο
    // Ακολουθούν κλειδιά, τιμές και δείκτες στον επόμενο bmap (αν ο κάδος είναι υπερχείλισης)
    // Διανείμετε όλα τα δεδομένα για το hmap.buckets σε ένα ενιαίο malloc μπλοκ
    // δείτε ../../runtime/map.go για λεπτομέρειες
}

Ενέργειες:

• Εισαγωγή/Ενημέρωση: Υπολογίζεται το hash του κλειδιού, καθορίζεται ο κάδος. Αν το κλειδί ήδη υπάρχει, ενημερώνεται η τιμή. Αλλιώς, το ζεύγος κλειδιού-τιμής προστίθεται στον κάδο. Σε περίπτωση υπερχείλισης ή υπέρβασης του Load Factor, μπορεί να πραγματοποιηθεί rehashing.
• Αναζήτηση: Υπολογίζεται το hash του κλειδιού, καθορίζεται ο κάδος. Τα στοιχεία στον κάδο ελέγχονται με βάση το top-hash, και στη συνέχεια συγκρίνονται τα πλήρη κλειδιά. Επιστρέφεται η τιμή και ένα flag ύπαρξης.
• Διαγραφή: Υπολογίζεται το hash του κλειδιού, καθορίζεται ο κάδος. Το στοιχείο σημαίνεται ως διαγραμμένο (αλλά δεν διαγράφεται άμεσα από τη μνήμη). Η διαγραφή πραγματοποιείται σε μελλοντικές ενέργειες ή κατά το rehashing.

Ο χάρτης σε Go δεν είναι συγχρονισμένος και δεν μπορεί να χρησιμοποιηθεί με ασφάλεια από πολλαπλές goroutines χωρίς εξωτερικό συγχρονισμό.