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 interfaceCopy constructorsThe SortedMap interfaceRequirements for SortedMapSortedMap Methods ISortedMap Methods IIThe TreeMap classTreeMap constructorsQuick summarySetsThe EndUsing Maps2A simple map: HashtableTo 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<String, String> table = new Hashtable<String, String>(); 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 constructorsHashtable() 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 loadF actor) 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 efficiencyA hash table that is mostly empty wastes spaceIf a hash table is nearly full, some searches may take a very long timeThe initial capacity of a hash table is the number of entries that it can hold initiallyThe load factor is a measure of how full it isA load factor of 75% is usually a good compromiseIf the table gets fuller than the load factor, Java creates a new, larger hash table and rehashes everythingRehashing is an expensive operation6Hashtable constructors (again)Hashtable() Use if the default values are good enoughHashtable(int initialCapacity) Use if you have some idea how many entries to expectTry to ensure it won’t be more than 75% fullIf space is not an issue, double or triple the sizeHashtable(int initialCapacity, float loa dFactor ) Use if you are trying to be super efficientRequires careful experimentation and tuningHashtable(Map<? extends K, ? extends V> t) Use to make a Hashtable from some other mapInitial capacity = 2*(size of t), load factor = 0.757The Collections frameworkHashtable is an old (pre-Collections) classHashtable has been retrofitted to implement the Map interfaceCollectionSortedSetListSetSortedMapMapHashtable8The Map interface IBasic operations:V put(K ke y, V value)Returns the previous value associated with key, or null if there was no previous valueV get(Object key)Returns null if the key was not foundA 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 IIOptional operations:V put(K key, V value)(So you could implement an immutable map)void putAll(Map t)Adds the mappings from t to this mapvoid clear()Object remove(Object key)Returns the value that was associated with the key, or nullOther:int size()Returns the number of key-value mappingsint hashCode()Returns a hash code value for this map10Optional operationsQuestion: 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 exactly this way11Map views Set<K> keySet() Returns a set view of the keys contained in this map. Collection<V> values() Returns a collection view of the values contained in this mapCan’t be a set—keys must be unique, but values may be repeatedSet<Map.Entry<K, V>> entrySet() Returns a set view of the mappings contained in this map.A view is dynamic access into the MapIf you change the Map, the view changesIf you change the view, the Map changesThe Map interface does not provide any IteratorsHowever, there are iterators for the above Sets and Collections12Map.Entry:Interface for entrySet elements public interface Entry { K getKey( ); V getValue( ); V setValue(V 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 iteration13ConstructorsMap is an interface, so it cannot require any constructorsHowever, Java always supplies:A no-argument constructor for each Map typeA 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 constructorsDefining your own Map class is easy:class MyMap implements Map { ... }There are, however, a lot of methods to implement14Hazards IIn order for a Hashtable to work correctly,equals must be defined properly on the keyshashCode must be defined properly on the keysThis 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 definedNote: equals and hashCode are properly defined for all of Java’s Maps; it’s the keys that you need to be careful with15Hazards IIYou should use immutable objects (like Strings) as keysIf 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
View Full Document