Java interview for developer. Collections. Part 3

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's simple to understand, but it is not so transparent at the first glance. Let's imagine a case, when you use in HashMap as a key some object of class Foo with a set of mutable fields. This object has correctly implemented methods equals() and hashCode(). You put a key-value pair in HashMap, using object A of the class Foo. But you still have a direct link (or use iterator to get to key object) to this object A outside HashMap. You (or somebody) use these direct links 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 your value from HashMap: you create new instance B of class Foo with fields values as they were in an 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 pointed to 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 changed 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 a new bucket for this object after resize, most likely in this case you will be pointed even to incorrect bucket with object B hashcode.

14. Why you cannot 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 a HashMap. byte[] - is an object with methods equals() and hashCode(), so no problems. But hashCode() calculation does not depend on elements in array (array use the original implementation of hashCode() from class Object). What it means? Let's look at the 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 the 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. The main feature of Set is the fact, that it does not allow duplicates to be stored in the same set. Formally, there could not be two elements which s1.equals(s2) == true in the same set.

TreeSet also adds features of tree to set, so elements stored here in a sorted way and the complexity of operations 'add', 'find', 'remove' are 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 the value field is not filled at all. As you remember, you can use only unique 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 uses Red-Black Tree internally. Details on implementing 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 to performance of TreeSet if you add elements 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 the tree: every new element as child of element that were added before. As a result we will get the perfomance of linked list.

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

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

You can use null as a key in HashMap. When you put such key in HashMap it gets 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 the 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 the 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).