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

Βασικά, θέλα να αποθηκεύσω μεγάλο όγκο δεδομένων σε μια από τις δομές της. Επειδή πρόκειται να πραγματοποιήσω αρκετές προσπελάσεις στα δεδομένα αυτά, με ενδοιαφέρει
να μάθω πώς διατάσσονται αυτά σε ένα αντικείmενο και πόσο θα μου κοστίσουν χρονικα!

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

Μπορείτε να μου συμπληρώσετε:

ArrayList: O(n)
SortedList : ?
HashTable: ?

Οι υπόλοιπες δεν με ενδοιαφέρουν.
Ευχαριστώ

Απ' όσο μπόρεσα να καταλάβω από το documentation της MSDN τα hashtables κάνουν chaining, άρα η προσπέλαση σε αυτά είναι O(1) (ή τέλος πάντων O(1+load_factor)).

Για τις sorted lists, η αναπαράσταση γίνεται με δυο λίστες, σορταρισμένες με το key. Η MSDN έχει στις εκάστοτε μεθόδους κάποιες λεπτομέρειες: η προσθήκη είναι O(n) worst case ή O(logn) για την εισαγωγή στο τέλος της λίστας (υποψιάζομαι όμως ότι το amortized cost θα είναι καλύτερο). To GetKey, GetByIndex κτλ. είναι O(1), οπότε αν κάνεις binary search μπορείς να κάνεις O(logn) (το οποίο φαίνεται ότι κάνει και το Contains, και γι' αυτό είναι κι αυτό O(logn)).

Αν κάνεις πολλές προσπελάσεις (και λίγες προσθήκες/διαγραφές), τα hashtables μάλλον είναι τα καλύτερα (O(1)), μετά τα SortedLists (Ο(logn)) και μετα τα ArrayLists (Ο(n) αν δεν ξέρεις το index και δεν είναι sorted).

mikem4600 wrote:

Απ' όσο μπόρεσα να καταλάβω από το documentation της MSDN τα hashtables κάνουν chaining, άρα η προσπέλαση σε αυτά είναι O(1) (ή τέλος πάντων O(1+load_factor)).

!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
ΜΠορείς να μου το εξηγήσεις αυτό!!! Το διάβασα και στο MSDN. Πώς είναι δυνατό?
Τί είναι το chaining!!!

Πάντως Insertions ¨εχω μόνο στην αρχή και deletions μόνο στο τέλος.Μόνο Αναζητήσεις έχω και μεταβολές(το οποίο όπως λέει πάλι Ο(1) είναι).

Κάτι άλλο:
Διάβαζα για την GetHashCode και λέει ότι δεν εξασφαλίζει μοναδικότητα.
Αν υποθέσω ότι αυτή χρησιμοποιεί το framework για να παράγει το hashcode του κλειδιού τοτε τί μου εγγυάται την μοναδικότητα της αναζήτησης?
Ή μήπως το κλειδί παίρνει αλλιώς hashcode?

Αν πρόκειται για objects που βασίζονται σε δικές σου κλάσεις, τότε είσαι υπεύθυνος να φτιάξεις εσύ τον αλγόριθμο.

Πάντως, το HashTable δεν χρησιμοποιεί το HashCode για να βρει τα data επακριβώς αλλά για να τα οργανώσει σε ομάδες, τα λεγόμενα HashBuckets. Έτσι, όταν ψάχνει κάτι, το κάνει narrow-down σε κάποιο HashBucket και κατόπιν να ψάχνει μέσα σε αυτό (μιας και το κουβεντιάζουμε, παρόμοια τεχνική χρησιμοποιεί και ο SQL Server όταν κάνει merge join). 

Άρα λοιπόν, αν πρόκειται να υλοποιήσεις έναν GetHashCode αλγόριθμο, πρέπει ανάλογα με τα data που έχει να βρεις έναν έξυπνο τρόπο να κατανέμονται σε ομάδες ώστε να έχεις μια καλή διασπορά. Όπως αντιλαμβάνεσαι, αν ο αλγόριθμος παράγει μοναδικά hash keys τότε δεν είναι κατάλληλος για το hash table γιατί τότε για κάθε item θα φτιάχνει κι ένα HashBucket, θα είναι κατάλληλος όμως για άλλα είδη αναζήτησης.

---

Vir prudens non contra ventum mingit

pontifikas wrote:

mikem4600 wrote: Απ' όσο μπόρεσα να καταλάβω από το documentation της MSDN τα hashtables κάνουν chaining, άρα η προσπέλαση σε αυτά είναι O(1) (ή τέλος πάντων O(1+load_factor)). !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! ΜΠορείς να μου το εξηγήσεις αυτό!!! Το διάβασα και στο MSDN. Πώς είναι δυνατό? Τί είναι το chaining!!! Πάντως Insertions ¨εχω μόνο στην αρχή και deletions μόνο στο τέλος.Μόνο Αναζητήσεις έχω και μεταβολές(το οποίο όπως λέει πάλι Ο(1) είναι).

To chaining είναι ένας από τους τρόπους αποθήκευσης στοιχείων σε hashtable (ένας άλλος είναι το open addressing).

Χοντρικά, τα hashtables χρησιμοποιούν μια συνάρτηση που λέγεται hash function. Αυτή παίρνει ως είσοδο ένα κλειδί (π.χ. ένα string) και το αντιστοιχεί με έναν ακέραιο στο διάστημα [1-n] (ιδανικά, με ισοπίθανο τρόπο). Τα hashtables χρησιμοποιούν ένα πίνακα μεγέθους n για την αποθήκευση των στοιχείων. Κάθε στοιχείο αποθηκεύεται στη θέση του πίνακα που αντιστοιχεί στο hash code του.

Η συνάρτηση αυτή υπολογίζεται σε O(1) και έχει την ιδιότητα να αντιστοιχεί πάντα το ίδιο κλειδί στον ίδιο ακέραιο. Αυτό όμως δεν σημαίνει, όπως παρατήρησες, ότι κάθε (διαφορετικό) κλειδί αντιστοιχεί σε διαφορετικό ακέραιο. Σε περίπτωση που υπάρχει conflict, δηλαδή δύο διαφορετικά κλειδιά πρέπει να αποθηκευτούν στην ίδια θέση του πίνακα (επειδή η hash function επέστρεψε τον ίδιο ακέραιο), τότε στο chaining χρησιμοποιείται μία λίστα (για τη συγκεκριμένη θέση του πίνακα), που λέγεται bucket. Οπότε δεν χρειάζεται (και δεν γίνεται) να παράγει η hash function μοναδικά αποτελέσματα για κάθε κλειδί (αφού σε αυτή την περίπτωση δεν θα χρειαζόμασταν τη hash function - και το κλειδί μοναδικό είναι).

Άρα ένα hashtable σε αυτή την περίπτωση είναι ουστιαστικά ένας πίνακας που κάθε κελί του είναι μια λίστα. Για να βρω ένα στοιχείο, υπολογίζω το hashcode του (με τη hash function, δηλ. σε O(1)) και αυτό μου υποδυκνείει τη θέση του πίνακα όπου βρίσκεται αποθηκευμένο το στοιχείο αυτό (και αυτό σε O(1) μπορώ να το προσπελάσω). Ιδανικά (δηλ. αν δεν υπάρχουν conflicts) έχω τελειώσει. Αν όμως έχουν συμβεί conflicts, στη θέση αυτή θα υπάρχουν πολλά στοιχεία (στη λίστα) και θα πρέπει να την ψάξω σειριακά (αφού ούτε ταξινομημένη είναι, ούτε τπτ). Αυτό θέλει χρόνο ανάλογο του βαθμού χρησιμοποίησης του hashtable (που ισούται με m/n όπου m τα στοιχεία που κρατάει το hashtable), δηλ. O(m/n). Συνολικά: O(1)+O(m/n)=O(1+m/n) (αυτό διότι δεν ξέρουμε αν 1 > m/n ή 1 < m/n).

Μερικά links:
http://www.sparknotes.com/cs/searching/hashtables/section1.html
http://en.wikipedia.org/wiki/Hash_table#Chaining
http://www.gamedev.net/reference/articles/article2066.asp

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

Να ρωτήσω κάτι.Από ότι κατάλαβα και από τα λεγόμεντα του kelman σε περίπτωση που σαν κλειδί, χρησιμοποιώ ένα αντικείμενο που υλοποιεί την GetHashCode κατά την προσθήκη στο table το hashing το κάνει το framework με δική του συνάρτηση.Σωστα?
Το hashing αυτό είναι ...μονοσήμαντο?

Και για να το φέρω στα μέτρα του προβλήματός μου, θέλω να αποθηκεύσω pixels εικόνας. Οι x,y συντεταγμένες αν τις γράψω στην μορφή:
(x.ToString()+"|"+y.ToString()) μου παράγει ένα string κλειδί, ουσιαστικά μοναδικό.
Θα έχω μονοσήμαντο hashing αν κάνω:

//Για το point (x,y)
//Φτοιάξε το κλειδί
string myKey = (x.ToString()+"|"+y.ToString());
//Πάρε το χρώμα.
Color myColor = myImage.GetPixel(x,y);
//Βάλε το χρώμα στο table
myHashTable.Add(myKey,myColor);

Συνήθως, κάνεις

myHashTable.Add(obj.GetHashCode, obj)

Φτιάχνεις τη κλάση σου, βάζεις ως members τα data που θες να αποθηκεύσεις και υλοποιείς τη μέθοδο GetHashCode

---

Vir prudens non contra ventum mingit

Νομίζω πως και οι δύο τρόποι καλοί είναι... Ο επίσημος είναι φυσικά του KelMan [myHashTable.Add(obj.GetHashCode, obj) σε δική σου τάξη] αλλά και αυτός με το string έχει σημαντικά πλεονεκτήματα, όπως το ότι τα strings έχουν ήδη GetHashCode μέθοδο και δεν χρειάζεται να φτιάξεις δική σου .

Από την άλλη, σκέφτομαι ότι αφού έχεις μια ορθογώνια εικόνα με γνωστό (πάνω-κάτω) μέγεθος, γιατί χρειάζεσαι hashtable και όχι έναν απλό δισδιάστατο πίνακα με τα χρώματα (ή, αν θες πράγματι να την χρησιμοποιήσεις ως εικόνα, κάτι μέσα από το System.Drawing) για να γλυτώσεις και την φασαρία με τα hashtables;

BTW, με εξαίρεση πολύ ειδικές, τετριμμένες περιπτώσεις, το hashing ΔΕΝ είναι μονοσήμαντο.