Πώς να εφαρμόσετε έναν απλό πίνακα κατακερματισμού σε JavaScript

Πόσο όμορφο είναι {};

Σας επιτρέπει να αποθηκεύετε τιμές ανά κλειδί και να τις ανακτάτε με πολύ αποδοτικό τρόπο ( O(1), περισσότερα σε αυτό αργότερα).

Σε αυτήν την ανάρτηση θέλω να εφαρμόσω έναν πολύ βασικό πίνακα κατακερματισμού και να ρίξω μια ματιά στις εσωτερικές λειτουργίες του για να εξηγήσω μια από τις πιο έξυπνες ιδέες στην επιστήμη των υπολογιστών.

Το πρόβλημα

Φανταστείτε ότι δημιουργείτε μια νέα γλώσσα προγραμματισμού: ξεκινάτε έχοντας αρκετά απλούς τύπους (συμβολοσειρές, ακέραιοι αριθμοί, πλωτήρες,…) και μετά προχωράτε στην εφαρμογή πολύ βασικών δομών δεδομένων. Πρώτα καταλήγετε με τον πίνακα ( []) και έπειτα έρχεται ο πίνακας κατακερματισμού (αλλιώς γνωστός ως λεξικό, συσχετιστικός πίνακας, κατακερματισμός, χάρτης και… η λίστα συνεχίζεται)

Αναρωτηθήκατε ποτέ πώς λειτουργούν; Πώς είναι τόσο καταραμένοι;

Λοιπόν, ας πούμε ότι το JavaScript δεν είχε {}ή new Map(), και ας εφαρμόσουμε το δικό μας DumbMap!

Μια σημείωση για την πολυπλοκότητα

Πριν ξεκινήσουμε τη μπάλα, πρέπει να καταλάβουμε πώς λειτουργεί η πολυπλοκότητα μιας λειτουργίας: Η Wikipedia έχει μια καλή ανανέωση στην υπολογιστική πολυπλοκότητα, αλλά θα προσθέσω μια σύντομη εξήγηση για τους τεμπέληδες.

Η πολυπλοκότητα μετρά πόσα βήματα απαιτούνται από τη λειτουργία μας - όσο λιγότερα βήματα, τόσο πιο γρήγορη είναι η εκτέλεση (επίσης γνωστή ως "χρόνος εκτέλεσης").

Ας ρίξουμε μια ματιά στο παρακάτω απόσπασμα:

function fn(n, m) { return n * m}

Η υπολογιστική πολυπλοκότητα (από τώρα απλώς "πολυπλοκότητα") fnείναι O(1), που σημαίνει ότι είναι σταθερή (μπορείτε να διαβάσετε O(1)ως " το κόστος είναι ένα "): ανεξάρτητα από τα επιχειρήματα που περνάτε, η πλατφόρμα που τρέχει αυτόν τον κώδικα πρέπει να κάνει μόνο μία λειτουργία (πολλαπλασιάστε nσε m). Και πάλι, δεδομένου ότι είναι μία λειτουργία, το κόστος αναφέρεται ως O(1).

Η πολυπλοκότητα μετριέται υποθέτοντας ότι τα επιχειρήματα της συνάρτησής σας θα μπορούσαν να έχουν πολύ μεγάλες τιμές. Ας δούμε αυτό το παράδειγμα:

function fn(n, m) { let s = 0
 for (i = 0; i < 3; i++) { s += n * m }
 return s}

Θα νομίζατε ότι η πολυπλοκότητά του είναι O(3), σωστά;

Και πάλι, δεδομένου ότι η πολυπλοκότητα μετριέται στο πλαίσιο πολύ μεγάλων επιχειρημάτων, έχουμε την τάση να «ρίχνουμε» σταθερές και να θεωρούμε O(3)το ίδιο όπως O(1). Έτσι, ακόμη και σε αυτήν την περίπτωση, θα λέγαμε ότι η πολυπλοκότητα fnείναι O(1). Ανεξάρτητα από την αξία nκαι την αξία m, καταλήγετε πάντα να κάνετε τρεις λειτουργίες - οι οποίες, και πάλι, είναι ένα σταθερό κόστος (επομένως O(1)).

Τώρα αυτό το παράδειγμα είναι λίγο διαφορετικό:

function fn(n, m) { let s = []
 for (i = 0; i < n; i++) { s.push(m) }
 return s}

Όπως βλέπετε, βγαίνουμε πολλές φορές από την τιμή n, η οποία θα μπορούσε να είναι στα εκατομμύρια. Σε αυτήν την περίπτωση, ορίζουμε την πολυπλοκότητα αυτής της συνάρτησης O(n), καθώς θα πρέπει να κάνετε όσες λειτουργίες είναι η αξία ενός από τα επιχειρήματά σας.

Άλλα παραδείγματα;

function fn(n, m) { let s = []
 for (i = 0; i < 2 * n; i++) { s.push(m) }
 return s}

Αυτό το παράδειγμα παρουσιάζει βρόχους 2 * n, που σημαίνει ότι πρέπει να είναι η πολυπλοκότητα O(2n). Δεδομένου ότι αναφέραμε ότι οι σταθερές "αγνοούνται" κατά τον υπολογισμό της πολυπλοκότητας μιας συνάρτησης, αυτό το παράδειγμα ταξινομείται επίσης ως O(n).

Ενα ακόμα?

function fn(n, m) { let s = []
 for (i = 0; i < n; i++) { for (i = 0; i < n; i++) { s.push(m) } }
 return s}

Εδώ βγαίνουμε και βγαίνουμε nξανά μέσα στον κύριο βρόχο, που σημαίνει ότι η πολυπλοκότητα είναι "τετράγωνο" ( n * n): αν nείναι 2, θα τρέξουμε s.push(m)4 φορές, αν 3 θα το τρέξουμε 9 φορές, και ούτω καθεξής.

Σε αυτήν την περίπτωση, η πολυπλοκότητα της συνάρτησης αναφέρεται ως O(n²).

Ένα τελευταίο παράδειγμα;

function fn(n, m) { let s = []
 for (i = 0; i < n; i++) { s.push(n) }
 for (i = 0; i < m; i++) { s.push(m) }
 return s}

Σε αυτήν την περίπτωση δεν έχουμε ένθετους βρόχους, αλλά βγαίνουμε δύο φορές σε δύο διαφορετικά ορίσματα: η πολυπλοκότητα ορίζεται ως O(n+m). Πεντακάθαρη.

Τώρα που μόλις εισαγάγατε μια σύντομη εισαγωγή (ή ανανέωση) σχετικά με την πολυπλοκότητα, είναι πολύ εύκολο να καταλάβετε ότι μια λειτουργία με πολυπλοκότητα O(1)θα έχει πολύ καλύτερη απόδοση από μια με O(n).

Τα τραπέζια Hash έχουν μια O(1)πολυπλοκότητα: από την άποψη του λαού, είναι εξαιρετικά γρήγοροι . Ας προχωρήσουμε.

(Είμαι λίγο ξαπλωμένος σε κατακερματισμούς που έχουν πάντα O(1)πολυπλοκότητα, αλλά απλά διαβάζω;))

Ας φτιάξουμε έναν (χαζή) πίνακα κατακερματισμού

Ο πίνακας κατακερματισμού μας έχει 2 απλές μεθόδους - set(x, y)και get(x). Ας αρχίσουμε να γράφουμε έναν κωδικό:

Και ας εφαρμόσουμε έναν πολύ απλό, αναποτελεσματικό τρόπο για να αποθηκεύσουμε αυτά τα ζεύγη τιμών-κλειδιών και να τα ανακτήσουμε αργότερα. Αρχικά αρχίζουμε να τα αποθηκεύουμε σε έναν εσωτερικό πίνακα (θυμηθείτε, δεν μπορούμε να το χρησιμοποιήσουμε {}από τότε που εφαρμόζουμε {}- μυαλό!):

Τότε είναι απλώς θέμα λήψης του σωστού στοιχείου από τη λίστα:

Το πλήρες παράδειγμά μας:

Μας DumbMap είναι εκπληκτικό! Λειτουργεί έξω από το κουτί, αλλά πώς θα λειτουργήσει όταν προσθέτουμε μεγάλη ποσότητα ζευγών κλειδιού-τιμής;

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

Τα αποτελέσματα? Όχι τόσο ενθαρρυντικό:

with very few records in the map: 0.118mswith lots of records in the map: 14.412ms

Κατά την εφαρμογή μας, πρέπει να βρούμε όλα τα στοιχεία μέσα this.listγια να βρούμε ένα με το αντίστοιχο κλειδί. Το κόστος είναι O(n), και είναι πολύ τρομερό.

Κάντε γρήγορα (er)

Πρέπει να βρούμε έναν τρόπο να αποφύγει τη μεταγωγή λίστα μας: η ώρα να βάλει κατακερματισμού πίσω στο πίνακα κατακερματισμού .

Αναρωτηθήκατε ποτέ γιατί αυτή η δομή δεδομένων ονομάζεται πίνακας κατακερματισμού ; Αυτό συμβαίνει επειδή χρησιμοποιείται μια λειτουργία κατακερματισμού στα πλήκτρα που ορίζετε και λαμβάνετε. Θα χρησιμοποιήσουμε αυτήν τη λειτουργία για να μετατρέψουμε το κλειδί μας σε ακέραιο iκαι να αποθηκεύσουμε την αξία μας στο ευρετήριο iτης εσωτερικής μας λίστας. Δεδομένου ότι η πρόσβαση σε ένα στοιχείο, από το ευρετήριό του, από μια λίστα έχει ένα σταθερό κόστος ( O(1)), τότε ο πίνακας κατακερματισμού θα έχει επίσης κόστος O(1).

Ας το δοκιμάσουμε:

Εδώ χρησιμοποιούμε το string-hash module, το οποίο μετατρέπει απλά μια συμβολοσειρά σε αριθμητικό hash. Το χρησιμοποιούμε για αποθήκευση και ανάκτηση στοιχείων στο ευρετήριο hash(key)της λίστας μας. Τα αποτελέσματα?

with lots of records in the map: 0.013ms

W - O - W. Αυτό μιλάω!

Δεν χρειάζεται να βρούμε όλα τα στοιχεία της λίστας και η ανάκτηση στοιχείων DumbMapείναι πολύ γρήγορη!

Επιτρέψτε μου να το θέσω όσο το δυνατόν πιο απλή: η κατακερματισμός είναι αυτό που κάνει τους πίνακες κατακερματισμού εξαιρετικά αποτελεσματικούς . Χωρίς μαγεία. Τίποτα περισσότερο. Νάντα. Απλώς μια απλή, έξυπνη, έξυπνη ιδέα.

Το κόστος της σωστής λειτουργίας κατακερματισμού

Φυσικά, η επιλογή μιας γρήγορης λειτουργίας κατακερματισμού είναι πολύ σημαντική. Εάν η hash(key)λειτουργία μας εκτελείται σε λίγα δευτερόλεπτα, η λειτουργία μας θα είναι αρκετά αργή ανεξάρτητα από την πολυπλοκότητά της.

Ταυτόχρονα, είναι πολύ σημαντικό να βεβαιωθείτε ότι η λειτουργία κατακερματισμού μας δεν παράγει πολλές συγκρούσεις , καθώς θα ήταν επιζήμια για την πολυπλοκότητα του πίνακα κατακερματισμού μας.

Ταραγμένος? Ας ρίξουμε μια πιο προσεκτική ματιά στις συγκρούσεις.

Συγκρούσεις

Ίσως να σκεφτείτε « Αχ, μια καλή λειτουργία κατακερματισμού δεν δημιουργεί ποτέ συγκρούσεις! ": Καλά, επιστρέψτε στον πραγματικό κόσμο και ξανασκεφτείτε το. Η Google μπόρεσε να παράγει συγκρούσεις για τον αλγόριθμο κατακερματισμού SHA-1 και είναι θέμα χρόνου, ή υπολογιστικής ισχύος, πριν από μια συνάρτηση κατακερματισμού σπάσει και επιστρέψει τον ίδιο κατακερματισμό για 2 διαφορετικές εισόδους. Πάντα υποθέστε ότι η λειτουργία κατακερματισμού δημιουργεί συγκρούσεις και εφαρμόστε τη σωστή άμυνα έναντι τέτοιων περιπτώσεων.

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

Αυτή η συνάρτηση χρησιμοποιεί έναν πίνακα 10 στοιχείων για την αποθήκευση τιμών, πράγμα που σημαίνει ότι τα στοιχεία είναι πιθανό να αντικατασταθούν - ένα δυσάρεστο σφάλμα στο DumbMap:

Προκειμένου να επιλυθεί το ζήτημα, μπορούμε απλά να αποθηκεύσουμε πολλά ζεύγη τιμών-κλειδιών στον ίδιο δείκτη. Ας τροποποιήσουμε λοιπόν τον πίνακα κατακερματισμού:

Όπως ίσως παρατηρήσετε, εδώ επιστρέφουμε στην αρχική μας υλοποίηση: αποθηκεύστε μια λίστα ζευγών κλειδιών-τιμών και πραγματοποιήστε βρόχο σε κάθε ένα από αυτά. Αυτό θα είναι αρκετά αργό όταν υπάρχουν πολλές συγκρούσεις για ένα συγκεκριμένο ευρετήριο της λίστας.

Ας συγκρίνουμε αυτό χρησιμοποιώντας τη δική μας hash()λειτουργία που δημιουργεί ευρετήρια από 1 έως 10:

with lots of records in the map: 11.919ms

και χρησιμοποιώντας τη συνάρτηση κατακερματισμού από string-hash, η οποία δημιουργεί τυχαία ευρετήρια:

with lots of records in the map: 0.014ms

Ω! Υπάρχει το κόστος επιλογής της σωστής λειτουργίας κατακερματισμού - αρκετά γρήγορα ώστε να μην επιβραδύνει την εκτέλεση από μόνη της και αρκετά καλή ώστε να μην προκαλεί πολλές συγκρούσεις.

Γενικά O (1)

Θυμάσαι τα λόγια μου;

Τα Hashtables έχουν μια O(1)πολυπλοκότητα

Λοιπόν, είπα ψέματα: η πολυπλοκότητα ενός πίνακα κατακερματισμού εξαρτάται από τη λειτουργία κατακερματισμού που επιλέγετε. Όσο περισσότερες συγκρούσεις δημιουργείτε, τόσο περισσότερο τείνει η πολυπλοκότητα O(n).

Λειτουργία κατακερματισμού όπως:

function hash(key) { return 0}

θα σήμαινε ότι ο πίνακας κατακερματισμού μας έχει μια πολυπλοκότητα O(n).

Γι 'αυτό, σε γενικές γραμμές, η υπολογιστική πολυπλοκότητα έχει τρία μέτρα: τα καλύτερα, τα μέσα και τα χειρότερα σενάρια. Τα Hashtables έχουν μια O(1)πολυπλοκότητα στα καλύτερα και μέσα σενάρια περιπτώσεων, αλλά εμπίπτουν O(n)στο χειρότερο σενάριό τους.

Θυμηθείτε: μια καλή λειτουργία κατακερματισμού είναι το κλειδί για έναν αποτελεσματικό πίνακα κατακερματισμού - τίποτα περισσότερο, τίποτα λιγότερο.

Περισσότερα για συγκρούσεις…

Η τεχνική που χρησιμοποιήσαμε για να διορθώσουμε DumbMapσε περίπτωση συγκρούσεων ονομάζεται ξεχωριστή αλυσίδα: αποθηκεύουμε όλα τα ζεύγη κλειδιών που δημιουργούν συγκρούσεις σε μια λίστα και βρόχους μέσω αυτών.

Μια άλλη δημοφιλής τεχνική είναι η ανοιχτή διεύθυνση:

  • σε κάθε ευρετήριο της λίστας μας αποθηκεύουμε ένα και μόνο ζεύγος κλειδιών-τιμών
  • όταν προσπαθείτε να αποθηκεύσετε ένα ζεύγος στο ευρετήριο x, εάν υπάρχει ήδη ένα ζεύγος κλειδιού-τιμής, προσπαθήστε να αποθηκεύσετε το νέο μας ζεύγος στοx + 1
  • αν x + 1ληφθεί, δοκιμάστε x + 2και ούτω καθεξής…
  • κατά την ανάκτηση ενός στοιχείου, κατακερματίστε το κλειδί και δείτε εάν το στοιχείο σε αυτήν τη θέση ( x) ταιριάζει με το κλειδί μας
  • αν όχι, προσπαθήστε να αποκτήσετε πρόσβαση στο στοιχείο στη θέση x + 1
  • ξεπλύνετε και επαναλάβετε μέχρι να φτάσετε στο τέλος της λίστας ή όταν βρείτε ένα κενό ευρετήριο - αυτό σημαίνει ότι το στοιχείο μας δεν βρίσκεται στον πίνακα κατακερματισμού

Έξυπνο, απλό, κομψό και συνήθως πολύ αποδοτικό!

Συχνές ερωτήσεις (ή TL; DR)

Ο πίνακας κατακερματισμού κατακερματίζει τις τιμές που αποθηκεύουμε;

Όχι, τα πλήκτρα έχουν κατακερματιστεί έτσι ώστε να μπορούν να μετατραπούν σε ακέραιο iκαι τα κλειδιά και οι τιμές αποθηκεύονται στη θέση iσε μια λίστα.

Οι συναρτήσεις κατακερματισμού που χρησιμοποιούνται από πίνακες κατακερματισμού δημιουργούν συγκρούσεις;

Απολύτως - έτσι οι πίνακες κατακερματισμού εφαρμόζονται με στρατηγικές άμυνας για την αποφυγή δυσάρεστων σφαλμάτων.

Οι πίνακες κατακερματισμού χρησιμοποιούν μια λίστα ή μια συνδεδεμένη λίστα εσωτερικά;

Εξαρτάται, και οι δύο μπορούν να λειτουργήσουν. Στα παραδείγματα μας, χρησιμοποιούμε τον πίνακα JavaScript ( []) που μπορεί να αλλάξει δυναμικά:

> a = []
> a[3] = 1
> a[ , 1 ]

Γιατί επιλέξατε JavaScript για τα παραδείγματα; Οι πίνακες JS είναι πίνακες κατακερματισμού!

Για παράδειγμα:

> a = [][]
> a["some"] = "thing"'thing'
> a[ some: 'thing' ]
> typeof a'object'

Ξέρω, καταραμένο JavaScript.

Το JavaScript είναι «καθολικό» και ίσως η ευκολότερη γλώσσα που πρέπει να κατανοήσετε όταν κοιτάζετε κάποιο δείγμα κώδικα. Το JS μπορεί να μην είναι η καλύτερη γλώσσα, αλλά ελπίζω ότι αυτά τα παραδείγματα είναι αρκετά σαφή.

Είναι το παράδειγμά σας μια πολύ καλή εφαρμογή ενός πίνακα κατακερματισμού; Είναι πραγματικά αυτό απλό;

Οχι, καθόλου.

Ρίξτε μια ματιά στην "εφαρμογή ενός πίνακα κατακερματισμού σε JavaScript" του Matt Zeunert, καθώς θα σας δώσει λίγο περισσότερο πλαίσιο. Υπάρχουν πολλά περισσότερα να μάθουν, οπότε θα πρότεινα επίσης να ρίξετε μια ματιά:

  • Το μάθημα του Paul Kube σε hash tables
  • Υλοποίηση του δικού μας πίνακα Hash με ξεχωριστή αλυσίδα στην Java
  • Αλγόριθμοι, 4η Έκδοση - Πίνακες κατακερματισμού
  • Σχεδιασμός ενός γρήγορου πίνακα κατακερματισμού

Στο τέλος…

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

Ελπίζω να σας άρεσε αυτό το άρθρο και μη διστάσετε να μοιραστείτε τα σχόλιά σας μαζί μου.

Ιδιαίτερες ευχαριστίες στον Joe που με βοήθησε αναθεωρώντας αυτό το άρθρο.

Adios!