Queues and Deques Core Java

As we already discussed, a queue lets you efficiently add elements at the tail and remove elements from the head. A double ended queue or deque lets you efficiently add or remove elements at the head and tail. Adding elements in the middle is not supported. Java SE 6 introduced a Deque interface. It is implemented by the ArrayDeque and LinkedList classes, both of which provide deques whose size grows as needed.

java.util.Queue<E> 5.0

  • boolean add(E element)
  • boolean offer(E element)
    adds the given element to the tail of this deque and returns true, provided the queue is not full. If the queue is full, the first method throws an IllegalStateException, whereas the second method returns false
  • E remove()
  • E poll()
    removes and returns the element at the head of this queue, provided the queue is not empty. If the queue is empty, the first method throws a NoSuchElementException, whereas the second method returns null.
  • E element()
  • E peek()
    returns the element at the head of this queue without removing it, provided the queue is not empty. If the queue is empty, the first method throws a NoSuchElementException, whereas the second method returns null.

java.util.Deque<E> 6

  • void addFirst(E element)
  • void addLast(E element)
  • boolean offerFirst(E element)
  • boolean offerLast(E element)
    adds the given element to the head or tail of this deque. If the queue is full, the first two methods throw an IllegalStateException, whereas the last two methods return false.
  • E removeFirst()
  • E removeLast()
  • E pollFirst()
  • E pollLast() removes and returns the element at the head of this queue, provided the queue is not empty. If the queue is empty, the first two methods throw a NoSuchElementException, whereas the last two methods return null.
  • E getFirst()
  • E getLast()
  • E peekFirst()
  • E peekLast()
    returns the element at the head of this queue without removing it, provided the queue is not empty. If the queue is empty, the first two methods throw a No Such Element Exception, whereas the last two methods return null.

java.util.ArrayDeque<E> 6

  • ArrayDeque()
  • ArrayDeque(int initialCapacity)
    constructs unbounded deques with an initial capacity of 16 or the given initial capacity.

Priority Queues

A priority queue retrieves elements in sorted order after they were inserted in arbitrary order. That is, whenever you call the remove method, you get the smallest element currently in the priority queue. However, the priority queue does not sort all its elements. If you iterate over the elements, they are not necessarily sorted. The priority queue makes use of an elegant and efficient data structure, called a heap.

A heap is a self-organizing binary tree in which the add and remove operations cause the smallest element to gravitate to the root, without wasting time on sorting all elements. Just like a TreeSet, a priority queue can either hold elements of a class that implements the Comparable interface or a Comparator object you supply in the constructor.

A typical use for a priority queue is job scheduling. Each job has a priority. Jobs are added in random order. Whenever a new job can be started, the highest-priority job is removed from the queue. (Since it is traditional for priority 1 to be the “highest” priority, the remove operation yields the minimum element.)
Listing below shows a priority queue in action. Unlike iteration in a TreeSet, the iteration here does not visit the elements in sorted order. However, removal always yields the smallest remaining element.

PriorityQueueTest.java

java.util.PriorityQueue 5.0

  • PriorityQueue()
  • PriorityQueue(int initialCapacity)
    constructs a priority queue for storing Comparable objects.
  • PriorityQueue(int initialCapacity, Comparator<? super E> c)
    constructs a priority queue and uses the specified comparator for sorting its elements.

Maps
A set is a collection that lets you quickly find an existing element. However, to look up an element, you need to have an exact copy of the element to find. That isn’t a very common lookup usually, you have some key information, and you want to look up the associated element. The map data structure serves that purpose. A map stores key/value pairs. You can find a value if you provide the key. For example, you may store a table of employee records, where the keys are the employee IDs and the values are Employee objects. The Java library supplies two general-purpose implementations for maps: HashMap and TreeMap. Both classes implement the Map interface.

A hash map hashes the keys, and a tree map uses a total ordering on the keys to organize them in a search tree. The hash or comparison function is applied only to the keys. The values associated with the keys are not hashed or compared. Should you choose a hash map or a tree map? As with sets, hashing is a bit faster, and it is the preferred choice if you don’t need to visit the keys in sorted order.

Here is how you set up a hash map for storing employees:

Whenever you add an object to a map, you must supply a key as well. In our case, the key is a string, and the corresponding value is an Employee object. To retrieve an object, you must use (and, therefore, remember) the key.

If no information is stored in the map with the particular key specified, then get returns null. Keys must be unique. You cannot store two values with the same key. If you call the put method twice with the same key, then the second value replaces the first one. In fact, put returns the previous value stored with the key parameter.

The remove method removes an element with a given key from the map. The size method returns the number of entries in the map. The collections framework does not consider a map itself as a collection. (Other frameworks for data structures consider a map as a collection of pairs, or as a collection of values that is indexed by the keys.) However, you can obtain views of the map, objects that implement the Collection interface, or one of its subinterfaces.

There are three views: the set of keys, the collection of values (which is not a set), and the set of key/value pairs. The keys and key/value pairs form a set because there can be only one copy of a key in a map. The methods

return these three views. (The elements of the entry set are objects of the static inner class Map.Entry.) Note that the keySet is not a HashSet or TreeSet, but an object of some other class that implements the Set interface. The Set interface extends the Collection interface. Therefore, you can use a keySet as you would use any collection. For example, you can enumerate all keys of a map:

TIP: If you want to look at both keys and values, then you can avoid value lookups by enumerating the entries. Use the following code skeleton:

If you invoke the remove method of the iterator, you actually remove the key and its associated value from the map. However, you cannot add an element to the key set view. It makes no sense to add a key without also adding a value. If you try to invoke the add method, it throws an Unsupported Operation Exception. The entry set view has the same restriction, even though it would make conceptual sense to add a new key/value pair.

Listing below illustrates a map at work. We first add key/value pairs to a map. Then, we remove one key from the map, which removes its associated value as well. Next, we change the value that is associated with a key and call the get method to look up a value. Finally, we iterate through the entry set.

MapTest.java

java.util.Map<K, V> 1.2

  • V get(K key)
    gets the value associated with the key; returns the object associated with the key, or null if the key is not found in the map. The key may be null.
  • V put(K key, V value)
    puts the association of a key and a value into the map. If the key is already present, the new object replaces the old one previously associated with the key. This method returns the old value of the key, or null if the key was not previously present. The key may be null, but the value must not be null.
  • void putAll(Map<? extends K, ? extends V> entries)
    adds all entries from the specified map to this map.
  • boolean containsKey(Object key)
    returns true if the key is present in the map.
  • boolean containsValue(Object value)
    returns true if the value is present in the map.
  • Set<Map.Entry<K, V>> entrySet()
    returns a set view of Map.Entry objects, the key/value pairs in the map. You can remove elements from this set and they are removed from the map, but you cannot add any elements.
  • Set<K> keySet()
    returns a set view of all keys in the map. You can remove elements from this set and the keys and associated values are removed from the map, but you cannot add any elements.
  • Collection<V> values()
    returns a collection view of all values in the map. You can remove elements from this set and the removed value and its key are removed from the map, but you cannot add any elements

java.util.Map.Entry<K, V> 1.2

  • K getKey()
  • V getValue()
    returns the key or value of this entry.
  • V setValue(V newValue)
    changes the value in the associated map to the new value and returns the old value.

java.util.HashMap<K, V> 1.2

  • HashMap()
  • HashMap(int initialCapacity)
  • HashMap(int initialCapacity, float loadFactor)
  • constructs an empty hash map with the specified capacity and load factor (a number between 0.0 and 1.0 that determines at what percentage of fullness the hash table will be rehashed into a larger one). The default load factor is 0.75.

java.util.TreeMap<K,V> 1.2

  • TreeMap(Comparator<? super K> c)
    constructs a tree map and uses the specified comparator for sorting its keys.
  • TreeMap(Map<? extends K, ? extends V> entries)
    constructs a tree map and adds all entries from a map.
  • TreeMap(SortedMap<? extends K, ? extends V> entries)
    constructs a tree map, adds all entries from a sorted map, and uses the same element comparator as the given sorted map.

java.util.SortedMap<K, V> 1.2

  • Comparator<? super K> comparator()
    returns the comparator used for sorting the keys, or null if the keys are compared with the compareTo method of the Comparable interface.
  • K firstKey()
  • K lastKey()
    returns the smallest or largest key in the map.

Specialized Set and Map Classes
The collection class library has several map classes for specialized needs that we briefly discuss in this section.

Weak Hash Maps
The WeakHashMap class was designed to solve an interesting problem. What happens with a value whose key is no longer used anywhere in your program? Suppose the last reference to a key has gone away. Then, there is no longer any way to refer to the value object. But because no part of the program has the key any more, the key/value pair cannot be removed from the map. Why can’t the garbage collector remove it? Isn’t it the job of the garbage collector to remove unused objects?

Unfortunately, it isn’t quite so simple. The garbage collector traces live objects. As long as the map object is live, then all buckets in it are live and they won’t be reclaimed. Thus, your program should take care to remove unused values from long-lived maps. Or, you can use a WeakHashMap instead. This data structure cooperates with the garbage collector to remove key/value pairs when the only reference to the key is the one from the hash table entry.

Here are the inner workings of this mechanism. The WeakHashMap uses weak references to hold keys. A WeakReference object holds a reference to another object, in our case, a hash table key. Objects of this type are treated in a special way by the garbage collector. Normally, if the garbage collector finds that a particular object has no references to it, it simply reclaims the object. However, if the object is reachable only by a WeakReference, the garbage collector still reclaims the object, but it places the weak reference that led to it into a queue. The operations of the WeakHashMap periodically check that queue for newly arrived weak references. The arrival of a weak reference in the queue signifies that the key was no longer used by anyone and that it has been collected. The WeakHashMap then removes the associated entry.

Linked Hash Sets and Maps
Java SE 1.4 added classes LinkedHashSet and LinkedHashMap that remember in which order you inserted items. That way, you avoid the seemingly random order of items in a hash table. As entries are inserted into the table, they are joined in a doubly linked list .

A linked hash table

A linked hash table

For example, consider the following map insertions from Listing below:

Then, staff.keySet().iterator() enumerates the keys in this order:

and staff.values().iterator() enumerates the values in this order:

A linked hash map can alternatively use access order, not insertion order, to iterate through the map entries. Every time you call get or put, the affected entry is removed from its current position and placed at the end of the linked list of entries. (Only the position in the linked list of entries is affected, not the hash table bucket. An entry always stays in the bucket that corresponds to the hash code of the key.) To construct such a hash map, call

Access order is useful for implementing a “least recently used” discipline for a cache. For example, you may want to keep frequently accessed entries in memory and read less frequently accessed objects from a database. When you don’t find an entry in the table, and the table is already pretty full, then you can get an iterator into the table and remove the first few elements that it enumerates. Those entries were the least recently used ones. You can even automate that process. Form a subclass of LinkedHashMap and override the method

Adding a new entry then causes the eldest entry to be removed whenever your method returns true. For example, the following cache is kept at a size of at most 100 elements:

Alternatively, you can consider the eldest entry to decide whether to remove it. For example, you may want to check a time stamp stored with the entry.

Enumeration Sets and Maps

The EnumSet is an efficient set implementation with elements that belong to an enumerated type. Because an enumerated type has a finite number of instances, the EnumSet is internally implemented simply as a sequence of bits. A bit is turned on if the corresponding value is present in the set. The EnumSet class has no public constructors. You use a static factory method to construct the set:

You can use the usual methods of the Set interface to modify an EnumSet. An EnumMap is a map with keys that belong to an enumerated type. It is simply and efficiently implemented as an array of values. You need to specify the key type in the constructor:

NOTE: In the API documentation for EnumSet, you will see odd-looking type parameters of the form E extends Enum<E>. This simply means “E is an enumerated type.” All enumerated types extend the generic Enum class. For example,

Identity Hash Maps

Java SE 1.4 added another class IdentityHashMap for another quite specialized purpose, where the hash values for the keys should not be computed by the hashCode method but by the System.identityHashCode method. That’s the method that Object.hashCode uses to compute a hash code from the object’s memory address. Also, for comparison of objects, the

In other words, different key objects are considered distinct even if they have equal contents. This class is useful for implementing object traversal algorithms (such as object serialization), in which you want to keep track of which objects have already been traversed.

java.util.WeakHashMap<K, V> 1.2

  • WeakHashMap()
  • WeakHashMap(int initialCapacity)
  • WeakHashMap(int initialCapacity, float loadFactor) constructs an empty hash map with the specified capacity and load factor.

java.util.LinkedHashSet<E> 1.4

  • LinkedHashSet()
  • LinkedHashSet(int initialCapacity)
  • LinkedHashSet(int initialCapacity, float loadFactor)
    constructs an empty linked hash set with the specified capacity and load factor.

java.util.LinkedHashMap<K, V> 1.4

  • LinkedHashMap()
  • LinkedHashMap(int initialCapacity)
  • LinkedHashMap(int initialCapacity, float loadFactor)
  • LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder)
    constructs an empty linked hash map with the specified capacity, load factor, and ordering. The accessOrder parameter is true for access order, false for insertion order.
  • protected boolean removeEldestEntry(Map.Entry<K, V> eldest)
    should be overridden to return true if you want the eldest entry to be removed. The eldest parameter is the entry whose removal is being contemplated. This method is called after an entry has been added to the map. The default implementation returns false old elements are not removed by default. However, you can redefine this method to selectively return true; for example, if the eldest entry fits a certain condition or the map exceeds a certain size.

java.util.EnumSet<E extends Enum<E>> 5.0

  • static <E extends Enum<E>> EnumSet<E> allOf(Class<E> enumType)
    returns a set that contains all values of the given enumerated type.
  • static <E extends Enum<E>> EnumSet<E> noneOf(Class<E> enumType)
    returns an empty set, capable of holding values of the given enumerated type.
  • static <E extends Enum<E>> EnumSet<E> range(E from, E to)
    returns a set that contains all values between from and to (inclusive).
  • static <E extends Enum<E>> EnumSet<E> of(E value)
  • static <E extends Enum<E>> EnumSet<E> of(E value, E... values)
    returns a set that contains the given values.

java.util.EnumMap<K extends Enum<K>, V> 5.0

  • EnumMap(Class<K> keyType)
    constructs an empty map whose keys have the given type.

java.util.IdentityHashMap<K, V> 1.4

  • IdentityHashMap()
  • IdentityHashMap(int expectedMaxSize)
    constructs an empty identity hash map whose capacity is the smallest power of 2 exceeding 1.5 * expectedMaxSize. (The default for expectedMaxSize is 21.)

java.lang.System 1.0

  • static int identityHashCode(Object obj) 1.1
    returns the same hash code (derived from the object’s memory address) that Object.hashCode computes, even if the class to which obj belongs has redefined the hashCode method.

All rights reserved © 2018 Wisdom IT Services India Pvt. Ltd DMCA.com Protection Status

Core Java Topics