Σύγκρουση (επιστήμη υπολογιστών)

Στην επιστήμη των υπολογιστών, σύγκρουση (αγγλικά: collision ή clash) είναι μια κατάσταση που παρουσιάζεται όταν δύο συμβολοσειρές (strings) έχουν την ίδια τιμή (hash value) κατακερματισμού, άθροισμα ελέγχου, ψηφιακό αποτύπωμα ή την κρυπτογραφική σύνοψη. Σε αυτή την περίπτωση οι τιμές ονομάζονται «συνώνυμες». Οι συμβολοσειρές μπορεί να είναι οσοδήποτε μικρές (π.χ. 1 byte) ή μεγάλες (π.χ. αρχείο πολλών GB) και ονομάζονται «κλειδιά». 

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

Για παράδειγμα η αντιστοίχιση ενός μικρού αριθμού ονομάτων (π.χ. λιγότερα από 20) σε κωδικούς του ενός byte (8bits), δηλαδή η απόδοση σε κάθε όνομα ενός κωδικού μεταξύ 0 και 255 με μηχανικό τρόπο (αυτόματα) και με την μικρότερη πιθανότητα οι κωδικοί δύο ή περισσοτέρων ονομάτων να συμπίπτουν (σύγκρουση ή collision). Φυσικά αν τα ονόματα ήταν περισσότερα από 256 η αντιστοίχιση αποτυγχάνει λόγω αναπόφευκτης σύγκρουσης.

Δείτε επίσης

Σημειώσεις

Παραπομπές 

Δομές δεδομένων