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

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

Στο σχήμα απεικονίζονται τέσσερις συμβολοσειρές - κλειδιά (Keys) στις οποίες με την χρήση συνάρτησης κατακερματισμού (hash function) αποδίδονται τιμές (hashes). Η συνάρτηση κατακερματισμού μας αποδίδει τιμές μεγέθους 4-bit και γιαυτό είναι από 00 έως 15 (δηλαδή, πλήθος τιμών 24=16). Στα κλειδιά «John Smith» και «Sandra Dee» έχουμε απόδοση της ίδιας τιμής, οπότε λέμε ότι έχουμε σύγκρουση (collision).
Στο σχήμα απεικονίζονται τέσσερις συμβολοσειρές - κλειδιά (Keys) στις οποίες με την χρήση συνάρτησης κατακερματισμού (hash function) αποδίδονται τιμές (hashes).
Η συνάρτηση κατακερματισμού μας αποδίδει τιμές μεγέθους 4-bit και γιαυτό είναι από 00 έως 15 (δηλαδή, πλήθος τιμών 24=16).
Στα κλειδιά «John Smith» και «Sandra Dee» έχουμε απόδοση της ίδιας τιμής, οπότε λέμε ότι έχουμε σύγκρουση (collision).

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

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

Δείτε επίσης

[Επεξεργασία | επεξεργασία κώδικα]

Σημειώσεις

[Επεξεργασία | επεξεργασία κώδικα]

Παραπομπές

[Επεξεργασία | επεξεργασία κώδικα]
  1. ↑ Σάββας, Κ. Ηλίας, (Λάρισα, Ιανουάριος 2005). «Αλγόριθμοι και Στοιχεία Πολυπλοκότητας. Ενότητα 11: Κατακερματισμός» από Ανώτατο Εκπαιδευτικό Ίδρυμα Θεσσαλίας, σελ. 104. Αρχειοθετήθηκε 09/03/2016. Ανακτήθηκε 12/01/2019.
  2. ↑ «ΣΗΜΕΙΩΣΕΙΣ. Εισαγωγή στη γλώσσα C++» από Δ.Ι.Ε.Κ. Μεταξουργείου, Αθήνα 2018. Αρχειοθετήθηκε 12/01/2019. Ανακτήθηκε 12/01/2019.
  3. ↑ (Αγγλικά) «Hashing - What is Collision?» από geeksforgeeks.org. Αρχειοθετήθηκε 09/12/2017. Ανακτήθηκε 12/01/2019.
  4. ↑ (Αγγλικά) «This is referred to as a collision (it may also be called a “clash”)». 5.5. Hashing από interactivepython.org. Αρχειοθετήθηκε 06/11/2018. Ανακτήθηκε 12/01/2019.
  5. ↑ Διομήδης Σπινέλλης. «Γλώσσες προγραμματισμού και δομές δεδομένων - Κατακερματισμός» από aueb.gr. Αρχειοθετήθηκε 08/08/2016. Ανακτήθηκε 11/01/2019.
  6. ↑ Τόλλης, Γ. Ιωάννης «Δομές Δεδομένων» από opencourses.uoc.gr, σελ. 6. Ανακτήθηκε 12/01/2019.