#JAVA集合的底层实现原理
## 关于集合类的层次结构
JAVA集合类包括了Collection接口和Map接口
其次Collection接口包括了List和Set两个子接口
List包括了ArrayList, LinkedList, Vector三个实现类
Set包括了HashSet,LinkedHashSet,TreeSet三个实现类
Map包括了HashMap,LinkedHashMap,TreeMap,Hashtable, properties五个实现类

主要要探究底层实现的是ArrayList与LinkedList, HashSet与 LinkedHashSet，HashMap与LinkedHashMap这三个实现类，其中TreeSet与TreeMap的两个排序也需要学会使用

## ArrayList与LinkedList与Vector
1. ArrayListjdk7及以前，在声明创建ArrayList数组时就在底层创建了这个长度为**10**的Object [] elements数组，如果添加时导致底层数组长度不够就会扩容，默认情况下，扩容为原来的数组的 **1.5** 倍，并将原来数组中的元素复制到新的数组中。
结论：尽量不要使用ArrayList的无参构造器，而使用带参的构造器，可以在创建时就确定了底层数组的长度，不用每次扩容提高效率。
2. jdk8时，在声明创建时生成Object [] elements= **{ }**，即没有创建底层数组，在添加第一个元素时会在底层创建一个长度为10的数组，扩容情况与jdk7相同。
3. 总结：jdk7的类似于单例设计模式的饿汉式，jdk8类似于单例设计模式的懒汉式，可以延迟数组的创建，有助于节省内存。
4. LinkedList内部声明了Node类型的first与last属性，默认值为null,将所有添加的对象封装到Node中，创建了Node对象，其中Node定义为双向链表。(不涉及扩容问题)
5. Vector与ArrayList不同是Vector底层扩容每次扩容为原来的两倍，ArrayList扩容为原来的1.5倍。
## HashSet
1. 向HashSet中添加元素，首先调用元素所在类的hashCode()方法，计算出该元素的哈希值，接着由该元素的哈希值通过散列函数计算出在数组中出现的位置：
若此位置上没有其他元素，则添加成功--情况一；
若有其他元素(或以链表方式存在的多个元素)，则比较其他元素与该元素的hash值：如果哈希值不同，则添加成功--情况二；如果hash值相同，进而调用该元素的equals()方法：equals返回true，添加失败；equals返回false，添加成功--情况三。
2. 对于情况二和三而言，该元素与已经存在指定索引上的数据以lianb1形式存储；jdk7：该元素指向原来元素；
jdk8：原来元素指向该元素。

## HashMap
1. jdk7及以下，实例化后底层创建了长度为16的一维数组Entry[] table，put()元素时，调用key的所在类的hashCode()方法计算key的哈希值，此哈希值经过散列函数的计算后，得到在Entry数组中的存放位置：如果此位置上数据为空，则key-value添加成功--情况一；如果此位置上的数据不为空(意味此位置上存在一个或多个数据(以链表存在))，比较key和已存在的一个或多个数据的哈希值：如果key的哈希值与已经存在的数据哈希值都不同，则key-value添加成功--情况二；如果key的哈希值和原来已经存在的某一个数据的哈希值相同，进而调用key所在类的equals()比较：如果equals()返回false，此时key-value添加成功--情况三；如果equals返回true，则用所要添加的value替换已经存在的value。
2. 关于情况二和情况三：此时key-value和原来的数据以链表方式存储。
3. 在不断添加过程中，当超出临界值(由加载因子和底层数组的长度的相乘得)(且要存放的位置非空)默认扩容会扩容为原来的2倍，并将原来的数据复制过来。
4. jdk8相较于jdk7在底层实现的不同：底层没有创建一个长度为16的数组；底层数组是Node[]，而非Entry[]；首次调用put()时，底层创建长度为16的数组；jdk7底层结构：数组+链表，jdk8底层结构：数组+链表+红黑树；当数组的某一索引位置上的元素以链表形式才能在的数据个数>8且当前数组的长度>64时，此时索引位置上的所有数据改为使用红黑树存储。
5. DEFAULT_INITIAL_CAPACITY : HashMap的默认容量，16；DEFAULT_LOAD_FACTOR：HashMap的默认加载因子，0.75；threshold：Bucket中链表长度大于该默认值，转化为红黑树，16*0.75=12；TREEIFY_THRESHOLD：Bucket中链表长度大于该默认值，转化为红黑树，8；MIN_TREEIFY_CAPACITY：桶中的Node被树化时最小的hash表容量，64。