Build Index Stage:
Hashcode Design Principle:
1. one object will generate the same hash code for repeated running
2. equal -> the same hash code
3. the same hash code !-> equal but good to have (最理想的hashcode)

Default hashcode: memory address in java



Search according to the Index Stage:
Hash Table
= dictionary index
Background:
1. we need o(1) to search
2. we need o(1) to add


Collision: different elements are mapped to the same cell

Solution 1: Linear Probing
Disadvantage: easy to cause clustering which reduce the search perfomance to o(k)
When all cells are full: resize 2x and rehash
Optimization: when cells are close to a certian capacity, we resize it
Load Factor: number of entires / length  <- (0,1) default by 0,75f

Solution 2: seperate chaining (java7之前中用了这个方法）
Process: if the entry has an existing element, kick out it and place the new element in the place and link the kicked out element with a singel linkedlist.
Problems: reduce the search performance when linked list is very long. o(k)

HashMap:
Hash Code is object's memory address;
How to build index: the index of array = hashcode % the length of the array
Collisiton Solution: seperate chain
Entry<K,V> is a key-value pair class
有必要分析HashMap的源码
Optimal Modular Formula:
X mod 2^n = X & (2^n - 1) (n!=0)
Iteration of HashMap:
1. Obj[0] ->....->obj[n];  is not the order we insert the elements
2. have to tranverse null cell - low performance;
The evolution of HashMap in Java 8:
the lenght of linkedlist is very long -> the linkedlist is automatically converted to a tree -> easy to search

HashSet: is actually a special HashMap
LinkedHashMap: LinkedList + HashMap （easy to traverse and traverse the order we insert elements)
LinkedList: maintain the order that the elements were inserted

LRC: Least Recently Used Cache
Function: maintain the access order;
如何更改LinkedHashMap保存顺序：
在构造器中把true改成false，可以实现对access order的维护

TreeMap:(one kind of Red-Black Tree)
Background: for a BST:
if the new element is greater than the former element every time we insert, it becomes a linked list.
Solution: Red-black Tree;
put():o(logn)
get():o(logn)
search():o(logn)
Application: sort and maintain the sort feature
TreeSet: one special TreeMap


*Heap:
Notion: not the heap in the JVM
1. complete tree:
   Every level must have maximum number of nodes（每层都满）
   Bottom level could be an exception（最后一层可以不满）
   Filled from left to right on each level(左偏）
2. Maximum/Minimum elements in the root
3. Children is smaller/larger than its parents

Heap Add/Remove:
1.Maintain the compelte tree
2.Maintain the order of parent and the child

Example remove():
1.remove the root element
2.pick the lowest and rightest element and put it in the root
3.exchange the root with its bigger child until the element cannot be exchanged any more.

Eample add():
1. add the element in the lowest and rightest position
2. exchange it with its parent util this cannot be processed any more

In the physical level:
Heap is implemented by an array
how to get the index of paretn and child

In Java:
Heap is implemented by a Priority Queue (Priority)


 Application: get the 10 largest number of a int set
 1. data set is very large -> hard to sort
 2. so we have to maintain  the insert order by the largest number dynamically
 3. we use heap