Java Collection and Map

Interface: Collection, List, Set, Map.
Class: ArrayList, LinkedList, Vector, HashSet, TreeSet, HashTable, HashMap, TreeMap.
           (Stack is inherited from Vector)
Difference between List and Set:
List can have duplicated elements but Set cannot.


Difference between ArrayList, LinkedList and Vector:
ArrayList and LinkedList are not synchronized.
Vector is synchronized.


ArrayList and Vector are based on Array, but with dynamic size. 
LinkedList is based on linked list, there is a pointer in each node, pointing to the next element.


Looking up element:
ArrayList and Vector support random access, but LinkedList does not, it needs to read from the head.


Inserting and deleting element:
ArrayList needs to move elements that is behind the target index.
LinkedList needs to move pointer.
So, if the target index is in the end of the list, ArrayList is fast. Otherwise, LinkedList is fast.


So, when you need to add/remove lots number of elements randomly in the List, and read from head in sequence, LinkedList is better.
When you need to add/remove lots number of elements at end of the list and randomly read data, ArrayList is better.


Difference between HashSet and TreeSet:
HashSet: Elements are not sorted.
TreeSet: Elements are sorted. Sorting algorithm: Red Black Tree. 
               Either the elements in the set has implemented comparable interface, or define Comparator when defining the TreeSet Object.


Difference between HashTable, HashMap and TreeMap:
TreeMap: Asynchronized.
                If needs to be synchronized, can use synchronizedSortedMap method:
               1 SortedMap m = Collections.synchronizedSortedMap(new TreeMap(...));
                Elements are sorted.
Difference between HashTable, HashMap is discussed in the previous article.

Hash Table(Reference WIKIPEDIA)

A Hash Table is a data structure for storing key/value pairs.

Slot: One unit for storing data, the container of data. 
Hash function: maps key to the index of the slot.calculates an index from the data item's key and use this index to place the data into the array.
Hash collision: hash function maps two different keys to one slot.
Load factor:  the ratio n/s between n and the size s of its array of buckets. It represents the portion of the s buckets in the structure that are filled with one of the n stored entries. If it approaches 0, it means that many buckets are empty and memory is wasted.


Collision resolution:
1. Chaining

• Each slot of the bucket array is a pointer to a linked list that contains the key-value pairs that hashed to the same location.
• Lookup worst case: O(n). All the entries map to one single slot.

Hash collision resolved by separate chaining.

Hash collision by separate chaining with head records in the bucket array.

2. Open Addressing

• All entry records are stored in the bucket array itself. 
• When a new entry has to be inserted, the buckets are examined, starting with the hashed-to slot and proceeding in some probe sequence, until an unoccupied slot is found.

Advantage:
Lookup speed is fast. But when there are many collisions, the speed will be decreased.
So it's important to write a good hash function. In the same time of keeping load factor, reducing collision.


Difference between Hash Table and Hash Map

• Hash Table is synchronized, but Hash Map is not.
• Hash Table inherits from Dictionary, but Hash Map inherits from Map.
• Hash Table does not allow null key or null value. But Hash Map allows. It can have multiple keys maps to null value, but it can only have one null key. Also, it must use containsKey() to check whether one specific key exists. Because when it returns null when using get(). It could be either the key does not exist or the value of the key is null.
• Hash Table uses Enumeration, but Hash Map uses Iterator.
• In Hash Table, the default size of hash array is 11, and increased to 2*old +1 each time. In Hash Map, the default size is 16, and when resizing, the size doubles.
• In Hash Table, it uses hashCode() directly, but in Hash Map, it recalculates the hash value and use & instead of mod.

Algorithm-Tree (Reference WIKIPEDIA)

1. Binary Search Tree

    Feature:

•     The left subtree of a node contains only nodes with keys less than the node's key.
•     The right subtree of a node contains only nodes with keys greater than the node's key.
•     Both the left and right subtrees must also be binary search trees.

    The major advantage of binary search trees over other data structures is that the related sorting algorithms and search algorithms such as in-order traversal can be very efficient.

    Example:

2. Red Black Tree

    Feature:

    A red–black tree is a binary search tree where each node has a colorattribute, the value of which is either red or black. In addition to the ordinary requirements imposed on binary search trees, the following requirements apply to red–black trees:

1. A node is either red or black.
2. The root is black. (This rule is sometimes omitted from other definitions. Since the root can always be changed from red to black, but not necessarily vice-versa, this rule has little effect on analysis.)
3. All leaves are the same color as the root.
4. Both children of every red node are black.
5. Every simple path from a given node to any of its descendant leaves contains the same number of black nodes.

    Example:

3. AVL Tree

    Feature:

   In an AVL tree, the heights of the two child subtrees of any node differ by at most one.

    AVL trees are more rigidly balanced than red-black trees, leading to slower insertion and removal but faster retrieval.

4. B Tree

    Feature:

    B-tree is optimized for systems that read and write large blocks of data. It is commonly used in databases and filesystems.

  Example(A B-tree of order 2 or order 5):

5. Prefix Tree

    Feature:

• A prefix tree, or trie, is an ordered tree data structure that is used to store an associative array where the keys are usually strings.
• Unlike a binary search tree, no node in the tree stores the key associated with that node; instead, its position in the tree defines the key it is associated with.
• All the descendants of a node have a common prefix of the string associated with that node, and the root is associated with the empty string. Values are normally not associated with every node, only with leaves and some inner nodes that correspond to keys of interest.

    It saves the storing space but wastes memory.//Personal Opinion

    The following are the main advantages of tries over binary search trees (BSTs):

• Looking up keys is faster. Looking up a key of length m takes worst case O(m) time. A BST performs O(log(n)) comparisons of keys, where n is the number of elements in the tree, because lookups depend on the depth of the tree, which is logarithmic in the number of keys if the tree is balanced. Hence in the worst case, a BST takes O(m log n) time. Moreover, in the worst case log(n) will approach m. Also, the simple operations tries use during lookup, such as array indexing using a character, are fast on real machines.
• Tries are more space efficient when they contain a large number of short keys, because nodes are shared between keys with common initial subsequences.
• Tries facilitate longest-prefix matching, helping to find the key sharing the longest possible prefix of characters all unique.
• The number of internal nodes from root to leaf equals the length of the key. Balancing the tree is therefore no concern.

   A trie can also be used to replace a hash table, over which it has the following advantages:

• Looking up data in a trie is faster in the worst case, O(m) time, compared to an imperfect hash table. An imperfect hash table can have key collisions. A key collision is the hash function mapping of different keys to the same position in a hash table. The worst-case lookup speed in an imperfect hash table is O(N) time, but far more typically is O(1), with O(m) time spent evaluating the hash.
• There are no collisions of different keys in a trie.
• Buckets in a trie which are analogous to hash table buckets that store key collisions are necessary only if a single key is associated with more than one value.
• There is no need to provide a hash function or to change hash functions as more keys are added to a trie.
• A trie can provide an alphabetical ordering of the entries by key.

     Tries do have some drawbacks as well:

• Tries can be slower in some cases than hash tables for looking up data, especially if the data is directly accessed on a hard disk drive or some other secondary storage device where the random-access time is high compared to main memory.^[5]
• Some keys, such as floating point numbers, can lead to long chains and prefixes that are not particularly meaningful. Nevertheless a bitwise trie can handle standard IEEE single and double format floating point numbers.

  Example:

                                                            

Summary of Time Complexity of each kind of tree:

Name	Construct			Operation			Self-Balanced
	Best	Average	Worst	Best	Average	Worst
Binary Search Tree	O(nlogn)	O(nlogn)	O(n2)	O(1)	O(log n)	O(log n)	No
Red Black Tree	----	O(nlogn)	----	O(1)	O(log n)	O(log n)	Yes
AVL Tree	----	O(nlogn)	----	O(1)	O(log n)	O(log n)	Yes
B Tree	----	O(nlogn)	----	O(1)	O(log n)	O(log n)	Yes
Prefix Tree	----	O(mn)	----	O(1)	O(m)	O(m)	No

 m is the length of the key.