5η Διάλεξη

Διάλεξη 21/3

Κατακερματισμός (hashing) II

(διαφάνειες U. Zwick [20-54] από μάθημα Advanced Algorithms, Tel Aviv University): 

• Επιθυμητές ιδιότητες. Καθολικότητα και k-ανεξαρτησία. Carter-Wegman Universal hash family. 
• Ανάλυση χρόνου βασικών πράξεων στην κλειστή και ανοιχτή διεθυνσιοδότηση.
• Μέθοδοι διερεύνησης στην ανοιχτή διευθυνσιοδότηση: γραμμική, τετραγωνική, διπλός κατακερματισμός.
• Τέλειος κατακερματισμός (perfect hashing). Κατακερματισμός κούκου (Cuckoo hashing). 

Προτεινόμενη μελέτη: σημειώσεις (και αναφορές που περιέχονται).