Πίνακας κατακερματισμού

Στην επιστήμη υπολογιστών, ο Πίνακας Κατακερματισμού (Αγγλικά: 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.