Over a million developers have joined DZone.

Java Interview for Developer: Collections Part 3 - Maps and Trees

· Java Zone

Check out this 8-step guide to see how you can increase your productivity by skipping slow application redeploys and by implementing application profiling, as you code! Brought to you in partnership with ZeroTurnaround.

This is the last part of Java interview questions for collections. 
Here is part one and two.

13. In what case you could "lost" element in HashMap?

This question is tricky, it simple to understand, but it is not so trasperent at the first glance. Let's imagine a case when you use in HashMap as a key some object of class Foo with set of mutable fields. This object has correctly implemented methods equals() and hashCode(). You put some key-value in HashMap, using object A of class Foo. But you still have direct link (or use iterator to get to key object) to this object outside HashMap and you (or somebody) use it to change values of one or more fields of object A, that is already put in HashMap as a key. Next you stop using direct link and lost it, but you want to get you value from HashMap: you create new instance B of class Foo with fields values as they were in object A, when you put it in HashMap as a key. What's next? If HashMap was not resized after fields of object A were changed, using new object B you will be in correct bucket (hashCode() of object B will be the same as it was for object A, when it were put in HashMap), but then you will use equals() to find correct element in bucket and here you can not find anything, cause object A has changes values of fields then it has object B. If HashMap was resized after fields of object A were changed, then hashCode() for object A with new fields values were recalculated to find new bucket for this object after resize, most likely in this case you will be come with object B to incorrect bucket.

14. Why you can not use byte[] as a key in HashMap?

To tell the truth, you can use byte[] or any other array (like int[], float[], etc.) as a key in HashMap. byte[] - is a object with method methods equals() and hashCode(), so no problems. But hashCode() calculation does not depend on elements in array (array use original implementation of hashCode() from class Object). What it means? Let's look on code:

byte[] a = new byte[]{1,2,3,4};
HashMap hashMap = new HashMap();
hashMap.put(a,"test");
byte[] b = new byte[]{1,2,3,4};
String result = hashMap.get(b);

In variable result you will have null, cause hashCode of array b is different from hashCode of array a. It means that if you use array as a key, you should use only original object to get value from HashMap back.

15. What is the difference between TreeSet and HashSet?

Here you need to start from the moment that TreeSet and HashSet, both implement interface Set. Main feature of Set is the fact, that is does not allows duplicates to be stored in the same set, formally in the same set could not be two elements which s1.equals(s2) == true.

TreeSet also add features of tree to set, so elements store here in sorted way and the comlexity of operation add, find, remove is lg N. Internally TreeSet is implemented using Red-Black Tree. HashSet internally is just HashMap, but in this HashMap you use only key field and value field is not filled. As you remember you can use only uniq keys in HashMap, so keys in HashMap formally is a Set. Complexity of operations in case of HashSet is the same as in HashMap.

16. What kind of tree used in TreeSet?

The answer for this question is in question #15. TreeSet internally use Red-Black Tree. Details of implementing of this kind of tree could be find in books about algorithms, but to tell the truth I have never asked about deep details of it.

17. What will happened with performance of TreeSet if you will add element in ad in ascending order?

This question could little bit frustrating, because you consider in basic that TreeSet internally use binary tree, but do not know what kind of binary tree used exactly, or just think that used simple binary tree. In this case seems like elements, that are going in ascending order, will be placed in the same branch of tree: every new element as child of element that were add before. As a result we will get perfomance of linked list.

But TreeSet actually use Red-Black Tree, the main feature of this tree is ability to regroup elements between branches to maintain optimal "height" of tree. In this case, complexity of all operations with tree will be lg N and it does not depend on order elements were added.

18. Is it possible to use null as a key in HashMap? in TreeMap?

You can use null as key in HashMap. When you put such key in HashMap it get hashCode value 0, but null - is not an object, seem like such value is some exceptional case, where you can get hash code of non object entity. So with hash code value 0, key-value pair will always be placed in bucket 0. To get such element HashMap has special code in get method:

private V getForNullKey() {  
    for (Entry e = table[0]; e != null; e = e.next) {  
        if (e.key == null)  
            return e.value;  
        }  
        return null;  
    }
}

So there is no problem with null and HashMap. In case of TreeMap, every time you add new element, TreeMap will use method compareTo() to find correct place in tree for new element. compareTo() will not be used for only one element - first added element, because there is nothing to compare with. null is not an object, there is no possible way to call compareTo() on null. So you can add null in TreeMap only once as first element only and no elements can be added after, also you can not perform mostly no operations with such TreeMap (e.g. it is ok to call size() on TreeMap, but put(), get() will give you NPE).

The Java Zone is brought to you in partnership with ZeroTurnaround. Check out this 8-step guide to see how you can increase your productivity by skipping slow application redeploys and by implementing application profiling, as you code!

Topics:

Published at DZone with permission of Ivan Zerin, DZone MVB. See the original article here.

Opinions expressed by DZone contributors are their own.

The best of DZone straight to your inbox.

SEE AN EXAMPLE
Please provide a valid email address.

Thanks for subscribing!

Awesome! Check your inbox to verify your email so you can start receiving the latest in tech news and resources.
Subscribe

{{ parent.title || parent.header.title}}

{{ parent.tldr }}

{{ parent.urlSource.name }}