Τι είναι ένας πίνακας κατακερματισμού και πώς επιτυγχάνει την αναζήτηση O(1);

Question

Accepted Answer

Ένας **πίνακας κατακερματισμού** (hash map) αποθηκεύει ζεύγη **key → value** και προσφέρει κατά μέσο όρο **O(1)** εισαγωγή, αναζήτηση και διαγραφή. Λειτουργεί περνώντας κάθε κλειδί μέσα από μια **συνάρτηση κατακερματισμού** που το αντιστοιχίζει σε ένα ευρετήριο σε έναν υποκείμενο πίνακα (ένα "κάδο").

## Πώς λειτουργεί

```text
key "cat" --hash()--> 3   buckets:
key "dog" --hash()--> 0     [0] -> ("dog", 5)
                            [1]
                            [2]
                            [3] -> ("cat", 9)
```

## Παράδειγμα

```python
phone = {}
phone['alice'] = 555_1234   # insert -> hash 'alice' to a bucket
num = phone['alice']        # lookup -> hash again, jump to bucket
del phone['alice']          # delete
'bob' in phone              # membership -> O(1) average
```

## Πολυπλοκότητα

| Λειτουργία | Μέσο όρο | Χείριστη περίπτωση |
|---|---|---|
| εισαγωγή | O(1) | O(n) |
| αναζήτηση | O(1) | O(n) |
| διαγραφή | O(1) | O(n) |

Η **χείριστη περίπτωση** O(n) συμβαίνει όταν πολλά κλειδιά συγκρούονται στον ίδιο κάδο.

## Ανταλλαγές

- **Δυνατότητες:** εξαιρετικά γρήγορη πρόσβαση βασισμένη σε κλειδί; ευέλικτα κλειδιά.
- **Αδυναμίες:** καμία ταξινόμηση των κλειδιών· επιπλέον μνήμη· O(n) χείριστη περίπτωση· χρειάζεται καλή συνάρτηση κατακερματισμού.

## Γιατί έχει σημασία

Οι πίνακες κατακερματισμού είναι ουσιαστικά η πιο χρησιμοποιούμενη δομή στην πράξη — βρίσκονται πίσω από λεξικά, σύνολα, κρυφή μνήμη, δείκτες βάσεων δεδομένων και απαλοιφή διπλοτύπων.

Η αντικατάσταση μιας γραμμικής σάρωσης με μια αναζήτηση κατακερματισμού είναι ένας από τους πιο συνηθισμένους τρόπους να μετατρέψετε έναν αλγόριθμο O(n²) σε O(n).

Λειτουργία	Μέσο όρο	Χείριστη περίπτωση
εισαγωγή	O(1)	O(n)
αναζήτηση	O(1)	O(n)
διαγραφή	O(1)	O(n)