Δύο διαφορετικοί κλειδιά μπορούν να κατακερματιστούν στον ίδιο κάδο — μια σύγκρουση. Οι πίνακες κατακερματισμού παραμένουν O(1) κατά μέσο όρο επιλύοντας συγκρούσεις και αλλάζοντας το μέγεθος πριν οι κάδοι γεμίσουν, ελεγχόμενο από τον συντελεστή φορτίου.
Separate chaining: each bucket holds a list
[3] -> ("cat",9) -> ("rat",2) # both hashed to 3
Open addressing: probe to the next free slot
hash=3 taken -> try 4 -> try 5 ... (linear probing)
load factor α = number_of_entries / number_of_buckets
α rises -> more collisions -> slower lookups
When α exceeds a threshold (e.g. 0.75):
-> allocate a bigger array (usually 2x)
-> REHASH every existing key into new buckets
# Conceptual resize
def _resize(self):
old = self.buckets
self.buckets = [None] * (len(old) * 2)
for entry in all_entries(old):
self._insert(entry.key, entry.value) # rehash into new array
| Λειτουργία | Μέσος όρος | Χείριστη |
|---|---|---|
| αναζήτηση / εισαγωγή / διαγραφή | O(1) | O(n) |
| μεμονωμένη αλλαγή μεγέθους | — | O(n) |
| εισαγωγή (αποσβεσμένη, με αλλαγή μεγέθους) | O(1) | — |
Μια αλλαγή μεγέθους είναι O(n) αλλά συμβαίνει σπάνια, οπότε αποσβένεται σε O(1) ανά εισαγωγή.
Αυτές οι εσωτερικές λεπτομέρειες εξηγούν γιατί οι χάρτες κατακερματισμού είναι γρήγοροι κατά μέσο όρο αλλά μπορούν να αυξηθούν σε O(n) — κρίσιμο για κώδικα ευαίσθητο σε απόδοση και άμυνα κατά των έχθρικών εισόδων (hash-flooding).
Η κατανόηση του συντελεστή φορτίου εξηγώνει επίσης τα κουμπιά ρύθμισης μνήμης/ταχύτητας που εκτίθενται από πραγματικές βιβλιοθήκες.