Home

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?

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.

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.

Find the largest K element in an array is a common code challenge in interviews. You may see this problem in several different formats like K Closest Points to the Origin.

Sorting the whole given array can solve this problem in time complexity of \(O(n\,log\,n)\) and space complexity of \(O(n)\). However, there is another efficient solution, which has a huge improvement of space complexity when K is small, through an import data structure - Heap.