Design Pattern - Factory Pattern
I am working on some simple AWS lambda functions now. To get the better performance, I decide to get rid of Spring framework in most of them as they are simple and straightforward. But without having a mature framework, it should be more carefully as I need to implement several methodologies by myself instead of using things provided by the framework. So, I decide to refresh my knowledge of the basics, like common design patterns in object oriented programming. I am going to talk about a few design patterns by summarizing the resources I found, putting my own thoughts and including some Java code examples in the next few posts.
Today, I am going to start our journey with Factory Pattern.
Why the size of Hashmap is power of 2 in Java
As we know, the Hashmap is implemented by a bucket of linked lists or red-black trees. However, when we look into the source code of Hashmap in Java 8, there are interesting comments on attributes related to the size of bucket, e.g. DEFAULT_INITIAL_CAPACITY and MAXIMUM_CAPACITY. It is said these values MUST be a power of two.
So, what’s the reason that the bucket size of a Hashmap has to be a number, which is power of two?
Count Inversions in an Array
This problem was asked by Google.
We can determine how “out of order” an array A is by counting the number of inversions it has. Two elements A[i] and A[j] form an inversion if A[i] > A[j] but i < j. That is, a smaller element appears after a larger element.
Given an array, count the number of inversions it has. Do this faster than \(O(n^2)\) time.
The Secret Improvement of HashMap in Java 8
HashMap is one of the most widely used data structure in Java. As we know, HashMap stores data in a number of buckets and each bucket is a linked list. The new elements will be added into the bucket at index of \((n - 1)\,\&\,hash\) (n is the current capacity in HashMap). When the size of a single linked list increases, the performance of retrievals gets worse. Java 8 improves the performance by converting the linked list into a Red-black Tree if the size is bigger than a threshold. I am going to talk about the basics of red-black tree and how Java applies this methodology in HashMap.