Monday, February 7, 2011
What is the difference between Synchronized Collection classes and Concurrent Collection Classes ? When to use what ?
JDK 1.5 introduce some good concurrent collections which is highly efficient for high volume , low latency system.
The synchronized collections classes, Hashtable and Vector, and the synchronized wrapper classes, Collections.synchronizedMap and Collections.synchronizedList, provide a basic conditionally thread-safe implementation of Map and List.
However, several factors make them unsuitable for use in highly concurrent applications -- their single collection-wide lock is an impediment to scalability and it often becomes necessary to lock a collection for a considerable time during iteration to prevent ConcurrentModificationExceptions.
The ConcurrentHashMap and CopyOnWriteArrayList implementations provide much higher concurrency while preserving thread safety, with some minor compromises in their promises to callers. ConcurrentHashMap and CopyOnWriteArrayList are not necessarily useful everywhere you might use HashMap or ArrayList, but are designed to optimize specific common situations. Many concurrent applications will benefit from their use.
So what is the difference between hashtable and ConcurrentHashMap , both can be used in multithreaded environment but once the size of hashtable becomes considerable large performance degrade because for iteration it has to be locked for longer duration.
Since ConcurrentHashMap indroduced concept of segmentation , how large it becomes only certain part of it get locked to provide thread safety so many other readers can still access map without waiting for iteration to complete.
In Summary ConcurrentHashMap only locked certain portion of Map while Hashtable lock full map while doing iteration.
As always comments , suggestions are welcome.
How HashMap works in Java
How HashMap works in Java or sometime how get method work in HashMap is common interview questions now days. Almost everybody who worked in Java knows what hashMap is, where to use hashMap or difference between hashtable and HashMap then why this interview question becomes so special? Because of the breadth and depth this question offers. It has become very popular java interview question in almost any senior or mid-senior level java interviews.
Questions start with simple statement
"Have you used HashMap before" or "What is HashMap? Why do we use it “
Almost everybody answers this with yes and then interviewee keep talking about common facts about hashMap like hashMap accpt null while hashtable doesn't, HashMap is not synchronized, hashMap is fast and so on along with basics like its stores key and value pairs etc.
This shows that person has used hashMap and quite familier with the funtionalities HashMap offers but interview takes a sharp turn from here and next set of follow up questions gets more detailed about fundamentals involved in hashmap. Interview here you and come back with questions like
"Do you Know how hashMap works in Java” or
"How does get () method of HashMap works in Java"
And then you get answers like I don't bother its standard Java API, you better look code on java; I can find it out in Google at any time etc.
But some interviewee definitely answer this and will say "HashMap works on principle of hashing, we have put () and get () method for storing and retrieving data from hashMap. When we pass an object to put () method to store it on hashMap, hashMap implementation calls
hashcode() method hashMap key object and by applying that hashcode on its own hashing funtion it identifies a bucket location for storing value object , important part here is HashMap stores both key+value in bucket which is essential to understand the retrieving logic. if people fails to recognize this and say it only stores Value in the bucket they will fail to explain the retrieving logic of any object stored in HashMap . This answer is very much acceptable and does make sense that interviewee has fair bit of knowledge how hashing works and how HashMap works in Java.
But this is just start of story and going forward when depth increases a little bit and when you put intervieww on scenarios every java developers faced day by day basis. So next question would be more likely about collision detection and collision resolution in HashMap e.g
"What will happen if two different objects have same hashcode?”
Now from here confusion starts some time interviewer will say that since Hashcode is equal objects are equal and HashMap will throw exception or not store it again etc. then you might want to remind them aobut equals and hashCode() contract that two unequal object in Java very much can have equal hashcode. Some will give up at this point and some will move ahead and say "Since hashcode () is same, bucket location would be same and collision occurs in hashMap, Since HashMap use a linked list to store in bucket, value object will be stored in next node of linked list." great this answer make sense to me though there could be some other collision resolution methods available this is simplest and HashMap does follow this.
But story does not end here and final questions interviewer ask like
"How will you retreive if two different objects have same hashcode?”
Hmmmmmmmmmmmmm
Interviewee will say we will call get() method and then HashMap uses keys hashcode to find out bucket location and retreives object but then you need to remind him that there are two objects are stored in same bucket , so they will say about traversal in linked list until we find the value object , then you ask how do you identify vlaue object because you don't value object to compare ,So until they know that HashMap stores both Key and Value in linked list node they won't be able to resolve this issue and will try and fail.
But those bunch of people who remember this key information will say that after finding bucket location , we will call keys.equals() method to identify correct node in linked list and return associated value object for that key in HashMap. Perfect this is the correct answer.
In many cases interviewee fails at this stage because they get confused between hashcode () and equals () and keys and values object in hashMap which is pretty obvious because they are dealing with the hashcode () in all previous questions and equals () come in picture only in case of retrieving value object from HashMap.
Some good developer point out here aht using immutable, final object with proper equals () and hashcode () implementation would act as perfect HashMap keys and improve perforance of hashMap by reducing collision. Immutablity also allows cacching there hashcode of different keys which makes overall retreival process very fast and suggest that String and various wrapper classes e.g Integer provided by Java Collection API are very good HashMap keys.
I like this question because of its depth and number of concept it touches indirectly, if you look at questions asked during interview this HashMap questions has verified
Concept of hashing
Collision resolution in HashMap
Use of equals () and hashCode () method and there importance?
Benefit of immutable object?
Just to summararize here are the answers which does makes sense for above questions
How HashMAp works in Java
HashMap works on principle of hashing, we have put () and get () method for storing and retrieving object form hashMap.When we pass an both key and value to put() method to store on HashMap, it uses key object hashcode() method to calculate hashcode and they by applying hashing on that hashcode it identifies bucket location for storing value object.
While retrieving it uses key object equals method to find out correct key value pair and return value object associated with that key. HashMap uses linked list in case of collision and object will be stored in next node of linked list.
Also hashMap stores both key+value tuple in every node of linked list.
What will happen if two different HashMap key objects have same hashcode?
They will be stored in same bucket but no next node of linked list. And keys equals () method will be used to identify correct key value pair in HashMap.
In terms of usage HashMap is very versatile and I have mostly used hashMap as cache in electronic trading application I have worked . Since finance domain used Java heavily and due to performance reason we need caching a lot HashMap comes as very handy there.
to check some article on hashMap see here
Wednesday, July 21, 2010
Behavioral Patterns - Iterator Pattern
Iterator should be implemented as an interface. This allows the user to implement it anyway its easier for him/her to return data.
We use iterators quite frequently in everyday life. For example, remote control of TV. Any remote control we use, either at home/hotel or at a friend's place, we just pick up the TV remote control and start pressing Up and Down or Forward and Back keys to iterate through the channels.
What sort of interface can Iterator be in case of Remote Controls?
/** | |
| public Channel nextChannel(int currentChannel); |
}// End of interface | |
The channel iterator is common for all the remote controls. It's like a specification implemented by all the remote control manufacturing companies.
/** | |||
| /** | ||
|
| Channel channel = new Channel(currentChannel+1); | |
| } |
|
|
| /** | ||
|
|
| Channel channel = new Channel(currentChannel-1); |
| } |
| |
}// End of class | |||
/** | |||
| private ChannelSurfer surfer; public RemoteControl() { | ||
|
| surfer = new ChannelSurfer(); | |
| } |
| |
| /** | ||
|
| return new Program(surfer.nextChannel()); | |
| } |
|
|
}// End of class | |||
We all know that every channel is associated to a program and it's basically the program and not the channel number which a user wants to see. And so, the implementation which returns a program for channels surfed.
This tells us that we can apply some logic before returning the elements through iterator. We can set rules. The Iterator here, can also be programmed to return the 'programs' straight away rather than returning the channels.
The common Java iterator is Enumeration which has implicit
hasMoreElements()
and nextElement() methods.
The benefits of Iterator are about their strength to provide a common interface for iterating through collections without bothering about underlying implementation.
Difference between Enumeration and Iterator
Use Iterator always.
One big difference between these two is (apart from what Pallav has already mentioned), iterator is fail-safe. If you are using an iterator to go through a collection you can be sure of no concurrent modifications in the underlying collection which may
happen in multi-threaded environments.
Well, apart from being an advantage this also is said to decrease performance by a tad. However, that's negligible. (Some amount of processing is involved in checking for modifications). If you see the docs it says about "well defined semantics" for the iterator, the fail-safe property adds to that.
-- Vinay Binny
Enumeration and Iterator are interfaces in java.util package.
Enumeration is the old Interface(for legacy classes like Hashtable).
Iterator is for the new classes like HashSet,HashMap..
Enumeration and Iterator are used to just count the no of elements and view it.
But Iterator has an additional method for deleting elements.
So when you intend to delete elements. you can go for the Iterator Interface.
-- Bava
All of the above are correct but we have forgotten about one thing - iterator is a design pattern and the purpose is to abstract looping. For example you have a class that loops thru Lists or ArraysLists so you used Enumeration. But suddenly another programmer made an Array (say String[]) that can only do for loop. Your enumeration is screwed I would say. So the strategy is to use Iterator. Now first you will have this method in your class:
//this is Loop.java
public void loopThis(Iterator iter){
while(iter.hasNext()){
Object obj = iter.next();
}
}
So you use it this way:
Loop loop = new Loop();
ArrayList daList = new ArrayList();
loop.loopThis(daList.keys().iterate());
Now this part is to show you haw to make an iterator out of a String[]
1. Make an Iterator Class
public class CustomIterator implements java.util.Iterator{
String[] arry;
int rowPosition = 0;
int lngth = 0;
public CustomIterator(String[] arry){
this.arry = arry;
this.lngth = arry.length;
}
public boolean hasNext(){
if(rowPosition >= lngth) return false;
else return true;
}
public Object next(){
Object obj = arry[rowPosition];
rowPosition++;
return obj;
}
public void remove(){
for(int i = rowPosition-1; i < (lngth -1); i++){
arry[i] = arry[i+1]; // move up data
}
arry[lngth-1] = null;
lngth--;
rowPosition--;
}
}
and here is how you do it:
Loop loop = new Loop();
ArrayList daList = new ArrayList();
loop.loopThis(daList.keys().iterate());
String[] str = new String[]{"1","2","3","4","5"};
CustomIterator iter = new CustomIterator(str);
loop.loopThis(iter);
-- Steve Torrefranca
Well, not really. What if I implement the iterator design pattern using the enumeration interface? The Iterator design pattern does'nt make it mandatory to implement a remove method. All it says is to give a iteration capability irrespective of the underlying collection. I'll make Custom Iterator implement Enumeration without the remove method. Now we've implemented the iterator design pattern using enumeration and the enumeration works fine. The eponymous iterator interface may have derived its name from the iterator pattern but does'nt mean that an Enumeration can use the iterator design pattern.
What is the advantage of using an Iterator compared to the get(index) method?
public class TestClass { public static void main(String[] args) { int len = 100000; LinkedList linkedLst = new LinkedList(); ArrayList arrayLst = new ArrayList(); for (int m =0; m!= len; m++) { int x = (int)Math.random(); linkedLst.add(x); arrayLst.add(x); } long t = System.currentTimeMillis(); for (int i = 0; i!=len; i++) { linkedLst.get(i); } t = System.currentTimeMillis() - t; System.out.println("LinkedList -- get(index) takes "+t +"(ms)"); t = System.currentTimeMillis(); for (Iterator itr = linkedLst.iterator(); itr.hasNext();) { itr.next(); } t = System.currentTimeMillis() - t; System.out.println("LinkedList -- Iterator takes "+t +"(ms)"); t = System.currentTimeMillis(); for (int i = 0; i!=len; i++) { arrayLst.get(i); } t = System.currentTimeMillis() - t; System.out.println("ArrayList -- get(index) takes "+t +"(ms)"); t = System.currentTimeMillis(); for (Iterator itr = arrayLst.iterator(); itr.hasNext();) { itr.next(); } t = System.currentTimeMillis() - t; System.out.println("ArrayList -- Iterator takes "+t +"(ms)"); } }LinkedList -- get(index) takes 25777(ms) LinkedList -- Iterator takes 0(ms) ArrayList -- get(index) takes 10(ms) ArrayList -- Iterator takes 10(ms)
... for (Integer i:linkedLst) { System.out.println(i); } ... for (Integer i:arrayLst) { System.out.println(i); }- Some Iterator implementations (including those of all the general purpose collection implementations provided by the JRE) may choose to throw ConcurrentModificationExceptionexception if this behavior is detected. Iterators that do this are known as fail-fast iterators, as they fail quickly and cleanly, rather that risking arbitrary, non-deterministic behavior at an undetermined time in the future.
- The get(index) method will return bad data that makes very difficult to identify the real problem.
Algorithms: Big-Oh Notation
How time and space grow as the amount of data increases
It's useful to estimate the cpu or memory resources an algorithm requires. This "complexity analysis" attempts to characterize the relationship between the number of data elements and resource usage (time or space) with a simple formula approximation. Many programmers have had ugly surprises when they moved from small test data to large data sets. This analysis will make you aware of potential problems.
Dominant Term
Big-Oh (the "O" stands for "order of") notation is concerned with what happens for very large values of N, therefore only the largest term in a polynomial is needed. All smaller terms are dropped.
For example, the number of operations in some sorts is N2 - N. For large values of N, the single N term is insignificant compared to N2, therefore one of these sorts would be described as an O(N2) algorithm.
Similarly, constant multipliers are ignored. So a O(4*N) algorithm is equivalent to O(N), which is how it should be written. Ultimately you want to pay attention to these multipliers in determining the performance, but for the first round of analysis using Big-Oh, you simply ignore constant factors.
Why Size Matters
Here is a table of typical cases, showing how many "operations" would be performed for various values of N. Logarithms to base 2 (as used here) are proportional to logarithms in other base, so this doesn't affect the big-oh formula.
| constant | logarithmic | linear | quadratic | cubic | ||
|---|---|---|---|---|---|---|
| n | O(1) | O(log N) | O(N) | O(N log N) | O(N2) | O(N3) |
| 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 2 | 1 | 1 | 2 | 2 | 4 | 8 |
| 4 | 1 | 2 | 4 | 8 | 16 | 64 |
| 8 | 1 | 3 | 8 | 24 | 64 | 512 |
| 16 | 1 | 4 | 16 | 64 | 256 | 4,096 |
| 1,024 | 1 | 10 | 1,024 | 10,240 | 1,048,576 | 1,073,741,824 |
| 1,048,576 | 1 | 20 | 1,048,576 | 20,971,520 | 1012 | 1016 |
Does anyone really have that much data?
It's quite common. For example, it's hard to find a digital camera that that has fewer than a million pixels (1 mega-pixel). These images are processed and displayed on the screen. The algorithms that do this had better not be O(N2)! If it took one microsecond (1 millionth of a second) to process each pixel, an O(N2) algorithm would take more than a week to finish processing a 1 megapixel image, and more than three months to process a 3 megapixel image (note the rate of increase is definitely not linear).
Another example is sound. CD audio samples are 16 bits, sampled 44,100 times per second for each of two channels. A typical 3 minute song consists of about 8 million data points. You had better choose the write algorithm to process this data.
A dictionary I've used for text analysis has about 125,000 entries. There's a big difference between a linear O(N), binary O(log N), or hash O(1) search.
Best, worst, and average cases
You should be clear about which cases big-oh notation describes. By default it usually refers to the average case, using random data. However, the characteristics for best, worst, and average cases can be very different, and the use of non-random data (often more realistic) data can have a big effect on some algorithms.
Why big-oh notation isn't always useful
Complexity analysis can be very useful, but there are problems with it too.
- Too hard to analyze. Many algorithms are simply too hard to analyze mathematically.
- Average case unknown. There may not be sufficient information to know what the most important "average" case really is, therefore analysis is impossible.
- Unknown constant. Both walking and traveling at the speed of light have a time-as-function-of-distance big-oh complexity of O(N). Altho they have the same big-oh characteristics, one is rather faster than the other. Big-oh analysis only tells you how it grows with the size of the problem, not how efficient it is.
- Small data sets. If there are no large amounts of data, algorithm efficiency may not be important.
Benchmarks are better
Big-oh notation can give very good ideas about performance for large amounts of data, but the only real way to know for sure is to actually try it with large data sets. There may be performance issues that are not taken into account by big-oh notation, eg, the effect on paging as virtual memory usage grows. Although benchmarks are better, they aren't feasible during the design process, so Big-Oh complexity analysis is the choice.
Typical big-oh values for common algorithms
Searching
Here is a table of typical cases.
| Type of Search | Big-Oh | Comments |
|---|---|---|
| Linear search array/ArrayList/LinkedList | O(N) | |
| Binary search sorted array/ArrayList | O(log N) | Requires sorted data. |
| Search balanced tree | O(log N) | |
| Search hash table | O(1) |
Other Typical Operations
| Algorithm | array ArrayList | LinkedList |
|---|---|---|
| access front | O(1) | O(1) |
| access back | O(1) | O(1) |
| access middle | O(1) | O(N) |
| insert at front | O(N) | O(1) |
| insert at back | O(1) | O(1) |
| insert in middle | O(N) | O(1) |
Sorting arrays/ArrayLists
Some sorting algorithms show variability in their Big-Oh performance. It is therefore interesting to look at their best, worst, and average performance. For this description "average" is applied to uniformly distributed values. The distribution of real values for any given application may be important in selecting a particular algorithm.
| Type of Sort | Best | Worst | Average | Comments |
|---|---|---|---|---|
| BubbleSort | O(N) | O(N2) | O(N2) | Not a good sort, except with ideal data. |
| Selection sort | O(N2) | O(N2) | O(N2) | Perhaps best of O(N2) sorts |
| QuickSort | O(N log N) | O(N2) | O(N log N) | Good, but it worst case is O(N2) |
| HeapSort | O(N log N) | O(N log N) | O(N log N) | Typically slower than QuickSort, but worst case is much better. |
Example - choosing a non-optimal algorithm
I had to sort a large array of numbers. The values were almost always already in order, and even when they weren't in order there was typically only one number that was out of order. Only rarely were the values completely disorganized. I used a bubble sort because it was O(1) for my "average" data. This was many years ago when CPUs were 1000 times slower. Today I would simply use the library sort for the amount of data I had because the difference in execution time would probably be unnoticed. However, there are always data sets which are so large that a choice of algorithms really matters.
Example - O(N3) surprise
I once wrote a text-processing program to solve some particular customer problem. After seeing how well it processed the test data, the customer produced real data, which I confidently ran the program on. The program froze -- the problem was that I had inadvertently used an O(N3) algorithm and there was no way it was going to finish in my lifetime. Fortunately, my reputation was restored when I was able to rewrite the offending algorithm within an hour and process the real data in under a minute. Still, it was a sobering experience, illustrating dangers in ignoring complexity analysis, using unrealistic test data, and giving customer demos.
Same Big-Oh, but big differences
Altho two algorithms have the same big-oh characteristics, they may differ by a factor of three (or more) in practical implementations. Remember that big-oh notation ignores constant overhead and constant factors. These can be substantial and can't be ignored in practical implementations.
Time-space tradeoffs
Sometimes it's possible to reduce execution time by using more space, or reduce space requirements by using a more time-intensive algorithm.
Thursday, July 15, 2010
Supercharging your HashMaps
There is plenty of content around that discuss the performance of the relative Java Collections classes, mostly in terms of adding and retrieving items and some of the specifics under the cover such as the effect of the initial capacity. HashMaps and HashSets are special cases that make heavy use of the Object.hashCode() contract and as such are particularly sensitive to the behaviour of that method.
This article was inspired by a couple of classes in the application I support at work. It has a couple of very large HashMaps, one containing several thousand properties and settings, and the other containing tens of thousands of translations. Since they are so pervasive their performance has a direct impact on the application, and since they are so large it was worth taking the time to see how they performed. From this I took a tangent to specifics affecting HashMap performance and the article below.
Firstly a recommendation: If you haven't read Joshua Bloch's Effective Java, you should. Much of the information below follows on from concepts in his book, but there is no replacement for the wealth contained in the book.
While looking at HashMaps, we will of course look at the effects on loading and retrieving data, but we'll also address the time to iterate the contents and combine the effects of the initial capacity at the same time. Having read the API, you are of course aware that the HashSet class is backed by a HashMap, which is why we cover one and not the other.
HashMaps With String Keys
Our HashMaps are keyed against either a String or Integer value, so I thought I would start with Strings.
Loading the Strings
I created three lists of random Strings containing 1,000 10,000 and 100,000 items. The Strings were from 5 to 10 characters long and all upper case.
The Strings values were loaded into an Array and the time taken to load them from the Array into the HashMap was measured for a variety of initial capacities and timed using something like this...
long start = System.nanoTime();
for (String key : array ) {
map.put(key, key);
}
System.out.println("Took " + (System.nanoTime() - start) / 1000000 + " ms");
| Key Size | Initial Capacity | Load time (ms) |
|---|---|---|
| 1000 | 10 | 4 |
| 1000 | 100 | 4 |
| 1000 | 1000 | 4 |
| 1000 | 10,000 | 4 |
| 1000 | 100,000 | 4 |
| 1000 | 1,000,000 | 4 |
| 10,000 | 10 | 20 |
| 10,000 | 100 | 20 |
| 10,000 | 1000 | 20 |
| 10,000 | 10,000 | 20 |
| 10,000 | 100,000 | 20 |
| 10,000 | 1,000,000 | 20 |
| 100,000 | 10 | 110 |
| 100,000 | 100 | 110 |
| 100,000 | 1000 | 110 |
| 100,000 | 10,000 | 110 |
| 100,000 | 100,000 | 110 |
| 100,000 | 1,000,000 | 110 |
| Table 1 - String key loading times | ||
These results are non-threatening and may even be a little faster than expected. It is certainly the case that you wouldn't think twice about putting 100,000 records in a HashMap if you knew it was going to take a tenth of a second to load.
Retrieving the Strings
Now that we have the data loaded, it isn't much good unless we can get it back out. Since HashMaps are renouned for their ability to return data quickly, we will start with that. Note that to make sure the time spent selecting an item doesn't affect our results, we will pick the first item from our initial list and load it repeatedly like this...
String searchKey = array[0];
long start = System.nanoTime();
for (int i = 0; i < LOOP_SIZE; i++) {
map.get(searchKey);
}
System.out.println("Took " + (System.nanoTime() - start) / 1000000 + " ms");| Key Size | Initial Capacity | Reads | Read time (ms) |
|---|---|---|---|
| 1000 | 10 | 100 million | ~2400 |
| 1000 | 100 | 100 million | ~2400 |
| 1000 | 1000 | 100 million | ~2400 |
| 1000 | 10,000 | 100 million | ~2400 |
| 1000 | 100,000 | 100 million | ~2400 |
| 1000 | 1,000,000 | 100 million | ~2400 |
| 10,000 | 10 | 100 million | ~2400 |
| 10,000 | 100 | 100 million | ~2400 |
| 10,000 | 1000 | 100 million | ~2400 |
| 10,000 | 10,000 | 100 million | ~2400 |
| 10,000 | 100,000 | 100 million | ~2400 |
| 10,000 | 1,000,000 | 100 million | ~2400 |
| 100,000 | 10 | 100 million | ~2400 |
| 100,000 | 100 | 100 million | ~2400 |
| 100,000 | 1000 | 100 million | ~2400 |
| 100,000 | 10,000 | 100 million | ~2400 |
| 100,000 | 100,000 | 100 million | ~2400 |
| 100,000 | 1,000,000 | 100 million | ~2400 |
| Table 2 - String key read times | |||
Once again I hope these results are non-threatening and pretty much as expected. Regardless of the size of the HashMap and the number of items it contains, the time taken to retrieve an item does not change. Note that 100 million reads is a fair amount of work for our HashMap to do, and is almost one operation for every millisecond in the day.
Iterating the Strings
The final piece of work to build our basic results is to test the amount of time taken to iterate the results. To get values that are visible, we iterate each set of keys depending on the number of items it contains, like this...
long start = System.nanoTime();
for (int i = 0; i < ITERATE_COUNT; i++) {
for (String string : map.keySet()) {
// This operation should be 'free', and the compiler
// should not be able to compile it out of the byte code.
string.hashCode();
}
}
System.out.println("Took " + (System.nanoTime() - start) / 1000000 + " ms");| Key Size | Initial Capacity | Iterations | Iteration Time (ms) |
|---|---|---|---|
| 1000 | 10 | 10,000 (x 1000) | ~510 |
| 1000 | 100 | 10,000 (x 1000) | ~510 |
| 1000 | 1000 | 10,000 (x 1000) | ~550 |
| 1000 | 10,000 | 10,000 (x 1000) | 1,100 |
| 1000 | 100,000 | 10,000 (x 1000) | 6,200 |
| 1000 | 1,000,000 | 10,000 (x 1000) | 50,000 |
| 10,000 | 10 | 1,000 (x 10,000) | ~520 |
| 10,000 | 100 | 1,000 (x 10,000) | ~520 |
| 10,000 | 1000 | 1,000 (x 10,000) | ~520 |
| 10,000 | 10,000 | 1,000 (x 10,000) | ~550 |
| 10,000 | 100,000 | 1,000 (x 10,000) | 1,200 |
| 10,000 | 1,000,000 | 1,000 (x 10,000) | |
| 100,000 | 10 | 100 (x 100,000) | 1800 |
| 100,000 | 100 | 100 (x 100,000) | 1800 |
| 100,000 | 1000 | 100 (x 100,000) | 1800 |
| 100,000 | 10,000 | 100 (x 100,000) | 1800 |
| 100,000 | 100,000 | 100 (x 100,000) | 1800 |
| 100,000 | 1,000,000 | 100 (x 100,000) | |
| Table 3 - String key iteration times | |||
Summarising Strings as Keys
Now that we have our baseline results using String as our keys, we can summarise:
- It is very fast to load String keys into a HashMap
- While the javadoc warns against making the initial capacity too small due to rehashing costs, this wasn't apparent in the results above.
- The 'read time' appears constant regardless of the number of items in the map or the current capacity. This is described in the HashMap API.
- The iteration time appears fairly constant unless the capacity is very large. This is described in the HashMap API too.
To be fair, the String class is a first class citizen in Java, and is able to make use of skilled design and specific treatment by the compiler. The largest help is that the String classes hashCode() method is lazy loaded and therefore cached. This was used in the iteration example since the hash code value had already been calculated and can therefore be reused without being recalculated, but it is also critical to the results we have seen so far, as we are about to discover.
HashMaps With Exotic Keys
While Strings and Integers are common choices as keys, it is often necessary to use classes that are more complicated, and the complicated nature of the class could relate directly to the behaviour of the HashMap utilising the class. Without trying to go overboard creating a class that incurs a cost while calculating its hash code, we will create a class that contains an array of primitive ints and provides a hash code based on the array contents.
The LargeHash Class
// This class is only designed to illustrate the cost of hashing.
// It is not for production use!
public class LargeHash {
private final int[] intValues;
public LargeHash (final int intValue) {
intValues = new int[1000];
for (int i = 0; i < intValues.length; i++) {
intValues[i] = intValue + i;
}
}
@Override
public int hashCode() {
final int prime = 31;
int result = 17;
result = prime * result + Arrays.hashCode(intValues);
return result;
}
@Override
public boolean equals (Object obj) {
if (this == obj )
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
final LargeHash other = (LargeHash) obj;
if (!Arrays.equals(intValues, other.intValues))
return false;
return true;
}
}The class is designed to be a HashMap key, and once an instance is created it has only limited functionality. The hashCode() and equals() methods were initially generated by Eclipse, and use methods from the Arrays helper class.
We will be performing the same operations of loading, reading and iterating a HashMap containing a large number of instances as keys, and the results are...
| Key Size | Initial Capacity | Load Time (ms) | Reads | Read Time (ms) | Iterations | Iteration Time (ms) | |||
|---|---|---|---|---|---|---|---|---|---|
| 1000 | 10 | 5 | 100 million | 275,000 * | 10,000 (x 1000) | 500 | |||
| 1000 | 100 | 5 | 100 million | 280,000 * | 10,000 (x 1000) | 500 | |||
| 1000 | 1000 | 4 | 100 million | 275,000 * | 10,000 (x 1000) | 500 | |||
| 1000 | 10,000 | 5 | 100 million | 280,000 * | 10,000 (x 1000) | 1100 | |||
| 1000 | 100,000 | 5 | 100 million | 275,000 * | 10,000 (x 1000) | 6200 ** | |||
| 1000 | 1,000,000 | 4 | 100 million | 275,000 * | 10,000 (x 1000) | 50,000 ** | |||
| 10,000 | 10 | 40 | 100 million | 280,000 * | 1000 (x 10,000) | 500 | |||
| 10,000 | 100 | 40 | 100 million | 280,000 * | 1000 (x 10,000) | 500 | |||
| 10,000 | 1000 | 40 | 100 million | 280,000 * | 1000 (x 10,000) | 520 | |||
| 10,000 | 10,000 | 42 | 100 million | 290,000 * | 1000 (x 10,000) | 520 | |||
| 10,000 | 100,000 | 43 | 100 million | 290,000 * | 1000 (x 10,000) | 1100 ** | |||
| 10,000 | 1,000,000 | 42 | 100 million | 280,000 * | 1000 (x 10,000) | 5800 ** | |||
| 100,000 | 10 | 350 | 100 million | 280,000 * | 100 (x 100,000) | 2100 | |||
| 100,000 | 100 | 350 | 100 million | 280,000 * | 100 (x 100,000) | 2100 | |||
| 100,000 | 1000 | 350 | 100 million | 280,000 * | 100 (x 100,000) | 2100 | |||
| 100,000 | 10,000 | 350 | 100 million | 280,000 * | 100 (x 100,000) | 2100 | |||
| 100,000 | 100,000 | 330 | 100 million | 280,000 * | 100 (x 100,000) | 2000 ** | |||
| 100,000 | 1,000,000 | 330 | 100 million | 280,000 * | 100 (x 100,000) | 2400 ** | |||
| * values are interpreted from repeated runs of 1 million reads ** See the afterthoughts... | |||||||||
| Table 4 - Simple LargeHash times | |||||||||
The LargeHash Behaviour
Firstly, the load time was larger but still not really noticeable. It took possibly twice as long, but twice 'not a hell of a lot' is still 'not much'. Interestingly, the API recommends setting the initial size to some realistic value to prevent incurring the cost of rehashing, but that cost doesn't appear in the results. It is possible that the initial capacity made a difference when we use 100,000 items in our Map, but not enough to provide any conclusive results.
The read time was obviously worse, to the extent that I decided to extrapolate the results rather than wait several minutes for each run to complete. This shows us that the hashCode() method is too important when used in HashMaps to be taken lightly, and consideration should be taken when choosing or designing a class that will be used as a hashed key. There is nothing incredibly wrong with the class itself, but when put under pressure it fails to perform and can cause a drag on the code.
Building a Responsible Key
The lesson to learn from the String class is that lazy loading and caching the hash value can have a dramatic effect on the read times, since this is crucial to the HashMap performance. This is particularly true when you have high high usage HashMaps like the ones in the introduction. Is important to not that the hash code cannot be cached if the instance state can change in a way that alters the hash code, which implies that the key should first be made immutable before the hash code can be lazy loaded.
The LargeHash class is almost immutable, since it doesn't require defensive copies of data coming in and no data is exposed. This means we are only required to make the class final to fulfil the immutable contract.
There a few options for lazy loading and caching the hash code, but we will copy the approach used in the String class. Since no synchronization is used it could lead to a race condition in which the hash code is set to different values, but immutable internal state protects us from this happening in this case. It is still possible for the hash code to be generated by more than thread, but once the value is set then it will be defined forever and we no longer worry about the value changing and do not suffer the cost of synchronization that is no longer required.
It is also important to note that the local variable 'h' is used throughout the method to ensure thread safety. Otherwise another thread could see the hash variable in an intermediate (non zero) state and return the incorrect value. The updated method looks like this...
@Override
// Style copied from String.hashCode()
public int hashCode() {
int h = hash;
if (h == 0) {
final int prime = 31;
h = 17;
h = prime * h + Arrays.hashCode(intValues);
hash = h;
}
return h;
}...and now has performance comparable to the String key while being all the more exotic in nature.
| Key Size | Initial Capacity | Load Time (ms) | Reads | Read Time (ms) | Iterations | Iteration Time (ms) | |||
|---|---|---|---|---|---|---|---|---|---|
| 1000 | 10 | 5 | 100 million | 2400 | 10,000 (x 1000) | 500 | |||
| 1000 | 100 | 5 | 100 million | 2400 | 10,000 (x 1000) | 500 | |||
| 1000 | 1000 | 5 | 100 million | 2400 | 10,000 (x 1000) | 500 | |||
| 1000 | 10,000 | 4 | 100 million | 2400 | 10,000 (x 1000) | 1100 | |||
| 1000 | 100,000 | 5 | 100 million | 2400 | 10,000 (x 1000) | 6200 ** | |||
| 1000 | 1,000,000 | 5 | 100 million | 2400 | 10,000 (x 1000) | 50,000 ** | |||
| 10,000 | 10 | 40 | 100 million | 2400 | 1000 (x 10,000) | 500 | |||
| 10,000 | 100 | 40 | 100 million | 2400 | 1000 (x 10,000) | 500 | |||
| 10,000 | 1000 | 42 | 100 million | 2400 | 1000 (x 10,000) | 500 | |||
| 10,000 | 10,000 | 40 | 100 million | 2400 | 1000 (x 10,000) | 500 | |||
| 10,000 | 100,000 | 40 | 100 million | 2400 | 1000 (x 10,000) | 1000 ** | |||
| 10,000 | 1,000,000 | 40 | 100 million | 2400 | 1000 (x 10,000) | 5800 ** | |||
| 100,000 | 10 | 350 | 100 million | 2400 | 100 (x 100,000) | 2000 | |||
| 100,000 | 100 | 350 | 100 million | 2400 | 100 (x 100,000) | 2000 | |||
| 100,000 | 1000 | 440 * | 100 million | 2400 | 100 (x 100,000) | 1800 * | |||
| 100,000 | 10,000 | 350 | 100 million | 2400 | 100 (x 100,000) | 2000 | |||
| 100,000 | 100,000 | 350 | 100 million | 2400 | 100 (x 100,000) | 2000 ** | |||
| 100,000 | 1,000,000 | 350 | 100 million | 2400 | 100 (x 100,000) | 2400 ** | |||
| * These values were a repeatable aberration ** See the afterthoughts... | |||||||||
| Table 5 - Optimised LargeHash times | |||||||||
In Conclusion
The hasCode() method matters. In fact I would extend that to state that all aspects of all contract methods matter. Joshua Bloch has plenty to say about the hashCode(), equals() and comparable() contracts, but when you consider that these methods are the backbone of large parts of the Java programming language, it may not be sufficient just to get the right. In critical places, the default hashing algorithm may not be enough.
While the API warns that making the initial size too small can incur an overhead due to rehashing when the capacity increases, this was not apparent in the tables above. The cost to iteration due to large capacities is easier to see. Therefore the data suggests that HashMaps should be initialised to a smaller size and definitely not overly large.
Afterthoughts
Unusual Iteration Times
Tables 4 and 5 show that the iteration time increases as the capacity increases, and we expected this result. What was unexpected were times that decreased when the Maps contained more entries.
I don't have much more to say about this than "gosh".
Actual Size
An interesting diversion is to look at the actual capacity of the HashMap. The internal size is always kept as a power of two, presumably for performance purposes, but it is also important to note that the 'power of two' property is enforced under the covers and certainly not exposed via the API. Therefore as a rule you should ignore it in your own code. One thing this means is that you shouldn't try to initialise HashMaps to an appropriate 'power of two' value as it is already done for you, but in doing so you may be actively harming yourself if the particulars are changed in later implementations.
The actual capacity is the smallest power of two that is greater than the initial capacity and greater than the number of items divided by the load factor. This second point is the reason that an initial capacity of 1000 would set the actual capacity to 1024 (is 2^10) but once this was 75% full (load factor 0.75) the capacity would be altered to 2048 (ie 2^11) as seen in Table 6.
While the actual capacity is not exposed directly, there are many ways to inspect the value and I found it easiest to attach a debugger to interrogate the HashMap instance.
| Key Size | Initial Capacity | Actual Capacity | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|
| 1000 | 10 | 2^11 | |||||||||
| 1000 | 100 | 2^11 | |||||||||
| 1000 | 1000 | 2^11 | |||||||||
| 1000 | 10,000 | 2^14 | |||||||||
| 1000 | 100,000 | 2^17 | |||||||||
| 1000 | 1,000,000 | 2^20 | |||||||||
| 10,000 | 10 | 2^14 | |||||||||
| 10,000 | 100 | 2^14 | |||||||||
| 10,000 | 1000 | 2^14 | |||||||||
| 10,000 | 10,000 | 2^14 | |||||||||
| 10,000 | 100,000 | 2^17 | |||||||||
| 10,000 | 1,000,000 | 2^20 | |||||||||
| 100,000 | 10 | 2^17 | |||||||||
| 100,000 | 100 | 2^17 | |||||||||
| 100,000 | 1000 | 2^17 | |||||||||
| 100,000 | 10,000 | 2^17 | |||||||||
| 100,000 | 100,000 | 2^17 | |||||||||
| 100,000 | 1,000,000 | 2^20 | |||||||||
| Table 6 - Actual capacities in the previous tests | |||||||||||
Iterating Map.Entry Sets
As a final aside, there are many articles that recommend iterating the Map.Entry set from HashMaps in preference to iterating the keys and then using the key to obtain the value. We already have the time required to iterate in the data above, and have also shown that the time to retrieve the value is constant, but we already knew that from the API.
long start = System.nanoTime();
for (int i = 0; i < ITERATE_COUNT; i++) {
for (Map.Entry entry : map.entrySet()) {
entry.getKey().hashCode();
}
}
System.out.println("Took " + (System.nanoTime() - start) / 1000000 + " ms"); While potentially faster, this code is less readable and would therefore need to be quite a bit faster to warrant adoption, so lets run the tests one last time...
| Key Size | Initial Capacity | Iterations | Get then Read * (ms) | Map.Entry (ms) | |
|---|---|---|---|---|---|
| 1000 | 10,000 | 10,000 (x 1000) | 1340 | 1330 | |
| 1000 | 100,000 | 10,000 (x 1000) | 6400 | 6400 | |
| 1000 | 1,000,000 | 10,000 (x 1000) | 50,000 | 50,000 | |
| 10,000 | 10,000 | 1,000 (x 10,000) | 740 | 700 | |
| 10,000 | 100,000 | 1,000 (x 10,000) | 1200 | 1200 | |
| 10,000 | 1,000,000 | 1,000 (x 10,000) | 6000 | 5900 | |
| 100,000 | 10,000 | 100 (x 100,000) | 2200 | 1900 | |
| 100,000 | 100,000 | 100 (x 100,000) | 2200 | 1500 | |
| 100,000 | 1,000,000 | 100 (x 100,000) | 2600 | 1900 | |
| * Times were calculated using the data from Tables 5 | |||||
| Table 7 - Map.Entry iteration times | |||||
The Map.Entry does show faster iteration times at the extreme end of the test data, but otherwise I'm not so convinced.
Code was output using the Java2Html plug-in for Eclipse using MyEclipse 6.5