Ένας νεαρός επιστήμονας υπολογιστών και οι συνεργάτες του απέδειξαν ότι η αναζήτηση σε δομές δεδομένων γνωστές ως hash tables μπορεί να είναι πολύ πιο γρήγορη από ό,τι πιστευόταν εδώ και δεκαετίες.
Μια ανακάλυψη από… περιέργεια
Το φθινόπωρο του 2021, ο Andrew Krapivin, προπτυχιακός φοιτητής στο Rutgers University, έπεσε πάνω σε μια επιστημονική εργασία που δεν του έκανε ιδιαίτερη εντύπωση. Όμως, δύο χρόνια αργότερα, όταν αποφάσισε να τη διαβάσει πιο προσεκτικά, ανακάλυψε κάτι που θα άλλαζε την κατανόηση μιας από τις πιο θεμελιώδεις δομές δεδομένων στην πληροφορική.
Η εργασία που διάβασε είχε τίτλο “Tiny Pointers” και αφορούσε μικροσκοπικούς δείκτες που κατευθύνουν σε συγκεκριμένα σημεία της μνήμης ενός υπολογιστή. Ο Krapivin βρήκε έναν τρόπο να τους μικρύνει ακόμα περισσότερο, εξοικονομώντας μνήμη. Ωστόσο, για να λειτουργήσει αυτή η τεχνική, χρειαζόταν μια νέα μέθοδο οργάνωσης των δεδομένων που αυτοί οι δείκτες θα χρησιμοποιούσαν. Έτσι, στράφηκε στα hash tables.
Κατά τη διάρκεια των πειραματισμών του, συνειδητοποίησε πως είχε ανακαλύψει έναν εντελώς νέο τύπο hash table, ικανό να εκτελεί αναζητήσεις με ταχύτητα που ξεπερνούσε κατά πολύ τις θεωρητικές προβλέψεις.
Μια αμφιλεγόμενη ανακάλυψη
Ο καθηγητής του, Martín Farach-Colton, συν-συγγραφέας της αρχικής εργασίας “Tiny Pointers”, ήταν επιφυλακτικός όταν ο Krapivin του παρουσίασε την ιδέα του. Τα hash tables είναι από τις πιο μελετημένες δομές δεδομένων στην πληροφορική και μια τέτοια ανακάλυψη φαινόταν απίθανη. Για να ελέγξει την εγκυρότητα των αποτελεσμάτων, ζήτησε τη γνώμη του William Kuszmaul, συνεργάτη του στο Carnegie Mellon University.
Η αντίδραση του Kuszmaul ήταν εντελώς διαφορετική: «Δεν βρήκες απλά ένα ενδιαφέρον hash table – ανέτρεψες μια 40χρονη εικασία!»
Η εικασία του Yao και η ανατροπή της
Το 1985, ο διάσημος επιστήμονας υπολογιστών Andrew Yao, μετέπειτα νικητής του βραβείου Turing, υποστήριξε ότι ο πιο αποδοτικός τρόπος αναζήτησης στοιχείων σε συγκεκριμένους τύπους hash tables απαιτούσε χρόνο ανάλογο του πόσο γεμάτος ήταν ο πίνακας. Με άλλα λόγια, όσο πιο γεμάτο ήταν το hash table, τόσο περισσότερα βήματα απαιτούνταν για να βρεθεί ένα ελεύθερο σημείο ή ένα συγκεκριμένο στοιχείο.
Για 40 χρόνια, η υπόθεση του Yao θεωρούνταν αληθινή. Όμως, ο Krapivin – χωρίς να γνωρίζει καν για την ύπαρξή της – ανακάλυψε μια νέα προσέγγιση που δεν βασιζόταν στην τυχαία αναζήτηση θέσεων (γνωστή ως uniform probing) και μπορούσε να εκτελεί αναζητήσεις πολύ ταχύτερα από όσο θεωρούνταν εφικτό.
Η νέα μέθοδος απαιτεί (log x)^2 βήματα, αντί για x, μια τεράστια βελτίωση όταν το hash table είναι σχεδόν γεμάτο. Οι Farach-Colton και Kuszmaul τον βοήθησαν να αποδείξει μαθηματικά ότι αυτό είναι το βέλτιστο δυνατό όριο, πράγμα που σημαίνει πως όχι μόνο η εικασία του Yao καταρρίφθηκε, αλλά βρέθηκε και η τελική απάντηση στο πρόβλημα.
Μια δεύτερη μεγάλη ανακάλυψη
Εκτός από την ανατροπή της εικασίας του Yao, η ομάδα του Krapivin έκανε μια ακόμα πιο εντυπωσιακή ανακάλυψη. Το 1985, ο Yao είχε δείξει ότι για συγκεκριμένες κατηγορίες hash tables, ο μέσος χρόνος αναζήτησης δεν μπορούσε να είναι μικρότερος από log x.
Οι Krapivin, Farach-Colton και Kuszmaul απέδειξαν ότι αυτό το όριο δεν ισχύει για όλα τα hash tables. Με έναν νέο σχεδιασμό, δημιούργησαν ένα hash table στο οποίο ο μέσος χρόνος αναζήτησης δεν εξαρτάται καθόλου από το πόσο γεμάτος είναι ο πίνακας – είναι πάντα σταθερός (constant time), κάτι που οι επιστήμονες δεν πίστευαν καν ότι ήταν δυνατό!
Πρακτικές επιπτώσεις
Αν και οι ανακαλύψεις αυτές μπορεί να μην έχουν άμεσες εφαρμογές, αλλάζουν ριζικά την κατανόησή μας για τις δομές δεδομένων. Όπως δήλωσε ο Alex Conway του Cornell Tech: «Είναι σημαντικό να κατανοούμε αυτές τις δομές καλύτερα. Δεν ξέρουμε πότε ένα τέτοιο αποτέλεσμα μπορεί να οδηγήσει σε πρακτικές βελτιώσεις».
Ο Krapivin, που πλέον είναι μεταπτυχιακός φοιτητής στο University of Cambridge, άλλαξε την πορεία της επιστήμης των υπολογιστών – και όλα ξεκίνησαν από μια τυχαία ιδέα, που γεννήθηκε από καθαρή περιέργεια.
Τι είναι τα hash tables
Τα hash tables (πίνακες κατακερματισμού) είναι μια από τις πιο σημαντικές δομές δεδομένων στην πληροφορική. Χρησιμοποιούνται για την αποθήκευση και την ανάκτηση δεδομένων με εξαιρετικά γρήγορο τρόπο, βασιζόμενα σε μια τεχνική που ονομάζεται κατακερματισμός (hashing).
Πώς λειτουργούν;
- Κατακερματισμός (Hashing): Κάθε στοιχείο που θέλουμε να αποθηκεύσουμε έχει ένα κλειδί (key). Ένας αλγόριθμος κατακερματισμού (hash function) μετατρέπει το κλειδί σε έναν αριθμό δείκτη (hash value), που καθορίζει σε ποια θέση του πίνακα θα αποθηκευτεί το στοιχείο.
- Αποθήκευση: Το στοιχείο τοποθετείται στη θέση που αντιστοιχεί στο hash value.
- Αναζήτηση: Όταν θέλουμε να βρούμε ένα στοιχείο, εφαρμόζουμε τον ίδιο hash function στο κλειδί του και μεταβαίνουμε κατευθείαν στη θέση του, αποφεύγοντας περιττές αναζητήσεις.
Πλεονεκτήματα:
Εξαιρετική ταχύτητα: Οι αναζητήσεις, οι εισαγωγές και οι διαγραφές γίνονται συνήθως σε χρόνο O(1), δηλαδή σταθερό χρόνο, ανεξάρτητα από το μέγεθος των δεδομένων.
Απλότητα και αποδοτικότητα: Χρησιμοποιούνται ευρέως σε βάσεις δεδομένων, cache memory, δικτυακές δομές και αλγορίθμους τεχνητής νοημοσύνης.
Προβλήματα:
Συγκρούσεις (Collisions): Εάν δύο διαφορετικά κλειδιά παράγουν τον ίδιο hash value, πρέπει να υπάρχει μια στρατηγική για να αποθηκευτούν σωστά (π.χ. αλυσίδωση, open addressing).
Μη προβλέψιμη σειρά: Τα δεδομένα δεν αποθηκεύονται με ταξινομημένο τρόπο, οπότε δεν είναι ιδανικά για περιπτώσεις όπου απαιτείται σειρά.
Χρήσεις: Από συστήματα caching (π.χ. DNS servers, databases) μέχρι αλγορίθμους ασφαλείας και κρυπτογραφία. Με τη νέα ανακάλυψη που ανέτρεψε την εικασία του Yao, οι hash tables μπορεί να γίνουν ακόμα πιο γρήγοροι και αποδοτικοί!
