Collections

Question 1

What is a list?

Answer 1

A list is a sequence of elements.
Basic methods are add, remove, get, size
The List interface provides a special iterator, called a ListIterator, that allows element insertion and replacement, and bidirectional access in addition to the normal operations that the Iterator interface provides. A method is provided to obtain a list iterator that starts at a specified position in the list.
In a list every element has a position assigned and can be accessed or removed by its position.

Question 2

What is a queue?

Answer 2

A Queue is a FIFO data structure where the first element being inserted is the first one to be removed from the queue.
To be more explicit about our intent, we could use the Deque (pronounced “deck”) interface, which is a double-ended queue, where the elements can be added or removed from either the head or the tail.

Question 3

What is a set?

Answer 3

A set data-structure represents a series of elements and operations on these elements where elements contrary to a list have no position. We can add and remove an object and check if it is contained in the list.
If an object is already present, set assure uniqueness, therefore it won’t be included twice.

Question 4

What is a map?

Answer 4

A Map is a hash map data structure which allows one null key and multiple null values.
It’s a key-value pair data structure.

Question 5

Describe equals and hashCode

Answer 5

If equals returns true then hashCode must return true as well, the contrary is not guaranteed.

The equals() method must be:

reflexive: an object must equal itself
symmetric: x.equals(y) must return the same result as y.equals(x)
transitive: if x.equals(y) and y.equals(z) then also x.equals(z)
consistent: the value of equals() should change only if a property that is contained in equals() changes (no randomness allowed)

E.g.

@Override
equals(Object obj) {
if(obj == null) return false;
if(!(obj instance of Whatever) return false;
Whatever other = (Whatever) obj;
return (firstName == other.firstName || (firstName != null && firstName.equals(other.getFirstName))
}
Hashcode criterias:
internal consistency: the value of hashCode() may only change if a property that is in equals() changes
equals consistency: objects that are equal to each other must return the same hashCode
collisions: unequal objects may have the same hashCode

E.g.
@Override
public final int hashCode() {
    int result = 17;
    if (city != null) {
        result = 31 * result + city.hashCode();
    }
    if (department != null) {
        result = 31 * result + department.hashCode();
    }
    return result;
}

Question 6

What are some list implementations?

Answer 6

Array List, LinkedList

Search Operation
Search Operation in ArrayList is pretty fast when compared to the LinkedList search operation. ArrayList Method get(int index) gives the performance of O(1) while LinkedList performance is O(n). This is because ArrayList allows random access to the elements in the list as it operates on an index-based data structure while LinkedList does not allow random access as it does not have indexes to access elements directly, it has to traverse the list to retrieve or access an element from the list.

Manipulation
Manipulation with ArrayList is slow because it internally uses array. If We need to insert or delete element in ArrayList, it may take O(n), as it internally uses array and we may have to shift elements in case of insertion or deletion. On the other hand manipulation with LinkedList is faster than ArrayList because it uses doubly linked list so no bit shifting is required in memory. If We need to insert or delete element in LinkedList, it will take O(1), as it internally uses a double linked list.

An ArrayList is a simpler data structure than a LinkedList . An ArrayList has a single array of references in contiguous memory locations. It only has to be recreated if the array is expanded beyond its allocated size. But, LinkedList consists of a chain of nodes; each node is separately allocated and has front and back pointers to other nodes. When it comes on adding and removing elements from the middle of the list Array list and Linked list perform the same. ArrayList will usually be faster. It needs less memory allocations, has much better locality of reference (which is important for processor caching) etc.

LinkedList class can act as a list and queue both because it implements List and Deque interfaces.

Question 7

What are some set implementations?

Answer 7

HashSet, LinkedHashSet

Java Set implementation uses internally an HashMap.

Question 8

What are map implementations?

Answer 8

HashMap, LinkedHashmap
HashMap contains an array of Node and Node can represent a class having following fields :
1) int hash
2) K key
3) V value
4) Node next

Question 9

What is hashing?

Answer 9

Hashing is a process of converting an object into integer form by using the method hashCode(). Its necessary to write hashCode() method properly for better performance of HashMap. Here I am taking key of my own class so that I can override hashCode() method to show different scenarios. 
hashCode() method is used to get the hash Code of an object

equals method is used to check that 2 objects are equal or not. This method is provided by Object class. You can override this in your class to provide your own implementation.
HashMap uses equals() to compare the key whether the are equal or not. If equals() method return true, they are equal otherwise not equal.

In case of collisions a list is created.
To avoid collisions equals and hashCode methods are used.
If there are collisions in a hashMap the values are stored in a list linked to that entry, where the collision occurred, in the hashMap.
Maps are not synchronised per se, but we can synchronise them using Collections.synchronizedMap(arg);