in java collections interview map hash map ~ read.

Java interview for developer. Collections. Part 2 - Maps.

This is new part of java interview questions.
Here is part one.

7. How does HashMap work?

I suppose this is the second most popular question on Java collections. I even don't remember interview, where I wasn't asked for this question.

Let's look on HashMap briefly. HashMap consists of "buckets". Technically, every "bucket" is just an element of the array, where links to lists are stored. When a new element adds to hashmap, its hash code is calculated. Using some specific rules this hashcode defines "bucket" (array element), where we should place new element. If at this moment "bucket" is empty, then link to the new element will be stored, otherwise we start to scan all elements in the list one by one, until we find the last element. Link to new element will be attached to last element in the list. In case in list was found element we the same key as in added element, then existing element will be replaced with new element.

Add, remove and search of elements in hashmap require constant time to perform. This is perfect result, but it works only if the hash-function steady placed elements in buckets. In this case, the worst time complexity for add, remove and search will be lg N (this statement was greatly discussed, when I first time publish this post, so I gave some explanation why it is look so), and in average case it will be constant time.

In common, this info will be enough to answer this question. You can expect more question about deeper understanding of processes in HashMap.

8. What is initial amount of buckets in HashMap?

The answer is 16. But, this amount could be changed in case of using non default constructor: using parameter 'capacity' initial amount of buckets could be changed.

9. What is time-complexity of searching element in HasMap? Does HashMap guarantee this time-complexity?

The answer for the first question could be found in asnwer #7. The answer for the second question is not so complex. For example, if you will use the hash-function that returns the same value any time it's called, then all records will be placed in single bucket. What does it mean? It means that now you have all elements in a single linked list, with accordinal time-complexity. So you could answer that HashMap does not guarantee time-complexity.

10. How functions equals and hashCode are used in logic of HashMap?

The answer for this question is also could be found from answer #7, but let's write an answer explicity. hashCode() function allows to find out bucket to go for the element and equals is used for comparing key of element that should be found in the bucket and all elements stored in the list inside the bucket.

11. What is range of returned values of function hashCode()?

Answer for this question is very easy, you just need to know type of returning value: int hashCode(). So, it means that the number of values equals to range in int (2^32 values).

12. In what case number of buckets will be increased in HashMap? How doest it happen?

This question really needs from you some deep knowledge of internal processes in a HashMap. May be you know about parameter 'loadFactor' in a HashMap. 'loadFactor' defines upper limit of not empty buckets by the formula: capacity * loadFactor. By default, loadFactor = 0.75. When number of buckets hit the limit, its number will be increased in 2 times.

comments powered by Disqus