Μπορεί ένα hash να ταιριάζει για διαφορετικά κλειδιά;

Ναι, η συνάρτηση κατακερματισμού για διαφορετικά κλειδιά μπορεί να συμπέσει — αυτό ονομάζεται σύγκρουση. Η σύγκρουση συμβαίνει επειδή η συνάρτηση κατακερματισμού απεικονίζει ένα μεγάλο σύνολο πιθανών κλειδιών σε ένα περιορισμένο σύνολο τιμών κατακερματισμού.

Για παράδειγμα, αν η συνάρτηση κατακερματισμού επιστρέφει έναν αριθμό 32-bit, τότε υπάρχουν περίπου 4 δισεκατομμύρια πιθανές τιμές, αλλά τα κλειδιά μπορεί να είναι πολύ περισσότερα.

Οι συγκρούσεις είναι ένα φυσιολογικό φαινόμενο, και οι αλγόριθμοι κατακερματισμού και οι δομές δεδομένων (όπως οι πίνακες κατακερματισμού) περιλαμβάνουν μεθόδους για τη διαχείρισή τους:

• αλυσίδες (chaining) — αποθήκευση όλων των στοιχείων με το ίδιο hash σε μια λίστα;
• ανοιχτή διεύθυνση — αναζήτηση του επόμενου ελεύθερου κελιού;
• διπλό κατακερματισμό και άλλες μέθοδοι.

Είναι σημαντικό να επιλέξετε μια καλή συνάρτηση κατακερματισμού που ελαχιστοποιεί τον αριθμό των συγκρούσεων για να διασφαλίσει υψηλή απόδοση.