The Map ADT and Hash Tables - University of Arizona

[Pages:41]The Map ADT and

Hash Tables

The Map ADT

?Map: An abstract data type where a value is "mapped" to a unique key

?Need a key and a value to insert new mappings

?Only need the key to find mappings ?Only need the key to remove mappings

2

Key and Value

?With Java generics, you need to specify ?the type of key ?the type of value

?Here the key type is String and the value type is BankAccount

Map accounts = new HashMap();

3

Put and get

?Add new mappings (a key mapped to a value):

Map accounts = new HashMap();

accounts.put("M", new BankAccount("Michel", 111.11)); accounts.put("G", new BankAccount("Georgie", 222.22)); accounts.put("R", new BankAccount("Daniel", 333.33));

BankAccount current = accounts.get("M");

assertEquals(111.11, current.getBalance(), 0.001);

assertEquals("Michel", current.getID());

current = accounts.get("R");

// What is current.getID()? _______________!

// What is current.getBalance()? __________!

4

keys must be unique

?put returns replaced value if key existed

?In this case, the mapping now has the same key mapped to a new value

?or returns null if the key does not exist

Map ranking = new HashMap();

assertNull(ranking.put(50, "Kim")); assertNull(ranking.put(25, "Li"));

// The key 25 is already in the map assertNotNull(ranking.put(25, "Any Name"));

5

remove

?remove will return false if key is not found

?return true if the mapping (the key-value pair) was successfully removed from the collection

assertTrue(accounts.remove("G")); assertFalse(accounts.remove("Not Here"));

6

get returns null

?get will return null if the key is not found

assertNotNull(accounts.get("M")); assertTrue(accounts.remove("M")); assertNull(accounts.get("M"));

7

Generic

?Can have different types of keys and values

?However, keys must implement Comparable and override equals (use Integer and String for key type)

Map ranking = new HashMap();

ranking.put(1, "Kim"); ranking.put(2, "Li"); ranking.put(3, "Sandeep"); assertEquals("Kim", ranking.get(1)); assertEquals("Li", ranking.get(2)); assertEquals("Sandeep", ranking.get(3)); assertNull(ranking.get(4));

assertNotNull(ranking.get(1));

assertTrue(ranking.remove(1));

assertNull(ranking.get(1));

8

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download