tailieunhanh - Data Structures and Algorithms: Maps and Dictionaries

Data Structures and Algorithms: Maps and Dictionaries presents Maps & Dictionaries, The Map ADT, Dictionary ADT, Implement Dictionary ADT, Hash Tables, Hash Functions and Hash Tables, Hash Codes, Compression Functions. | Maps and Dictionaries Data structures and Algorithms Acknowledgement: These slides are adapted from slides provided with Data Structures and Algorithms in C++ Goodrich, Tamassia and Mount (Wiley, 2004) Outline Maps () Hash tables () Dictionaries () Maps and Dictionaries 2 Maps & Dictionaries Map ADT and Dictionary ADT: model a searchable collection of key-value entries main operations are searching, inserting, and deleting entries Map: multiple entries with the same key are not allowed Map applications: Dictionary: multiple entries with the same key are allowed Dictionary applications: address book student-record database word-definition pairs credit card authorizations DNS mapping of host names (., ) to internet IP addresses (., ) Maps and Dictionaries 3 Maps Maps and Dictionaries 4 The Map ADT Map ADT methods: get(k): if the map M has an entry with key k, return its associated value; else, return null put(k, v): insert entry (k, v) into the map M; if key k is not already in M, then return null; else, return old value associated with k remove(k): if the map M has an entry with key k, remove it from M and return its associated value; else, return null size(), isEmpty() keys(): return an iterator of the keys in M values(): return an iterator of the values in M Maps and .