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.
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.
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.
java.util.Map<K, V> 1.2
java.util.Map.Entry<K, V> 1.2
java.util.HashMap<K, V> 1.2
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.SortedMap<K, V> 1.2
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
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
java.util.LinkedHashMap<K, V> 1.4
java.util.EnumSet<E extends Enum<E>> 5.0
java.util.EnumMap<K extends Enum<K>, V> 5.0
java.util.IdentityHashMap<K, V> 1.4
Core Java Related Interview Questions
|J2EE Interview Questions||Core Java Interview Questions|
|JDBC Interview Questions||JSP Interview Questions|
|Android Interview Questions||JavaServer Faces (JSF) Interview Questions|
|Java collections framework Interview Questions||Java 8 Interview Questions|
|Java Collections Interview Questions||Java Exception Handling Interview Questions|
|Java Concurrency Interview Questions||Java Serialization Interview Questions|
|Java Programmer Interview Questions||Java Inheritance Interview Questions|
|Java IO Interview Questions||Object Oriented Programming in PHP Interview Questions|
Core Java Tutorial
An Introduction To Java
The Java Programming Environment
Fundamental Programming Structures In Java
Objects And Classes
Interfaces And Inner Classes
User Interface Components With Swing
Deploying Applications And Applets
Exceptions, Logging, Assertions, And Debugging
All rights reserved © 2018 Wisdom IT Services India Pvt. Ltd
Wisdomjobs.com is one of the best job search sites in India.