Πίνακας κατακερματισμού: Διαφορά μεταξύ των αναθεωρήσεων
μ Ρομπότ: Προσθήκη: ml:ഹാഷ് ടേബിൾ |
μ r2.7.1) (Ρομπότ: Προσθήκη: ko:해시 테이블 |
||
Γραμμή 20: | Γραμμή 20: | ||
[[et:Paisktabel]] |
[[et:Paisktabel]] |
||
[[fa:جدول درهمسازی]] |
[[fa:جدول درهمسازی]] |
||
⚫ | |||
[[fr:Table de hachage]] |
[[fr:Table de hachage]] |
||
⚫ | |||
[[hr:Hash tablica]] |
[[hr:Hash tablica]] |
||
[[hu:Hash tábla]] |
|||
[[it:Hash table]] |
[[it:Hash table]] |
||
⚫ | |||
⚫ | |||
[[ |
[[ko:해시 테이블]] |
||
[[lt:Dėstymo lentelė]] |
[[lt:Dėstymo lentelė]] |
||
[[ |
[[lv:Heštabula]] |
||
[[ml:ഹാഷ് ടേബിൾ]] |
[[ml:ഹാഷ് ടേബിൾ]] |
||
[[nl:Hashtabel]] |
[[nl:Hashtabel]] |
||
⚫ | |||
⚫ | |||
[[nn:Hashtabell]] |
[[nn:Hashtabell]] |
||
⚫ | |||
[[pl:Tablica mieszająca]] |
[[pl:Tablica mieszająca]] |
||
[[pt:Tabela de dispersão]] |
[[pt:Tabela de dispersão]] |
||
Γραμμή 38: | Γραμμή 40: | ||
[[sk:Hašovacia tabuľka]] |
[[sk:Hašovacia tabuľka]] |
||
[[sr:Хеш табела]] |
[[sr:Хеш табела]] |
||
⚫ | |||
[[sv:Hashtabell]] |
[[sv:Hashtabell]] |
||
[[th:ตารางแฮช]] |
[[th:ตารางแฮช]] |
Έκδοση από την 06:20, 26 Ιανουαρίου 2013
Στην επιστήμη υπολογιστών, ο Πίνακας Κατακερματισμού (Αγγλικά: Hash table) είναι μία δομή δεδομένων για την αποθήκευση συνόλων στοιχείων. Χαρακτηριστικό του πίνακα κατακερματισμού είναι ότι μπορεί να εκτελέσει σε σταθερό χρόνο, δηλαδή με πολυπλοκότητα Ο(1), τις λειτουργίες της εισαγωγής, αναζήτησης και διαγραφής στοιχείων.
Η κατασκευή του βασίζεται στη δομή πίνακα και στον ορισμό μίας συνάρτησης κατακερματισμού. Η συνάρτηση αυτή ορίζει για κάθε στοιχείο που εισάγεται έναν "κωδικό" που καθορίζει με μοναδικό τρόπο την θέση αποθήκευσης του στοιχείου αυτού στον πίνακα. Η συνάρτηση κατακερματισμού δεν είναι ένα-προς-ένα δηλαδή, παρότι σε όλα τα στοιχεία που είναι ίσα αποδίδεται πάντα ο ίδιος κωδικός, μπορεί διαφορετικά στοιχεία να έχουν και πάλι τον ίδιο κωδικό, με άμεσο αποτέλεσμα, κατά την εισαγωγή τους, να πρέπει να καταλήξουν στην ίδια θέση του πίνακα. Τέτοιες περιπτώσεις ονομάζονται συγκρούσεις (Αγγλικά: collisions) και έχουν αναπτυχθεί διάφοροι τρόποι αντιμετώπισής τους, όπως η χρήση συνδεδεμένων λιστών.
Στην γλώσσα προγραμματισμού Java η κλάση που υλοποιεί τον πίνακα κατακερματισμού είναι η HashMap, ενώ μια παλαιότερη υλοποίησή του είναι η κλάση Hashtable.
Παραπομπές
- Cormen, Thomas H. (2003). Introduction to Algorithms. MIT Press. σελίδες 205–213 & 501–505. ISBN 0-262-03293-7. Unknown parameter
|coauthors=
ignored (|author=
suggested) (βοήθεια)