Collections

Question 1

Difference between ArrayList and Vector?

Answer 1

1) Vector are Synchronized, due for deprecated, slow, poorly designed, not recommended to use
2)ArrayList are not thread safe
3) thread safe of ArrayList
CopyOnWriteArrayList
List namesList = Collections.synchronizedList(new ArrayList());

Question 2

Character of ArrayList ?

Answer 2

1) Backed by a dynamic array
2) random index access is O(1)
3) manipulation is slow compare with linked list, when one element added/removed, need to move all impacted bits in array

Question 3

Character of LinkedList?

Answer 3

1) internally uses a doubly linked list to store the elements
2) No ramdom index access, need O(n) to find the element
3) Manipulation with LinkedList is faster than ArrayList because it uses a doubly linked list, so no bit shifting is required in memory.
4) Can be used as a Queue/Stack because it implements Deque interfaces
5) have memory over head as need to store the pointers

Question 4

How HashMap internally works?

Answer 4

1. Java7: Array + Linkedlist
   Java8: Array+LinkedList+RedBlackTree(when linkedlist size >8)
   Entry: key, value, hashcode, next pointer
   V never used in comparation!

2.
Capacity - array size, doubled when extended
LoadFactor - default 0.75
threshold - of Extend, = capacity*loadFactor - if not will cause hash collision degreed the performance

3. how get(key)/put(k, v) works
   call key.hashCode(), find the bucket
   call key.equals(otherKey), find the elements

Question 5

How HashSet internally works?

Answer 5

HashMap with all Node with dummy V.

Question 6

Array’s HashCode - need tests

Answer 6

1) Since arrays don’t override the Object.hashCode method. Changing the array’s contents thus does not affect its hash code.
2) To get an array’s hash code correctly, you should call Arrays.hashCode(nums).

Question 7

HashSet and TreeSet Difference?

Answer 7

1. HSimplemented by HashTable, TS-> Tree structure
2. HS elements are unordered, TS elements are sorted
3. HS add/remove/contans is O(1), TS is O(logN)
4. HS using equals() check duplication, TS using compareTo()
5. TS not allow null elements
6. 2 elements equal() must , compareTo() should return 0

Question 8

LinkedHashMap internal implementation?

Answer 8

1. HashMap with gauranteed order of insertion

2. Using a DoubleLinkedList to keep the insertion order

Question 9

Interfaces on Collection framework?

Answer 9

1. Collection
List->(ArrayList, LinkedList, Vector->Stack)
Set->(HashSet, LinkedHashSet)
->SortedSet->NavigableSet->(TreeSet)
Queue->Deque->(LinkedList)

2. Map->(HashMap, LinkedHashMap)
   - >SortedMap->NavigableMap->(TreeMap)

3.Iterator->ListIterator

Question 10

Fail Fast Iterator and Fail safe Iterator

Answer 10

Fail-safe iterators - will not throw any exception even if the collection is modified while iterating over it.
Fail-fast iterators throw an exception(ConcurrentModificationException) if the collection is modified while iterating over it.

Question 11

Iterator Vs ListIterator

Answer 11

Iterator

1. can be used on Map, set ,list
2. can only traverse forward
3. can not modify elements
4. can not return index

ListIterator

1. can only used on List
2. can traverse forward and backword: next(), previous()
3. can modify elements add(), remove(), set()
4. can return index nextIndex(), previousIndex()

Question 12

Collection Vs Collections

Answer 12

Collection - super Interface of List, Set

Collections - Utility class for Collection - because previous java8 version does not allow default methods
addAll(other)
emptyList/Map/Set() - parameterized type safe
EMPTY_SET/LIST/MAP - return raw type
reverse(List> list)
max/min(Collections c), max/min(Collections c, comparator c)

Question 13

Coding 1. Implement HashMap using array

Answer 13

1. entryclass

2. mymap class, put, get

Question 14

Coding 2. Implement ArrayList using array

Answer 14

todo