DOC PREVIEW
Penn CIT 594 - Using Maps

This preview shows page 1-2-3-26-27-28 out of 28 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 28 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 28 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 28 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 28 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 28 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 28 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 28 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Using MapsA simple map: HashtableExample use of a HashtableHashtable constructorsWhich constructor should you use?Hashtable constructors (again)The Collections frameworkThe Map interface IThe Map interface IIOptional operationsMap viewsMap.Entry: Interface for entrySet elementsConstructorsHazards IHazards IIFrom Hashtables to HashMapssynchronizedCopying objectsThe Cloneable interfaceThe SortedMap interfaceRequirements for SortedMapSortedMap Methods ISortedMap Methods IIThe TreeMap classTreeMap constructorsQuick summarySetsThe EndUsing Maps2A simple map: Hashtable•To create a Hashtable, use:import java.util.*;Hashtable table = new Hashtable();•To put things into a Hashtable, use:table.put(key, value);•To retrieve a value from a Hashtable, use:value = table.get(key);3Example use of a Hashtable import java.util.*;public class HashtableUser { public static void main(String[] args) { Hashtable table = new Hashtable(); table.put("one", "un"); table.put("two", "deux"); table.put("three", "trois"); System.out.println("two -> " + table.get("two")); System.out.println("deux -> " + table.get("deux")); }} two -> deuxdeux -> null4Hashtable constructors•Hashtable() –Constructs a new, empty Hashtable with a default capacity (11) and default load factor (0.75). •Hashtable(int initialCapacity) –Constructs a new, empty Hashtable with the specified initial capacity and the default load factor (0.75). •Hashtable(int initialCapacity, float loadFactor) –Constructs a new, empty Hashtable with the specified initial capacity and the specified load factor. •Hashtable(Map t) –Constructs a new Hashtable with the same mappings as the given Map.5Which constructor should you use?•This is basically a question of efficiency–A hash table that is mostly empty wastes space–If a hash table is nearly full, some searches may take a very long time•The initial capacity of a hash table is the number of entries that it can hold initially•The load factor is a measure of how full it is–A load factor of 75% is usually a good compromise–If the table gets fuller than the load factor, Java creates a new, larger hash table and rehashes everything–Rehashing is an expensive operation6Hashtable constructors (again)•Hashtable() –Use if the default values are good enough•Hashtable(int initialCapacity) –Use if you have some idea how many entries to expect–Try to ensure it won’t be more than 75% full–If space is not an issue, double or triple the size•Hashtable(int initialCapacity, float loadFactor) –Use if you are trying to be super efficient–Requires careful experimentation and tuning•Hashtable(Map t) –Use to make a Hashtable from some other map–Initial capacity = 2*(size of t), load factor = 0.757The Collections framework•Hashtable is an old (pre-Collections) class•Hashtable has been retrofitted to implement the Map interfaceCollectionSortedSetListSetSortedMapMapHashtable8The Map interface I•Basic operations:–Object put(Object key, Object value)•Returns the previous value associated with key, or null if there was no previous value–Object get(Object key)•Returns null if the key was not found•A return value of null may not mean the key was not found (some implementations of Map allow null keys and values)•Tests:–boolean containsKey(Object key)–boolean containsValue(Object value)•Warning: probably requires linear time!–boolean isEmpty()–boolean equals(Object o)•Returns true if o is also a map and has the same mappings9The Map interface II•Optional operations:–Object put(Object key, Object value)•(So you could implement an immutable map)–void putAll(Map t)•Adds the mappings from t to this map–void clear()–Object remove(Object key)•Returns the value that was associated with the key, or null•Other:–int size()•Returns the number of key-value mappings–int hashCode()•Returns a hash code value for this map10Optional operations•Question: How can a method declared in an interface be optional?•Answer: you have to implement it, but the implementation may be something like this: public void remove(Object key) throws UnsupportedOperationException { throw new UnsupportedOperationException();}•In fact, HashMap extends AbstractMap, which provides many of the map operations, and implements the optional operations like this11Map views• Set keySet() –Returns a set view of the keys contained in this map.• Collection values() –Returns a collection view of the values contained in this map–Can’t be a set—keys must be unique, but values may be repeated•Set entrySet() –Returns a set view of the mappings contained in this map.•A view is dynamic access into the Map–If you change the Map, the view changes–If you change the view, the Map changes•The Map interface does not provide any Iterators–However, there are iterators for the above Sets and Collections12Map.Entry: Interface for entrySet elements •public interface Entry { Object getKey( ); Object getValue( ); Object setValue(Object value);}•This is a small interface for working with the Collection returned by entrySet( )•Can get elements only from the Iterator, and they are only valid during the iteration13Constructors•Map is an interface, so it cannot require any constructors•However, Java always supplies:–A no-argument constructor for each Map type–A constructor that takes a Map argument, and copies its key-value pairs into the new Map •If you ever implement your own Map class, you should define these constructors–Defining your own Map class is easy:class MyMap implements Map { ... }–There are, however, a lot of methods to implement14Hazards I•In order for a Hashtable to work correctly,–equals must be defined properly on the keys–hashCode must be defined properly on the keys•This is not a problem if you use Strings for the keys (this is extremely common)•If you use objects of some other class as your keys, you must make sure equals and hashCode are properly defined•Note: equals and hashCode are properly defined for all of Java’s Maps; it’s the keys that you need to be careful with15Hazards II•You should use immutable objects (like Strings) as keys•If you put a value into a hash table with a mutable key, and you change the key, what happens?–Answer: Nothing good!•Special case #1: A map may not contain itself as a key•Special case #2: A map


View Full Document

Penn CIT 594 - Using Maps

Documents in this Course
Trees

Trees

17 pages

Searching

Searching

24 pages

Pruning

Pruning

11 pages

Arrays

Arrays

17 pages

Stacks

Stacks

30 pages

Recursion

Recursion

25 pages

Hashing

Hashing

24 pages

Recursion

Recursion

24 pages

Graphs

Graphs

25 pages

Storage

Storage

37 pages

Trees

Trees

21 pages

Arrays

Arrays

24 pages

Hashing

Hashing

24 pages

Recursion

Recursion

25 pages

Graphs

Graphs

23 pages

Graphs

Graphs

25 pages

Stacks

Stacks

25 pages

Recursion

Recursion

25 pages

Quicksort

Quicksort

21 pages

Quicksort

Quicksort

21 pages

Graphs

Graphs

25 pages

Recursion

Recursion

25 pages

Searching

Searching

24 pages

Counting

Counting

20 pages

HTML

HTML

18 pages

Recursion

Recursion

24 pages

Pruning

Pruning

11 pages

Graphs

Graphs

25 pages

Load more
Download Using Maps
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Using Maps and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Using Maps 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?