Αλγοριθμική ερώτηση

[nik324]

Λοιπόν αφού το άνοιξα το θέμα ας το εκμεταλευτώ...

 

Θα ήθελα να κάνουμε μια συζήτηση για συναρτήσεις κατακερματισμού και με ποιον τρόπο θα πρέπει αυτές να επιλέγονται...

 

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

Και θέλουμε να κάνουμε χρήση της τεχνικής αλυσίδων...

Πως θα επιλέξουμε το μέγεθος του hash table?

Επεξ/σία 7 Δεκεμβρίου 2012 από nik324

[migf1]

Θα σου πω μια πολύ απλοϊκή προσέγγιση.

 

Με δεδομένο πως ο αριθμός ταυτότητας έχει ένα γράμμα μπροστά από τον αριθμό, η πιο απλοϊκή προσέγγιση είναι να έχεις ένα hash-table με 24 slots, 1 για κάθε γράμμα.

 

Αν υποθέσουμε τώρα πως ο αριθμός μετά το γράμμα έχει συγκεκριμένο πλήθος ψηφίων, ή έστω συγκεκριμένο μέγιστο πλήθος ψηφίων, ας πούμε 6, τότε για κάθε γράμμα έχουμε 999999 πιθανές hased τιμές, δηλαδή σύνολο 24 * 999999 = "ζήσε Μάη μου να φας τριφύλι" = 23.999.976 slots.

 

But we can do better than that.

 

Το μέγιστο άθροισμα ψηφίων που μπορεί να προκύψει από έναν 6 ψήφιο αριθμό είναι το 6 * 9 = 54. Οπότε μπορούμε να κάνουμε hash στα γράμματα το άθροισμα των ψηφίων όσων αριθμών έχουν μπροστά τους το εκάστοτε γράμμα. Οπότε αμέσως-αμέσως έχουμε κατέβει στα 24 * 54 = 1296 slots για το hash-table μας. Νούμερο απόλυτα διαχειρίσιμο.

 

Αν θέλουμε ακόμα λιγότερα slots, μπορούμε π.χ. να σπάσουμε το 1296 σε 130 δεκάδες ή ακόμα και σε 13 εκατοντάδες, αλλά προφανώς όσο λιγότερα slots έχει το hash-table τόσο περισσότερο αναιρούμε την χρησιμότητά του.

 

EDIT:

 

Το 'ψαχνα στα bookmarks μου, αλλά μάλλον είναι στο laptop. Οπότε μετά από λίγο googling το βρήκα: http://www.fearme.com/misc/alg/node28.html

 

Πιστεύω θα σου φανεί χρήσιμο

 

 

[defacer]

Πρώτα απ' όλα: το μέγεθος του hash table δεν έχει καμία σχέση με την επιλογή της hash function.

 

Αν ο πίνακας έχει μέγεθος N και περνάς μέσα Χ ανθρώπους τότε κατα μέσο όρο η κάθε λίστα θα έχει μήκος Χ/Ν. Όσο πιο κοντά στο ιδανικό είναι η επιλεγμένη hash function τόσο μικρότερη θα είναι και η διασπορά των πραγματικών μηκών που θα έχουν οι λίστες σε σχέση με το ιδανικό Χ/Ν, δηλαδή τόσο πιο κοντά στο θεωρητικό Χ/Ν θα είναι και οι πραγματικές τιμές.

 

Τώρα με δεδομένα ότι

• Χ ~= 500 όπως λες
  
• η hash function δεν θα είναι τραγική
  
• λίστες με 5 ("τυχαίο" νούμερο) στοιχεία και κάτω είναι just fine
  

έχουμε 5 ~= 500 / Ν => Ν ~= 100 το μέγεθος ενός hashtable που θα πηγαίνει σφαίρα.

 

Στη γενική περίπτωση όμως όπου δεν έχεις ιδέα τελικά πόσο πράγμα θα μπει μέσα στο hashtable είσαι αναγκασμένος να προβλέψεις το γεγονός ότι αν το load factor του πίνακα ανέβει πάνω από κάποιο όριο (το οποίο εξαρτάται από το πώς αντιμετωπίζονται τα collisions, π.χ. με linear probing προφανώς το load factor είναι όχι απλά ανεπιθύμητο αλλά αδύνατο να γίνει > 1 ενώ με separate chaining μπορεί να έχεις load factor 10 και να είσαι OK) τότε θα πρέπει να μεταφέρεις όλα σου τα δεδομένα σε ένα νέο μεγαλύτερο πίνακα (κάτι που σημαίνει ότι θα χρειαστεί να ξανακάνεις hash τα πάντα). Συνήθως αυτό γίνεται περίπου διπλασιάζοντας το μέγεθος του πίνακα κάθε φορά ούτως ώστε για N στοιχεία να μη χρειαστούν παραπάνω από lgN reallocations κατά τη διάρκεια ζωής του πίνακα. Το πώς και πότε γίνεται reallocation και με ποιά κριτήρια είναι ένα θέμα που έχει κάποιο ψωμί από μόνο του μιας και μιλάμε για την περίπτωση όπου δεν ξέρεις πώς θα χρησιμοποιηθεί η class HashTable που γράφεις.

 

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

 

>
hash = 0;
for (i = 0; i < numberOfPiecesToHash; ++i) {
hash = hash * X + hashFunction(getPieceToHash(i));
}

 

όπου

• η επιστρεφόμενη τιμή της hashFunction() έχει περίπου το ίδιο range με τις τιμές που μπορεί να πάρει το hash ανάλογα με το data type του
  
• το numberOfPiecesToHash εξαρτάται από το πλήθος των δεδομένων που θέλεις να κάνεις hash γιατί έμμεσα το range επιστροφών της hashFunction εξαρτάται από το πόσα δεδομένα έχεις για να την ταϊσεις κάθε φορά
  
• το Χ είναι ένας πρώτος αριθμός αρκετά μεγάλος ούτως ώστε συνήθως το hash * X να κάνει overflow με αποτέλεσμα να "ανακατεύονται τα bits"
  

Υπάρχουν πολλές άλλες λεπτομέρειες που εμπλέκονται γενικά οπότε δεν συνεχίζω γιατί δε θα τελειώσει ποτέ το post.

[migf1]

Πρώτα απ' όλα: το μέγεθος του hash table δεν έχει καμία σχέση με την επιλογή της hash function.

...

 

Δεν είμαι σίγουρος τι εννοείς με την παραπάνω μπολνταρισμένη (από εσένα) φράση, αλλά το τετριμμένο 101 hasing function είναι το λεγόμενο division hashing:

 

>
int hash_by_division(int key, size_t lenHtab) 
{
 return key % lenHtab;
}

 

το οποίο προφανώς βρίσκεται σε απόλυτη εξάρτηση από το μέγεθος του hash table.

 

EDIT:

 

Ομοίως και το multiplication hashing, ομοίως και το variable string addition hashing (μόλις τα τσέκαρα για να βεβαιωθώ πως το θυμόμουν σωστά).

[defacer]

Εννοώ πως το τελευταίο % hashTableSize δεν είναι μέρος της hash function αλλά μέρος του implementation του hashtable (αν κάνεις google για τους όρους που αναφέρεις θα δεις ότι όντως αυτή η μεταβλητή δεν αναφέρεται πουθενά). Στο παράδειγμα που έδωσες η hash function στην πραγματικότητα είναι f(x) = x.

 

Ή για να το πω με άλλα λόγια, μια hash function για strings θα επιστρέψει πάντα την ίδια τιμή για το string "hello" ανεξάρτητα από το πόσο μεγάλος είναι ο hashtable στον οποίο θέλεις να το βάλεις.

[migf1]

Εννοώ πως το τελευταίο % hashTableSize δεν είναι μέρος της hash function αλλά μέρος του implementation του hashtable (αν κάνεις google για τους όρους που αναφέρεις θα δεις ότι όντως αυτή η μεταβλητή δεν αναφέρεται πουθενά). Στο παράδειγμα που έδωσες η hash function στην πραγματικότητα είναι f(x) = x.

 

Ή για να το πω με άλλα λόγια, μια hash function για strings θα επιστρέψει πάντα την ίδια τιμή για το string "hello" ανεξάρτητα από το πόσο μεγάλος είναι ο hashtable στον οποίο θέλεις να το βάλεις.

 

Και πάλι δεν σε πιάνω. Ποιο είναι το πρόβλημα που η "hello" γίνεται hashed πάντα στο ίδιο slot; Αυτό είναι το ζητούμενο στην συντριπτική πλειοψηφία.

 

Επίσης πως είναι δυνατόν π.χ. το x % 256 να δίνει ίδιο αποτέλεσμα με π.χ. το x % 100;

[defacer]

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

 

Αυτή είναι η built-in hash function σε .ΝΕΤ. Όπως βλέπεις δεν παίρνει καμία παράμετρο, επομένως το μέγεθος του hashtable της είναι άγνωστο. Άρα δεν αποτελεί μέρος των υπολογισμών που κάνει η hash function.

 

Προκειμένου να αξιοποιηθεί το αποτέλεσμα της hash function, ο hash table το παίρνει και κάνει το modulo. Αλλά αυτό δεν κάνει το modulo μέρος της hash function.

 

Μου τελειώνουν οι τρόποι να το πω σιγά σιγά.

[albNik]

Επίσης πως είναι δυνατόν π.χ. το x % 256 να δίνει ίδιο αποτέλεσμα με π.χ. το x % 100;

 

6400 είναι κοινός πολλαπλασιαστής του 100 και 256

 

για καθε x<100

(6400*k+x)%100=(6400*k+x)%256

[migf1]

@defacer

 

Το .net μπορεί να υλοποιεί όπως θέλει την μέθοδο που ονομάζει Object.GetHashCode, όπως το ίδιο μπορεί να κάνει οποιοδήποτε framework.

 

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

 

@albnik:

 

Αναφέρεσαι σε εξαιρέσεις, αναφέρθηκα στον κανόνα (εκείνα τα "π.χ." το κάνουν νομίζω προφανές)

[defacer]

Update

 

Για να συμπληρώσω κάποια πράγματα και να είναι πιο εμφανές το γιατί έγραψα με bold παραπάνω. Λες:

 

Με δεδομένο πως ο αριθμός ταυτότητας έχει ένα γράμμα μπροστά από τον αριθμό, η πιο απλοϊκή προσέγγιση είναι να έχεις ένα hash-table με 24 slots, 1 για κάθε γράμμα.

 

Φάουλ. Αν θέλεις να χρησιμοποιήσεις τη γνώση που έχεις για τη δομή των δεδομένων που θα κάνεις hash, αυτό πρέπει να γίνει μέσα στην hash function, στοχεύοντας στο να είναι η έξοδός της ομαλά κατανεμημένη. Όπως λέει και το link:

 

In these cases, the uniformity criterion should hold for almost all typical subsets of entries that may be found in the table, not just for the global set of all possible entries.

 

Δηλαδή το uniformity καλό είναι να ισχύει για τις τιμές που θα χρησιμοποιήσεις στην πράξη, οπότε αν έχεις δεδομένα γι' αυτές το ιδανικό θα ήταν να τα χρησιμοποιήσεις μέσα στη hash function.

 

Σε καμία περίπτωση δεν πρόκειται να υπολογίσεις το hash table size χρησιμοποιώντας αυτά τα δεδομένα, μιας και το ζητούμενο από ένα hash table είναι η ταχύτητά του. Η οποία στη γενική περίπτωση εξαρτάται μόνο από το load factor και από τον τρόπο χειρισμού συγκρούσεων. Ο δεύτερος είναι σταθερός, οπότε μένει μόνο το load factor το οποίο και πάλι στη γενική περίπτωση εξαρτάται από το πλήθος των στοιχείων που έχουν μπει μέσα και το μέγεθος του πίνακα.

 

Επομένως είναι φανερό πως το μέγεθος του πίνακα πρέπει να εξαρτάται γενικά μόνο από το πόσα στοιχεία σκοπεύεις να βάλεις μέσα και όχι από τη μορφή που έχουν αυτά (δεν μας νοιάζει αν "το πρώτο byte έχει 24 πιθανές τιμές" -- μας νοιάζει μόνο το αν θα βάλουμε μέσα 10 αριθμούς ταυτότητας ή 10 εκατομμύρια).

 

Και update στο update, μιας και μόλις είδα την απο πάνω απάντηση: δεν πρόκειται να συνεχίσω αυτή τη συζήτηση. Μπορείς πάντα να την κάνεις εσύ με άλλους ή κι εγώ με άλλους.

[migf1]

Update

 

Για να συμπληρώσω κάποια πράγματα και να είναι πιο εμφανές το γιατί έγραψα με bold παραπάνω. Λες:

 

 

 

Φάουλ. Αν θέλεις να χρησιμοποιήσεις τη γνώση που έχεις για τη δομή των δεδομένων που θα κάνεις hash, αυτό πρέπει να γίνει μέσα στην hash function, στοχεύοντας στο να είναι η έξοδός της ομαλά κατανεμημένη. Σε καμία περίπτωση δεν πρόκειται να υπολογίσεις το hash table size χρησιμοποιώντας αυτά τα δεδομένα, μιας και το ζητούμενο από ένα hash table είναι η ταχύτητά του. Η οποία στη γενική περίπτωση εξαρτάται μόνο από το load factor και από τον τρόπο χειρισμού συγκρούσεων. Ο δεύτερος είναι σταθερός, οπότε μένει μόνο το load factor το οποίο και πάλι στη γενική περίπτωση εξαρτάται από το πλήθος των στοιχείων που έχουν μπει μέσα και το μέγεθος του πίνακα.

 

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

 

Και update στο update, μιας και μόλις είδα την απο πάνω απάντηση: δεν πρόκειται να συνεχίσω αυτή τη συζήτηση. Μπορείς πάντα να την κάνεις εσύ με άλλους ή κι εγώ με άλλους.

 

Το μόνο φάουλ που υπάρχει είναι πως εξομοιώνεις την γενική έννοια "hashing" με την εξειδικευμένη ένοια "uniform hashing" και κατόπιν προσπαθείς να επιχειρηματολογήσεις παίρνοντάς το ως δεδομένο.

 

Δεν είναι όμως.

[albNik]

Βασικά όλα τα ν<100 δίνουν ίδιο υπόλοιπο με 100 και 256.

 

Πάντως θα περίμενα από την GetHashCode του .ΝΕΤ να επιστέφει long. Με int32 είναι σχετικά μεγάλη η πιθανότητα δυο αντικείμενα να έχουν ίδιο hash.

To GetHashCode δεν εξασφαλίζει ισότητα, πρέπει να χρησιμοποιείται για πρώτο γρήγορο έλεγχο, μετά αν είναι ίδιο να γίνεται επιπλέον σύγκριση.

 

 

[defacer]

Πάντως θα περίμενα από την GetHashCode του .ΝΕΤ να επιστέφει long. Με int32 είναι σχετικά μεγάλη η πιθανότητα δυο αντικείμενα να έχουν ίδιο hash.

 

Σχετικά μεγάλη; Αν είναι uniform η hash function τότε βάσει του birthday paradox θα πρέπει να βάλεις μέσα περίπου 77Κ αντικείμενα για να έχεις 50% πιθανότητα για ένα collision.

 

To GetHashCode δεν εξασφαλίζει ισότητα, πρέπει να χρησιμοποιείται για πρώτο γρήγορο έλεγχο, μετά αν είναι ίδιο να γίνεται επιπλέον σύγκριση.

 

Αυτό ισχύει για όλες τις hash functions (εκτός πολύ ειδικών περιπτώσεων, π.χ. perfect hashing) λόγω του pigeonhole principle: το πεδίο τιμών της είναι ένα πεπερασμένο σύνολο, επομένως αν οι πιθανές είσοδοι είναι άπειρες (π.χ. strings) ή έστω απλά περισσότερες από το μέγεθος του συνόλου τότε δε μπορείς να κάνεις διαφορετικά.

[migf1]

Για να μην καταστραφεί άδικα κι αυτό το νήμα όπως τόσα άλλα, σε προηγούμενο ποστ έχω δώσει link από το algorithms archive, ειδικά για τα hash functions.

 

Δίνω ένα ακόμα που θεωρώ must-read για όποιον θέλει να ασχοληθεί με hahsing, από το Virginia Tech University: http://research.cs.vt.edu/AVresearch/hashing/index.php

 

To αν το μέγεθος του πίνακα έχει ή όχι σχέση με την επιλογή του hash-function, και το ανάποδο το αφήνω στην κρίση των ενδιαφερόμενων.

 

[defacer]

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

 

Μήπως, λέω μήπως, η σελίδα του Virginia Tech απευθύνεται σε εντελώς αρχάριους και γι' αυτό το λόγο κάποια πράγματα τα εξηγεί στο περίπου και όχι τόσο technically correctly;

 

http://research.cs.v...ntroduction.php

 

Hashing is a method for storing and retrieving records from a database. It lets you insert, delete, and search for records based on a search key value.

 

Μπα, η ιδέα μου θα είναι.