The collections api - Data Structures and Problem Solving Using Java - page 274

1 public static List<String> listDuplicates( List<String> coll )
2 {
3 Map<String,Integer> count = new TreeMap<String,Integer>( );
4 List<String> result = new ArrayList<String>( );
5
6 for( String word : coll )
7 {
8 Integer occurs = count.get( word );
9 if( occurs == null )
10 count.put( word, 1 );
11 else
12 count.put( word, occurs + 1 );
13 }
14
15 for( Map.Entry<String,Integer> e : count.entrySet( ) )
16 if( e.getValue( ) >= 2 )
17 result.add( e.getKey( ) );
18
19 return result;
20 }

figure 6.39
A typical use of a map

placed in the map, we do so with a count of 1. Otherwise, we update the
count. Note the judicious use of autoboxing and unboxing. Then at lines 15-17,
we use an iterator to traverse through the entry set, obtaining keys that appear
with a count of two or more in the map.

priority queues

6.9

Although jobs sent to a printer are generally placed on a queue, that might not
always be the best thing to do. For instance, one job might be particularly
important, so we might want to allow that job to be run as soon as the printer
is available. Conversely, when the printer finishes a job, and several 1-page
jobs and one 100-page job are waiting, it might be reasonable to print the long
job last, even if it is not the last job submitted. (Unfortunately, most systems
do not do this, which can be particularly annoying at times.)
Similarly, in a multiuser environment the operating system scheduler
must decide which of several processes to run. Generally, a process is allowed
to run only for a fixed period of time. A poor algorithm for such a procedure
involves use of a queue. Jobs are initially placed at the end of the queue. The
scheduler repeatedly takes the first job from the queue, runs it until either it
finishes or its time limit is up, and places it at the end of the queue if it does
not finish. Generally, this strategy is not appropriate because short jobs must

The priority queue
supports access of
the minimum item
only.