Πώς είναι δομημένη και οργανωμένη η δομή δεδομένων…

Το HashMap στη Java βασίζεται στις αρχές της κατακερματισμού. Αποθηκεύει ζεύγη "κλειδί-τιμή".

Εσωτερική δομή:

Πίνακες κάδων (δοχείων). Κάθε κάδος είναι μια συνδεδεμένη λίστα (ή δέντρο, από το Java 8 και μετά, όταν υπάρχουν πολλές συγκρούσεις).
Όταν προστίθεται ένα στοιχείο (put):
1. Υπολογίζεται ο κωδικός κατακερματισμού του κλειδιού (key.hashCode()).
2. Ο κωδικός κατακερματισμού τροποποιείται για καλύτερη κατανομή (hash).
3. Χρησιμοποιώντας τον τροποποιημένο κωδικό και το μέγεθος του πίνακα, υπολογίζεται η θέση του κάδου (hash & (array_size - 1)).
4. Το στοιχείο (ζεύγος "κλειδί-τιμή" ως αντικείμενο Node) τοποθετείται σε αυτόν τον κάδο. Αν ο κάδος ήδη περιέχει στοιχεία, το νέο στοιχείο προστίθεται στην αρχή της συνδεδεμένης λίστας ή του δέντρου.
5. Κατά την προσθήκη, ελέγχεται αν το κλειδί υπάρχει ήδη: χρησιμοποιείται η μέθοδος equals() για σύγκριση κλειδιών. Αν βρεθεί, η τιμή ενημερώνεται.
Όταν λαμβάνεται ένα στοιχείο (get):
1. Υπολογίζεται η θέση του κάδου με το κλειδί.
2. Στον κάδο, γίνεται αναζήτηση του στοιχείου με το κλειδί, χρησιμοποιώντας τις μεθόδους hashCode() και equals().
3. Επιστρέφεται η σχετική τιμή.

Οργάνωση:

Συγκρούσεις: Αν πολλά κλειδιά έχουν τον ίδιο κωδικό κατακερματισμού και πέφτουν στον ίδιο κάδο, αποθηκεύονται ως συνδεδεμένη λίστα. Από το Java 8 και μετά, αν ο αριθμός των στοιχείων σε έναν κάδο ξεπεράσει ένα όριο (συνήθως 8), η λίστα μετατρέπεται σε δέντρο για ταχύτερη αναζήτηση (O(log n) αντί για O(n)).
Αναπλήρωση μεγέθους: Όταν ο αριθμός των στοιχείων ξεπεράσει το όριο φόρτωσης (load factor * capacity), το HashMap αυξάνει το μέγεθος του εσωτερικού πίνακα και επανακατακερματίζει όλα τα στοιχεία. Αυτή η λειτουργία είναι ακριβή (O(n)).
Παράμετροι:
- capacity: Αρχικό μέγεθος του πίνακα (προεπιλογή 16).
- load factor: Όριο φόρτωσης (προεπιλογή 0.75). Ορίζει πότε θα γίνει αναπλήρωση.

Γιατί είναι σημαντικά τα hashCode() και equals():

Η σωστή λειτουργία του HashMap εξαρτάται από την σωστή υλοποίηση αυτών των μεθόδων.
Αν το equals() επιστρέφει true για δύο αντικείμενα, το hashCode() πρέπει να επιστρέφει την ίδια τιμή.
Λανθασμένη υλοποίηση μπορεί να οδηγήσει σε μη εύρεση στοιχείων (get θα επιστρέψει null), ακόμα και αν έχουν προστεθεί.

Παράδειγμα δομής Node:

// Μόνο εσωτερική χρήση
static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;

    Node(int hash, K key, V value, Node<K,V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }

    public final K getKey()        { return key; }
    public final V getValue()      { return value; }
    public final String toString() { return key + "=" + value; }

    public final int hashCode() {
        return Objects.hashCode(key) ^ Objects.hashCode(value);
    }

    public final V setValue(V newValue) {
        V oldValue = value;
        value = newValue;
        return oldValue;
    }

    public final boolean equals(Object o) {
        if (o == this)
            return true;
        if (o instanceof Map.Entry) {
            Map.Entry<?,?> e = (Map.Entry<?,?>)o;
            if (Objects.equals(key, e.getKey()) &&
                Objects.equals(value, e.getValue()))
                return true;
        }
        return false;
    }
}

Το HashMap παρέχει γρήγορη (μέσος όρος O(1)) προσθήκη, λήψη και διαγραφή στοιχείων με ομοιόμορφη κατανομή των hash. Στην χειρότερη περίπτωση (ισχυρές συγκρούσεις), η λειτουργία μπορεί να γίνει O(n) ή O(log n) με δέντρα.

Πώς είναι δομημένη και οργανωμένη η δομή δεδομένων HashMap στη Java;