Unit 10: Maps PDF

✎ Unit 10: Maps Unit Objectives. Here you will: learn about when to use map explore some concrete implementations of map in the JCF ✔ SHS Wong DSA 10.Maps 1/22 ✎...

✎ Unit 10: Maps Unit Objectives. Here you will: learn about when to use map explore some concrete implementations of map in the JCF ✔ SHS Wong DSA 10.Maps 1/22 ✎ The Map ADT... maps keys to values. ➠ Each key is mapped with one value. SHS Wong DSA 10.Maps 2/22 ✎ The Map ADT... maps keys to values. ➠ Each key is mapped with one value. Set of key−value pairs K1 V1 K3 V5 K2 V2 K4 V4 K5 V5 K6 V6 Also known as dictionary, associative array and lookup table. SHS Wong DSA 10.Maps 2/22 ✎ The Map ADT... maps keys to values. Typical operations includes: ➠ Each key is mapped with one value. ⋄ Add: Associate a new value Set of key−value pairs with a new key. K1 V1 K3 V5 K2 V2 K4 V4 K5 V5 K6 V6 Also known as dictionary, associative array and lookup table. SHS Wong DSA 10.Maps 2/22 ✎ The Map ADT... maps keys to values. Typical operations includes: ➠ Each key is mapped with one value. ⋄ Add: Associate a new value Set of key−value pairs with a new key. K1 V1 ⋄ Reassign: Associate an K3 V5 existing key in the map with K2 V2 a new value. K4 V4 K5 V5 K6 V6 Also known as dictionary, associative array and lookup table. SHS Wong DSA 10.Maps 2/22 ✎ The Map ADT... maps keys to values. Typical operations includes: ➠ Each key is mapped with one value. ⋄ Add: Associate a new value Set of key−value pairs with a new key. K1 V1 ⋄ Reassign: Associate an K3 V5 existing key in the map with K2 V2 a new value. K4 V4 K5 V5 ⋄ Remove: Remove a key with its associated value from the K6 V6 key set in the map. Also known as dictionary, associative array and lookup table. SHS Wong DSA 10.Maps 2/22 ✎ The Map ADT... maps keys to values. Typical operations includes: ➠ Each key is mapped with one value. ⋄ Add: Associate a new value Set of key−value pairs with a new key. K1 V1 ⋄ Reassign: Associate an K3 V5 existing key in the map with K2 V2 a new value. K4 V4 K5 V5 ⋄ Remove: Remove a key with its associated value from the K6 V6 key set in the map. Also known as dictionary, ⋄ Lookup: Find the value (if associative array and lookup any) that is associated with a ✔ table. key. SHS Wong DSA 10.Maps 2/22 ✎ When would maps be useful? to model the contents of a dictionary to model the contents of a phone book to provide various indexing for a table of database records ✔ SHS Wong DSA 10.Maps 3/22 ✎ Modelling dictionary contents using Map Consider the data in a dictionary entry, e.g.: Source: Cambridge Dictionary Online How to model the dictionary entry in Java? public class LexicalEntry { ✔ private String word; private POS pos; private String glossary; private BLOB usPronounciation; private BLOB ukPronounciation; } SHS Wong DSA 10.Maps 4/22 ✎ Modelling dictionary contents using Map Consider the data in a dictionary entry, e.g.: Source: Cambridge Dictionary Online How to model the dictionary entry in Java? ✔ Define a Java class named Entry. SHS Wong DSA 10.Maps 4/22 ✎ Modelling dictionary contents using Map What kind of fields should class Entry have? ✔ Which field should be used as the key? SHS Wong DSA 10.Maps 5/22 ✎ Modelling dictionary contents using Map What kind of fields should class Entry have? 1 public class Entry { 2 private String word; 3 private POS pos; // part-of-speech, e.g. noun 4 private Pronunciation pronunciation; 5 private String meaning; 6 7 // other details omitted 8 } 9 10 enum POS { 11 PRONOUN, NOUN, VERB, ADJECTIVE, ADVERB, PREPOSITION 12 } ✔ Which field should be used as the key? SHS Wong DSA 10.Maps 5/22 ✎ Modelling dictionary contents using Map What kind of fields should class Entry have? 1 public class Entry { 2 private String word; 3 private POS pos; // part-of-speech, e.g. noun 4 private Pronunciation pronunciation; 5 private String meaning; 6 7 // other details omitted 8 } 9 10 enum POS { 11 PRONOUN, NOUN, VERB, ADJECTIVE, ADVERB, PREPOSITION 12 } ✔ Which field should be used as the key? word SHS Wong DSA 10.Maps 5/22 ✎ Modelling dictionary contents using Map How to model the following kind of dictionary contents to facilitate efficient dictionary lookup? Source: Cambridge Dictionary Online What would be the key and value? How to model a dictionary with 5, 000 entries in Java? ✔ SHS Wong DSA 10.Maps 6/22 ✎ Modelling dictionary contents using Map How to model the following kind of dictionary contents to facilitate efficient dictionary lookup? Source: Cambridge Dictionary Online What would be the key and value? K = word to be looked up, V = dictionary entry How to model a dictionary with 5, 000 entries in Java? ✔ SHS Wong DSA 10.Maps 6/22 ✎ Modelling dictionary contents using Map How to model the following kind of dictionary contents to facilitate efficient dictionary lookup? Source: Cambridge Dictionary Online What would be the key and value? K = word to be looked up, V = dictionary entry How to model a dictionary with 5, 000 entries in Java? Map dictionary = ✔ new HashMap(7500); SHS Wong DSA 10.Maps 6/22 ✎ Modelling contents of a phone book Consider the following data in a phone book entry, e.g.: How to model the phone book entry in Java? ✔ SHS Wong DSA 10.Maps 7/22 ✎ Modelling contents of a phone book Consider the following data in a phone book entry, e.g.: How to model the phone book entry in Java? ✔ Define a Java class named Contact. SHS Wong DSA 10.Maps 7/22 ✎ Modelling contents of a phone book What fields should class Contact have? Which field should be used as the key? ✔ SHS Wong DSA 10.Maps 8/22 ✎ Modelling contents of a phone book What fields should class Contact have? 1 public class Contact { 2 3 private String name; 4 private Address address; 5 private String phone; 6 private String url; 7 8 // other details omitted 9 10 } Which field should be used as the key? ✔ SHS Wong DSA 10.Maps 8/22 ✎ Modelling contents of a phone book What fields should class Contact have? 1 public class Contact { 2 3 private String name; 4 private Address address; 5 private String phone; 6 private String url; 7 8 // other details omitted 9 10 } Which field should be used as the key? ✔ name SHS Wong DSA 10.Maps 8/22 ✎ Modelling contents of a phone book How to model a phone book with contact information such as the below to facilitate efficient lookup? What would be the key and value? How to model the data in a phone book in Java? ✔ SHS Wong DSA 10.Maps 9/22 ✎ Modelling contents of a phone book How to model a phone book with contact information such as the below to facilitate efficient lookup? What would be the key and value? K = name of person/organisation, V = correspondence detail How to model the data in a phone book in Java? ✔ SHS Wong DSA 10.Maps 9/22 ✎ Modelling contents of a phone book How to model a phone book with contact information such as the below to facilitate efficient lookup? What would be the key and value? K = name of person/organisation, V = correspondence detail How to model the data in a phone book in Java? Map phoneBook = new HashMap(); ✔ SHS Wong DSA 10.Maps 9/22 ✎ Indexing database records Consider the following Supplier table: Source: http://c2.com/cgi/wiki?SupplierPartsDatabase How to model a supplier record in Java? ✔ SHS Wong DSA 10.Maps 10/22 ✎ Indexing database records Consider the following Supplier table: Source: http://c2.com/cgi/wiki?SupplierPartsDatabase How to model a supplier record in Java? ✔ Define a Java class named Supplier. SHS Wong DSA 10.Maps 10/22 ✎ Indexing database records What fields should class Supplier have? 1 public class Supplier { 2 3 private String id; 4 private String name; 5 private int status; 6 private String city; 7 8 // other details omitted 9 ✔ 10 } SHS Wong DSA 10.Maps 11/22 ✎ Indexing database records With the following supplier table: Source: http://c2.com/cgi/wiki?SupplierPartsDatabase How to model the records in a supplier table such as the below to facilitate efficient efficient search over the supplier’s: 1. name (SNAME), or 2. location (CITY)? ✔ ➡ A means to facilitate search is by indexing data. SHS Wong DSA 10.Maps 12/22 ✎ Indexing database records With the following supplier table: Source: http://c2.com/cgi/wiki?SupplierPartsDatabase How to model the records in a supplier table such as the below to facilitate efficient efficient search over the supplier’s: 1. name (SNAME), or 2. location (CITY)? Use HashMap to index the data in the supplier table. ✔ ➡ A means to facilitate search is by indexing data. SHS Wong DSA 10.Maps 12/22 ✎ Indexing database records We will need two maps... What would be the key and value? How to model the required indexing in Java? ✔ SHS Wong DSA 10.Maps 13/22 ✎ Indexing database records We will need two maps... What would be the key and value? 1. K = data in SNAME, V = supplier record 2. K = data in CITY, V = supplier records How to model the required indexing in Java? ✔ SHS Wong DSA 10.Maps 13/22 ✎ Indexing database records We will need two maps... What would be the key and value? 1. K = data in SNAME, V = supplier record 2. K = data in CITY, V = supplier records How to model the required indexing in Java? Map suppliersByName = new java.util.HashMap(); Map suppliersByCity = new java.util.TreeMap(); ✔ SHS Wong DSA 10.Maps 13/22 ✎ Potential Implementations of Map What sort of structure does each element in a map have? SHS Wong DSA 10.Maps 14/22 ✎ Potential Implementations of Map What sort of structure does each element in a map have? Answer: Each element in a map is an entry of key-value pair. SHS Wong DSA 10.Maps 14/22 ✎ Potential Implementations of Map What sort of structure does each element in a map have? Answer: Each element in a map is an entry of key-value pair. Which implementation of map is more efficient? ⋄ array ⋄ linked list, i.e. a linear linked structure ⋄ tree, i.e. a hierarchical linked structure ⋄ hash table ✔ SHS Wong DSA 10.Maps 14/22 ✎ The Map interface in JCF The java.util package includes the interface Map. A map is a mapping from a finite set of keys to values. Each key is mapped to a single value. Given a key, one can look up the corresponding value from a map. SHS Wong DSA 10.Maps 15/22 ✎ The Map interface in JCF The java.util package includes the interface Map. A map is a mapping from a finite set of keys to values. Each key is mapped to a single value. Given a key, one can look up the corresponding value from a map. New key-value pairs can be added to a map. Existing key-value pairs can be removed from the map. ✔ SHS Wong DSA 10.Maps 15/22 ✎ Some Methods in the Map interface in JCF The main methods defined in the Map interface are: V get(Object key) ➠ Returns the value to which the specified key is mapped. (Look up) SHS Wong DSA 10.Maps 16/22 ✎ Some Methods in the Map interface in JCF The main methods defined in the Map interface are: V get(Object key) ➠ Returns the value to which the specified key is mapped. (Look up) V put(K key, V value) ➠ Associates the specified value with the specified key (Reassign) ➠ If the key is not yet in the map, add a new key-value mapping. (Add) SHS Wong DSA 10.Maps 16/22 ✎ Some Methods in the Map interface in JCF The main methods defined in the Map interface are: V get(Object key) ➠ Returns the value to which the specified key is mapped. (Look up) V put(K key, V value) ➠ Associates the specified value with the specified key (Reassign) ➠ If the key is not yet in the map, add a new key-value mapping. (Add) V remove(Object key) ➠ Removes the mapping for a key. (Remove) ✔ SHS Wong DSA 10.Maps 16/22 ✎ Concrete Implementations of Map in JCF The main implementations of Map are: ⋄ HashMap – hash table implementation of map. ➠ Used when the order of the data in the map is irrelevant, e.g. for storing data in an electronic dictionary. SHS Wong DSA 10.Maps 17/22 ✎ Concrete Implementations of Map in JCF The main implementations of Map are: ⋄ HashMap – hash table implementation of map. ➠ Used when the order of the data in the map is irrelevant, e.g. for storing data in an electronic dictionary. ⋄ ConcurrentHashMap – a thread-safe, hash table implementation of map that supports concurrent operations. SHS Wong DSA 10.Maps 17/22 ✎ Concrete Implementations of Map in JCF The main implementations of Map are: ⋄ HashMap – hash table implementation of map. ➠ Used when the order of the data in the map is irrelevant, e.g. for storing data in an electronic dictionary. ⋄ ConcurrentHashMap – a thread-safe, hash table implementation of map that supports concurrent operations. ⋄ TreeMap – an ordered map, ordered by the natural order of keys. ➠ Used when the data in the map need to be ordered, e.g. for storing data in a dictionary for printing a paper dictionary: private TreeMap dictionary; ✔ SHS Wong DSA 10.Maps 17/22 ✎ How to Iterate over Map? java.util.Map does not extends the interface Iterable. ➟ Hence, an enhanced-for statement cannot be used to iterate over the contents of a Map object. SHS Wong DSA 10.Maps 18/22 ✎ How to Iterate over Map? java.util.Map does not extends the interface Iterable. ➟ Hence, an enhanced-for statement cannot be used to iterate over the contents of a Map object. Map provides convenient methods for obtaining the contents of the map: ⋄ Set keySet(): Returns a set of the keys contained in this map. ⋄ Set entrySet(): Returns a set of key-to-value mappings contained in this map. ⋄ Collection values(): Returns a collection of the values contained in this map. ➡ The collection can contain the same object more than once. Why? SHS Wong DSA 10.Maps 18/22 ✎ How to Iterate over Map? java.util.Map does not extends the interface Iterable. ➟ Hence, an enhanced-for statement cannot be used to iterate over the contents of a Map object. Map provides convenient methods for obtaining the contents of the map: ⋄ Set keySet(): Returns a set of the keys contained in this map. ⋄ Set entrySet(): Returns a set of key-to-value mappings contained in this map. ⋄ Collection values(): Returns a collection of the values contained in this map. ➡ The collection can contain the same object more than once. Why? ➟ An enhanced-for statement can be used to iterate through the ✔ returned data: Set and Collection. SHS Wong DSA 10.Maps 18/22 ✎ Different keys may be mapped to the same value Set of key−value pairs K1 V1 K3 V3 K2 V2 K4 V4 K5 V1 K6 V2 ✔ Different keys can be mapped to the same value. SHS Wong DSA 10.Maps 19/22 ✎ Iterating over Map: An Example 1 public void results() { 2 System.out.println(raffle.title() + "\nThe winners are... "); 3 4 // Get info about who has won what. 5 Map winners = raffle.luckyDraw(); 6 7 9 for (Map.Entry map : winners.entrySet()) { 10 11 Prize prize = map.getKey(); // the prize 12 Ticket winner = map.getValue(); // the winning ticket 13 14 System.out.println(prize.toString() + " goes to " + 15 winner.buyer()); 16 } 17 System.out.println("Many Congratulations!!"); 18 } ✔ See the lucky draw eclipse Java project in Lab 2 for details. SHS Wong DSA 10.Maps 20/22 ✎ Iterating over Map: Another Example 1 public void results() { 2 System.out.println(raffle.title() + "\nThe winners are... "); 3 4 // Get info about who has won what. 5 Map winners = raffle.luckyDraw(); 6 7 9 for (Prize prize : winners.keySet()) { 10 11 // the winning ticket 12 Ticket winner = winners.get(prize); 13 14 System.out.println(prize.toString() + " goes to " + 15 winner.buyer()); 16 } 17 System.out.println("Many Congratulations!!"); ✔ 18 } SHS Wong DSA 10.Maps 21/22 ✎ Learning Outcomes Learning Outcomes. You should now be able to: identify when to use map use some implementations of map in JCF to solove a computing problem appropriately explain the difference between the data structure hash table and the ADT map SHS Wong DSA 10.Maps 22/22