Collections, Maps and Iterators - Java - page 865

Display 16.9 Method Headings in the Map<K,V> Interface (part 3 of 3)

public void putAll(Map<? extends K,? extends V> mapToAdd) (Optional)

Adds all mappings of mapToAdd into the calling object's map.

public V remove (Object key) (Optional)

Removes the mapping for the specified key. If the key is not found in the map then null is
returned; otherwise the previous value for the key is returned.

Concrete Map Classes
The abstract class AbstractMap<K,V> is convenient for implementing the Map<K,V>
interface, just as the AbstractSet<T> class served the same purpose for the Set<T> inter-
face. When defining a derived class of AbstractMap<K,V> you need to define not just the
abstract methods but also all the methods you intend to use. It usually makes more sense
to use (or define derived classes of ) the HashMap<K,V> or TreeMap<K,V> classes, which
are derived classes of AbstractMap<K,V> and are full implementations of the Map<K,V>
interfaces. However, if you wish to implement your own map with your own data struc-
tures, then it would be appropriate to derive classes from AbstractMap<K,V> .
In this chapter we will focus only on the HashMap<K,V> class, which is a concrete imple-
mentation of the Map<K,V> interface. Internally, the class uses a hash table similar to what
we discussed in Chapter 15. Note that this class does not make any guarantee as to the
order of elements placed in the map. If you require order, then you should use the
TreeMap<K,V> class (which internally uses a tree to store its elements) or the LinkedHash-
Map<K,V> class, which uses a doubly linked list to maintain order inside a HashMap<K,V>
object. The LinkedHashMap<K,V> class is derived from the HashMap<K,V> class.
Knowing how hash tables operate is helpful in optimizing a program that uses a
HashMap . When we created a hash table in Chapter 15, we used a fixed-sized array
where each array entry referenced a linked list. A hash function mapped an input
value, like a String, to an index in the array. If the size of the array is much smaller
than the number of elements added, then there will be lots of collisions and execution
performance will be low. On the other hand, if the size of the array is much larger than
the number of elements added, then memory will be wasted. A similar tradeoff exists
with the HashMap<K,V> class. One of the constructors allows us to specify an initial
capacity and a load factor . The initial capacity specifies how many “buckets” exist in
the hash table. This would be analogous to the size of the array of the hash table. The
load factor is a number between 0 and 1. This variable specifies a percentage such that
if the number of elements added to the hash table exceeds the load factor, then the
capacity of the hash table will automatically increase. The default load factor is 0.75
and the default initial capacity is 16. This means that the capacity will be increased (by
roughly double) once 12 elements are added to the map. This process is called rehash-
ing and can be time consuming if you have a large number of elements in the map.

initial
capacity
load factor

rehashing