Changes to String.intern() in Java 7

intern() method of String class is used for internalizing Java String. It's a process of creating a String pool where String objects with equal values are stored only once.
You can look at this post for more details on the method.

There is no change in the contract of the method. So, from the perspective of usage of this method, it's still same. Changes are mainly around the implementation of String pool where interned strings are stored. Let's go in detail :

 

intern() method until Java 6

Until Java 6 (and even some of the early Java 7 releases) all interned strings were stored in PermGen (Permanent Generation) memory. This memory area is reserved for long lived objects such as classes and constant pools. PermGen has fixed size, so it can NOT be expanded at runtime. This means that careless usage of interning strings can result in problem. JVM specification refers to this memory area as Method Area.

 

intern() method in Java 7

String pool in Java 7 was relocated to heap. So method area is logically part of heap, link. This means fixed size limitation of Perm Gen is not an issue any more. So along with normal objects, interned Strings will also get stored in heap.

 

References :

http://www.oracle.com/technetwork/java/javase/8-whats-new-2157071.html
https://blogs.oracle.com/jonthecollector/entry/presenting_the_permanent_generation
http://java-performance.info/string-intern-in-java-6-7-8/
http://kevinboone.net/java_oddities.html
http://mfinocchiaro.files.wordpress.com/2008/07/java-virtual-machine-neutral.pdf
http://radar.oreilly.com/2011/09/java7-features.html
http://www.infoq.com/news/2013/12/Oracle-Tunes-Java-String
http://java-performance.info/changes-to-string-java-1-7-0_06/

PriorityQueue in Java

PriorityQueue is one of the queue implementation based on Heap. A (normal) queue follows first-in, first-out (FIFO) principle. So, the element waiting longest goes out next. But, PriorityQueue is a queue with priority and hence the element with highest need (or priority) goes next. It partially orders elements in the data structure which is weaker than sorted order.

I have discussed the heap data structure in a separate post (here). As discussed in the post; the elements can be ordered as per min-heap property or max-heap property. Elements can be ordered according to natural ordering or by the Comparator provided at the time of construction of the queue. Let's take a look at the simplest possible example. (Taken numbers from the heap post)

 import java.util.PriorityQueue;  
   
 public class PQDemo {  
      private static PriorityQueue<Integer> pq;  
   
      public static void main(String[] args) {  
           pq = new PriorityQueue<>(); //can pass Comparator in the argument 
           pq.offer(10);  
           pq.offer(45);  
           pq.offer(75);  
           pq.offer(70);  
           pq.offer(55);  
           pq.offer(90);  
           pq.offer(1001);  
   
           System.out.println(" Elements in the Priority Queue :" + pq.toString());  
             
           System.out.print(" Taking out elements from Priority Queue :");  
           while (!pq.isEmpty())  
                System.out.print(pq.poll() + ", ");  
      }  
 }  

Output:
Elements in the Priority Queue :[10, 45, 75, 70, 55, 90, 1001]
Taking out elements from Priority Queue :10, 45, 55, 70, 75, 90, 1001, 

Important Points from above program

• Normal iterator ( .toString()) doesn't print elements in sorted order. You need to use sort() method of Array class to sort it. (i.e. Arrays.sort(pq.toArray())
• poll() method removes elements from the queue in sorted order
• It is using default ordering technique (as provided in Integer class) and hence elements are stored in ascending order (Min-heap).
• No matter how many elements you put in above queue; the head will always have the smallest element.
• To use max-heap property; pq = new PriorityQueue<>(Collections.reverseOrder()); Check this post for details

 

API specification

[PriorityQueue<E> Java Doc - here]

Let's look at the specific details of the API:

1. It is an unbounded queue implementation and the default initial capacity is 11
2. offer() or add() inserts the specified element in the queue
3. poll() retrieves and removes the head of the queue, or returns null if the queue is empty
4. peek() retrieves the head of the queue but doesn't remove it. Returns null if queue is empty.
5. element() is similar to peek() with only exception that it throws exception if queue is empty.
6. remove() is similar to poll() with only exception that it throws exception if queue is empty.
7. size() returns number of elements in the queue.
8. This is not a thread safe API. So multiple threads should not access it concurrently.
9. Doesn't allow null elements. Putting null throws NullPointerException. 

that is it for now!!! keep posting your inputs. 

Using Comparator to change sort technique in Java

Java provides ability to sort an array (or collection ), if the contained type properly implements java.lang.Comparable<T> interface. If type is comparable; sort method from Arrays class can be used for sorting the container (array or collection). This same utility is used by Collections API as well. You can design a type keeping in mind a natural sorting techniques, but there could still be a possibility to sort it differently. In such scenario, it doesn't make sense to go back to the class and modify the definition of the method. Some time, it might not be even feasible (to modify the class)!

In this post, I will be mentioning how can we provide a different ordering technique (other than one provided by class). The approach discussed in the post is applicable for any type (inbuilt or custom); but to make it simpler, I have considered Java's inbuilt type, String. Let's start with an example :

 String[] country = { "India", "US", "France" };  
 Arrays.sort(country);  
 System.out.println(Arrays.toString(country));  
 // Output : [France, India, US]  

Above snippet is able to sort array of strings because String class implements Comparable interface (i.e. provides implementation of compareTo(..) method)
To sort collections; Collections.sort(..) can be used.

Providing Custom Comparison 

So default comparison provided by String class, sorts the array in ascending order. What if you have to sort the above array in descending order?
Now modifying the compareTo(..) method of the String class is out of question (ditto the case, if you using a type from a jar). 

This is where the need for alternative comparison or ordering technique arises. Java provides another interface java.util.Comparator<T> to impose ordering on some collection of objects. This interface has compare(..) method to compare two objects of same type. So, we can create a Comparator<String> instance and pass it to the sort method. 

 import java.util.Comparator;  
 public class MyComparator implements Comparator<String> {  
      @Override  
      public int compare(String o1, String o2) {  
           return o2.compareTo(o1);  
      }  
 }  

 MyComparator my = new MyComparator();  
 Arrays.sort(country, my);  
 System.out.println(Arrays.toString(country));  
 //Output : [US, India, France]  

Note that the compare method in MyComparator class is basically calling compareTo method provided by String class. It has just reversed the order to reverse sort the array.

Java provides an inbuilt method to sort a collection in reverse order. So we don't need to re-invent the wheel but we should be aware of the logic.
Arrays.sort(country, Collections.reverseOrder());

Above approach is bit verbose; we can use anonymous class to make it more compact.

 import java.util.Arrays;  
 import java.util.Comparator;  
 public class OverrideDefaultSort {  
      public static String[] reverseSort(String[] country) {  
           Comparator<String> c = new Comparator<String>() {  
                @Override  
                public int compare(String o1, String o2) {  
                     return o2.compareTo(o1);  
                }  
           };  
           Arrays.sort(country, c);  
           return country;  
      }  
      public static void main(String[] args) {  
           String[] country = { "India", "US", "France" };  
           String[] c = OverrideDefaultSort.reverseSort(country);  
           System.out.println("Reverse Ordering:" + Arrays.toString(c));  
      }  
 }  

Output:
Natural Orering:[France, India, US]
Reverse Ordering:[US, India, France]

So second argument of sort method can take any comparator. Also above code can be even compacted further and Comparator can be provided inline inside the sort method. Below snippet sorts the array by size (or length) of the String.

 Arrays.sort(country, new Comparator<String>(){  
   @Override  
   public int compare(String o1, String o2) {  
       return Integer.compare(o1.length(), o2.length());  
   }  
 });  

Output:
Sort by length:[US, India, France]

So, sort in as many ways as you may wish !!!