Hash Table

Αυτή η σελίδα αφορά το hash table, μια δομή δεδομένων η οποία δεν χρειάζεται να υλοποιηθεί συχνά. Σας συστήνουμε να το μάθετε γιατί περιέχει κάποιες ενδιαφέρουσες γενικές ιδέες, αλλά δεν είναι ιδιαίτερα χρήσιμο, εκτός αν χρησιμοποιείτε κάποια γλώσσα προγραμματισμού η οποία δεν περιέχει υλοποίησή του (όπως η c). Στο τέλος παραθέτουμε πώς μπορούμε να αποφύγουμε την υλοποίηση της δομής αυτής χρησιμοποιώντας την STL της c++.

Το hash table, ή αλλιώς πίνακας κατακερματισμού, είναι μία δομή δεδομένων για γρήγορη αποθήκευση και ανάκτηση ζευγών στοιχείων. Συγκεκριμένα, αποθηκεύει ένα κλειδί και μία τιμή, έτσι ώστε δεδομένου του κλειδιού να μπορεί να επιστρέψει την τιμή. Για να το πετύχει αυτό, αντιστοιχεί σε κάθε κλειδί μία (όχι απαραίτητα μοναδική) θέση σε κάποιον πίνακα και αποθηκεύει σε εκείνη τη θέση το ζεύγος κλειδιού και τιμής. Η συνάρτηση που κατασκευάζει τη θέση δεδομένης της τιμής λέγεται hash function (συνάρτηση κατακερματισμού) και οι μοναδικές συνθήκες για τη συνάρτηση αυτή είναι να επιστρέφει θέσεις στο κατάλληλο εύρος, και να έχει μικρή πιθανότητα για δύο διαφορετικά κλειδιά να επιστρέψει την ίδια θέση. Την δεύτερη συνθήκη θα την ορίσουμε καλύτερα παρακάτω.

• Βασική ιδέα
• Συνάρτηση κατακερματισμού
  • Για φυσικούς αριθμούς
  • Για λέξεις
  • Θεωρητικές ιδιότητες
• Υλοποίηση
  • Με λίστες (cuckoo hashing)
  • Με πίνακα (linear probing)
  • Με STL

Βασική ιδέα

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

Για παράδειγμα, ας υποθέσουμε ότι σε κάποιο πρόβλημα μας δίνονται ζευγάρια αριθμών και λέξεων $(n,w)$, και θέλουμε δεδομένου του αριθμού $n$ να επιστρέψουμε την αντίστοιχη λέξη $w$, όμως γνωρίζουμε ότι οι αριθμοί είναι πολύ μεγάλες δυνάμεις του δύο. Σε αυτήν την περίπτωση, δεν μπορούμε απλά να κατασκευάσουμε έναν πίνακα και στη θέση $n$ να τοποθετήσουμε τη λέξη $w$, αλλά πρέπει να συμπυκνώσουμε κάπως τις τιμές. Παρατηρούμε ότι θα μπορούσαμε να χρησιμοποιήσουμε τη συνάρτηση $h(n)=\log_2 n$, η οποία στην $k$-οστή δύναμη του δύο αντιστοιχεί τον αριθμό $k$. Με αυτόν τον τρόπο συμπυκνώνουμε πολύ καλά το εύρος τιμών μας, και μπορούμε να αποθηκεύουμε τις λέξεις στις αντίστοιχες θέσεις (με την πολύ καλή ιδιότητα ότι η συνάρτηση $h$ είναι ένα-προς-ένα).

Ένα άλλο παράδειγμα που θα μπορούσαμε να παραθέσουμε είναι ότι μας δίνονται ζευγάρια λέξεων και αριθμών $(w,n)$ και θέλουμε δεδομένης της λέξης να επιστρέψουμε τον αριθμό, όμως γνωρίζουμε ότι οι λέξεις αποτελούνται μόνο από τα γράμματα ‘a’ και ‘b’. Συνεπώς, μπορούμε να συμβολίσουμε την λέξη $w$ ως έναν αριθμό στο δυαδικό σύστημα (αντικαθιστώντας τα ‘a’ με 1 και τα ‘b’ με 0, αρκεί βέβαια να προσθέσουμε τον αριθμό 1 στην αρχή έτσι ώστε η λέξη ‘bba’ και η λέξη ‘ba’ να μην αντιστοιχούν στον ίδιο αριθμό), μειώνοντας δραματικά το εύρος των τιμών.

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

Συνάρτηση κατακερματισμού

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

Για φυσικούς αριθμούς

Η πιο απλή περίπτωση όπου μπορούμε να χρησιμοποιήσουμε συναρτήσεις κατακερματισμού είναι οι φυσικοί αριθμοί. Έστω $M$ το μέγεθος του hash table (το οποίο το αποφασίζουμε εμείς). Τότε, θα χρησιμοποιούμε τη συνάρτηση κατακερματισμού $h(n) = n\mod M$. Ακολουθεί η υλοποίηση της συνάρτησης αυτής:

int M=1000003;
unsigned int hash_num(unsigned long long n) {
    return n%M;
}

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

Αυτή η συνάρτηση είναι ιδιαίτερα απλοϊκή, και μπορούμε να την βελτιώσουμε θέτοντας $h(n) = (an+b)\mod M$, όπου $a,b$ είναι δύο φυσικοί αριθμοί τους οποίους επιλέγουμε τυχαία στην αρχικοποίηση του προγράμματός μας.

Για λέξεις

Η πιο σημαντική χρήση των hash tables είναι όταν τα κλειδιά είναι αλφαριθμητικές σειρές. Για να δημιουργήσουμε τη συνάρτηση, θα αναφερθούμε στο παράδειγμα που παραθέσαμε παραπάνω, στο οποίο τα κλειδιά αποτελούνται μόνο από τους χαρακτήρες ‘a’ και ‘b’. Σε εκείνο το παράδειγμα, θεωρήσαμε ότι οι λέξεις είναι αριθμοί σε βάση το δύο. Εάν είχαμε τα γράμματα ‘a’, ‘b’, ‘c’, ‘d’, ‘e’, τότε θα μπορούσαμε να χρησιμοποιήσουμε ως βάση το πέντε. Συνεπώς, για να καλύψουμε ολόκληρο το αλφάβητο, μπορούμε να χρησιμοποιήσουμε ως βάση το 26. Δεδομένου ολόκληρου του εύρους χαρακτήρων, μπορούμε να έχουμε βάση το 256. Για παράδειγμα, η λέξη “pdp” αντιστοιχεί στον αριθμό $256^2\times 112 + 256^1\times 100 + 256^0\times 112 = 7365744$. Επειδή σε γενικές γραμμές οι αριθμοί που προκύπτουν είναι μεγάλοι, μπορούμε να συνδυάσουμε την μέθοδο αυτήν με την παραπάνω μέθοδο κατακερματισμού φυσικών αριθμών. Οπότε, αν $w_i$ είναι η τιμή σε ascii του $i$-οστού γράμματος της δεδομένης λέξης, και $s$ το πλήθος γραμμάτων της λέξης, τότε θέτουμε $h(w) = (256^sw_0 + 256^{s-1}w_1 + \ldots + 256^1w_{s-1}+256^0w_s)\mod M$, το οποίο γράφεται και ως $h(w) = (((256^sw_0\mod M+256^{s-1}w_1)\mod M+\ldots+256^1w_{s-1})\mod M + 256^0w_s)\mod M$. Άρα έχουμε την εξής υλοποίηση:

int M = 1000003, base = 256;
unsigned int hash_word(char *str) {
    int s = strlen(str);
    unsigned int out = 0;
    for(int i=0; i<s; ++i) {
        out = ((out*base)%M+str[i])%M;
    }
    return out;
}

Θεωρητικές ιδιότητες

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

Ένας βασικός όρος για τις συναρτήσεις κατακερματισμού είναι η “ανεξαρτησία” τους (independence). Μια συνάρτηση κατακερματισμού $h()$ λέγεται $k$-independent αν για κάθε $k$ διαφορετικές μεταξύ τους τιμές $x_i$, ισχύει ότι οι εικόνες τους υπό την $h$ (δηλαδή τα $h(x_1), \ldots, h(x_k)$) είναι ανεξάρτητες τυχαίες μεταβλητές. Δηλαδή, δεδομένων των τιμών της $h$ σε $k-1$ διαφορετικές μεταξύ τους τιμές, δεν μπορούμε να προβλέψουμε την τιμή της $h$ σε ένα καινούριο σημείο.

Ο πιο συνηθισμένος τρόπος για να κατασκευάσουμε $k$-independent συναρτήσεις σε ακέραιους αριθμούς είναι να θεωρήσουμε ένα πολυώνυμο βαθμού $k$ με τυχαίους συντελεστές και να πάρουμε το υπόλοιπο της συνάρτησης υπό έναν πρώτο αριθμό. Στην πράξη, συνήθως χρησιμοποιούμε το πολύ 2-independent συναρτήσεις κατακερματισμού, αν και για κάποιους αλγορίθμους απαιτούνται πολυώνυμα μεγαλύτερου βαθμού.

Οι συναρτήσεις που παραθέσαμε παραπάνω δεν είναι 2-independent, αλλά πάλι μπορούμε να τις χρησιμοποιήσουμε. Συγκεκριμένα, η συνάρτηση που παραθέσαμε για φυσικούς αριθμούς είναι πολυώνυμο πρώτου βαθμού. Σε κάθε περίπτωση μπορούμε να χρησιμοποιήσουμε πολυώνυμο δευτέρου βαθμού εάν παρατηρήσουμε υπερβολικά πολλά collisions, αλλά κάτι τέτοιο είναι ιδιαίτερα σπάνιο σε διαγωνισμούς.

Υλοποίηση

Το hash table υποστηρίζει τις εξής πράξεις:

• Insert(key, value): Αναθέτει την τιμή value στο κλειδί key.
• Lookup(key): Επιστρέφει την τιμή που έχουμε αναθέσει στο κλειδί key.

Όπως αναφέραμε παραπάνω, οι συναρτήσεις κατακερματισμού έχουν την πιθανότητα να δώσουν σε διαφορετικά κλειδιά την ίδια θέση. Σύμφωνα με το birthday paradox, εάν το μέγεθος του hash table είναι $M$, τότε δεδομένων $\sqrt{M}$ στοιχείων υπάρχει μεγάλη πιθανότητα για σύγκρουση τιμών (ανεξάρτητα από την επιλεγμένη συνάρτηση κατακερματισμού). Συνεπώς, χρειαζόμαστε έναν τρόπο να αντιμετωπίσουμε αυτές τις περιπτώσεις.

Με λίστες (cuckoo hashing)

Η πιο αυτονόητη υλοποίηση του hash table χρησιμοποιεί έναν πίνακα από λίστες, και όταν τοποθετεί ένα ζευγάρι σε μια θέση, το τοποθετεί στο τέλος της αντίστοιχης λίστας. Μπορούμε να βελτιώσουμε αρκετά αυτήν την ιδέα, χρησιμοποιώντας δύο συναρτήσεις κατακερματισμού (οπότε και λαμβάνουμε δύο θέσεις για το κλειδί) και εισάγουμε το ζευγάρι στο τέλος της μικρότερης λίστας (από τις λίστες που αντιστοιχούν στις θέσεις που λάβαμε).

Για να πετύχουμε καλύτερη ταχύτητα (και για να είμαστε σωστοί από άποψης θεωρητικής πολυπλοκότητας), χρησιμοποιούμε κάτι που λέγεται cuckoo hashing. Ουσιαστικά κατασκευάζουμε δύο συναρτήσεις κατακερματισμού και χρησιμοποιούμε δύο πίνακες (η πρώτη συνάρτηση αντιστοιχεί στον πρώτο πίνακα, και η δεύτερη στον δεύτερο). Κατά την εισαγωγή ενός αντικειμένου, βρίσκουμε τις τιμές και των δύο συναρτήσεων κατακερματισμού στο κλειδί του αντικειμένου, και το προσθέτουμε στον πίνακα του οποίου η λίστα στην αντίστοιχη θέση είναι μικρότερη. Ο αλγόριθμος αυτός απαιτεί 2-independent συνάρτηση κατακερματισμού, αλλά σε πρακτικές εφαρμογές δεν είναι απαραίτητο κάτι τέτοιο. Γενικά μπορείτε για λόγους συντομίας να χρησιμοποιήσετε μόνο έναν πίνακα, αλλά σε γενικές γραμμές δεν συστήνεται.

Ακολουθεί υλοποίηση σε c++, στην οποία χρησιμοποιούμε την δομή vector αντί για λίστα για λόγους ευκολίας. Δημιουργούμε ένα hash table στο οποίο το κλειδί και η τιμή είναι λέξεις. Στην περίπτωση που δεν υπάρχει το κλειδί στην δομή μας επιστρέφουμε ένα κενό string.

int M = 1000003, base = 256, a[2], b[2];
vector<pair<string, string> > table[2][M], table[M];
void Initialize() {
    srand(time(NULL));
    a[0]=rand()%1000;
    a[1]=rand()%1000;
    b[0]=rand()%1000;
    b[1]=rand()%1000;
}
unsigned int hash_word(string str, int ind) {
    int s = str.size();
    unsigned int out = 0, tmp;
    for(int i=0; i<s; ++i) {
        tmp = (a[ind]*str[i]+b[ind])%base;
        out = ((out*base)%M+tmp)%M;
    }
}
void Insert(string key, string value) {
    unsigned int pos[2];
    pos[0] = hash_word(key, 0);
    pos[1] = hash_word(key, 1);
    for(int ind=0; ind<2; ++ind) {
        for(int i=0; i<table[ind][pos[ind]].size(); ++i) {
            if(table[ind][pos[ind]][i].first == key) {
                table[ind][pos[ind]][i].second = value;
                return;
            }
        }
    }
    int ind=0;
    if(table[1][pos[1]].size()<table[0][pos[0]].size()) {
        ind=1;
    }
    table[ind][pos[ind]].insert(make_pair(key, value));
}
string Lookup(string key) {
    string out;
    unsigned int pos[2];
    pos[0] = hash_word(key, 0);
    pos[1] = hash_word(key, 1);
    for(int ind=0; ind<2; ++ind) {
        for(int i=0; i<table[ind][pos[ind]].size(); ++i) {
            if(table[ind][pos[ind]][i].first == key) {
                out = table[ind][pos[ind]][i].second;
            }
        }
    }
    return out;
}

Με πίνακα (linear probing)

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

Το βασικότερο θετικό αυτής της υλοποίησης (πέρα από την απλότητά της), είναι η ταχύτητά της. Επειδή τα στοιχεία που αναζητούμε βρίσκονται όλα στον ίδιο πίνακα, και η αναζήτηση στοιχείου προσπελάζει σειριακά τον πίνακα, ο αλγόριθμος αυτός είναι cache-efficient. Αυτό σε γενικές γραμμές σημαίνει ότι χρησιμοποιεί πιο αποτελεσματικά την μνήμη του υπολογιστή από τον παραπάνω αλγόριθμο, ο οποίος συνέχεια κοιτάζει διαφορετικά σημεία στη μνήμη.

Να σημειωθεί ότι για να είναι γρήγορος αυτός ο αλγόριθμος, πρέπει το μέγεθος του πίνακα να είναι διπλάσιο από το μέγιστο πλήθος στοιχείων που θα εισάγουμε. Θεωρητικά, στο linear probing πρέπει να χρησιμοποιούμε 5-independent συνάρτηση κατακερματισμού. Σε πρακτικές εφαρμογές όμως, μια απλή συνάρτηση κατακερματισμού, όπως αυτή που παραθέτουμε παρακάτω, είναι αρκετή.

ΠΡΟΣΟΧΗ: Εάν θέλουμε να αφαιρέσουμε αντικείμενα, δεν είναι όσο απλό όσο θα ήταν στην προηγούμενη υλοποίηση. Αντί απλά να τα σβήνουμε από τον πίνακα, πρέπει να εισάγουμε ένα στοιχείο που θα υποδηλώνει ότι εκείνο το κελί δεν είναι άδειο σε περίπτωση που ψάχνουμε ένα στοιχείο, αλλά σε περίπτωση εισαγωγής μπορούμε να το αλλάξουμε.

Ακολουθεί υλοποίηση σε c++.

int M = 1000003, base = 256;
pair<string, string> table[M];
unsigned int hash_word(string str) {
    int s = str.size();
    unsigned int out = 0;
    for(int i=0; i<s; ++i) {
        out = ((out*base)%M+str[i])%M;
    }
}
void Insert(string key, string value) {
    unsigned int pos = hash_word(key);
    while(!table[pos][i].first.empty() && table[pos][i].first != key) {
        pos = (pos+1)%M;
    }
    table[pos] = make_pair(key, value);
}
string Lookup(string key) {
    string out;
    unsigned int pos = hash_word(key);
    while(!table[pos][i].first.empty() && table[pos][i].first != key) {
        pos = (pos+1)%M;
    }
    return table[pos].second;
}

Για πληρέστερη υλοποίηση του linear probing σε c παραπέμπουμε εδώ.

Με STL

Για όσους χρησιμοποιούν τη γλώσσα c++ υπάρχει μία ιδιαίτερα εύκολη λύση, χρησιμοποιώντας τη συλλογή STL. Συγκεκριμένα, στην c++11 προστέθηκε η δομή unordered_map , η οποία βρίσκεται στην ομώνυμη βιβλιοθήκη. Σε παλιότερες εκδόσεις της c++, η δομή αυτή υπάρχει (όχι επισήμως), και μπορεί να βρεθεί στη βιβλιοθήκη tr1/unordered_map. Να σημειώσουμε ότι είναι ιδιαίτερα σημαντικό στην αρχή του προγράμματός μας να χρησιμοποιούμε table.rehash(M) όπου table είναι το unordered_map και M είναι το πλήθος των στοιχείων που θα εισάγουμε συνολικά, διότι αλλιώς η δομή θα είναι αρκετά αργή (ακόμα και πιο αργή από το map το οποίο έχει αναζήτηση και προσθήκη σε $O(\log n)$ αντί για $O(1)$ που έχει το unordered_map).

Ακολουθεί υλοποίηση hash table με τη χρήση του unordered_map σε c++11.

#include <unordered_map> // unordered_map
unordered_map<string, string> table;
void Initialize(int n) {
    table.rehash(n);
}
void Insert(string key, string value) {
    table[key] = value;
}
void Lookup(string key) {
    if(table.find(key)!=table.end()) {
        return table[key];
    }
    return "";
}

Εάν χρησιμοποιούσαμε παλαιότερη έκδοση της c++, θα αντικαθιστούσαμε την πρώτη γραμμή του κώδικα με τις εξής δύο γραμμές:

#include <tr1/unordered_map>
using namespace tr1;

Σχόλια