Java常用Collections集合实现原理
一、HashMap集合
1、HashMap的结构：底层是一个数组，每个数组元素是一个链表，实现了Map接口（实现Map接口的集合允许有重复值），key和value都可以为空
2、方法实现原理：当HashMap.put时，先根据key计算Hash值，然后根据hash值找到这个元素在数组中的位置，如果数组中该位置已经有元素了，那么先遍历该位置的链表，如果链表中key相同，则将values进行替换，如果key不相同，则加入到该条链表的头部，最先加入的在尾部；如果数组中该位置没有元素，则将该元素放入到数组的该位置。当HashMap.get时，根据key计算hash值，然后根据hash值找到这个元素在数组中的位置，然后通过key的equals方法找到对应的元素即可。
3、当数组的大小是2的n次幂的时候，元素分布比较均匀,分析算法得出，根据hash值计算数组位置的算法
hash & (table.length - 1)
4、HashMap的resize原理：当HashMap中元素个数达到一定值Max时就需要扩充数组的大小，扩大一倍，此时需要重新计算每个元素的位置，因此扩充容量是一个非常消耗性能的过程，最好在初始化的时候能够预测Hashmap的大小并指定数组大小。这个Max值的计算方法：数组容量 * 加载因子；加载因子默认为0.75f，数组容量默认16，在初始化HashMap时两个参数可以进行设置；
5、Fail-Fast机制：HashMap操作是异步的，因此在不同线程中操作不安全，HashMap利用modCount值来指定修改次数，遍历操作时会先将该值给expectedModCount，每遍历一次判断两值是否相等，不相等的话说明在其他地方修改了，此时抛出ConcurrentModificationException异常。
二、HashSet集合
1、HashSet结构：底层是靠HashMap实现的，实现了Set接口（实现set接口的集合不允许有重复值），key和value都可以为空
2、方法实现原理：当HashSet.add之前，要先确保对象重写equals()和hashCode()方法，这样才能比较对象的值是否相等；HashSet保存的是对象，对应于HashMap中key-values的key;
3、HashSet和HashMap的区别
| HashMap | HashSet |
|---|---|
| HashMap实现了Map接口 | HashSet实现了Set接口 |
| HashMap储存键值对 | HashSet仅仅存储对象 |
| 使用put()方法将元素放入map中 | 使用add()方法将元素放入set中 |
| HashMap中使用键对象来计算hashcode值 | HashSet使用成员对象来计算hashcode值，对于两个对象来说hashcode可能相同，所以equals()方法用来判断对象的相等性，如果两个对象不同的话，那么返回false |
三、HashTable集合：
1、HashTable的结构：类似于HashMap，底层是一个数组，每个数组元素是一个链表，实现了Map接口（实现Map接口的集合允许有重复值），key和values不允许为空；默认容量为 11，加载因子为 0.75。
2、方法实现原理：当HashTable.put时，先根据key计算Hash值，然后根据hash值找到这个元素在数组中的位置（算法:(hash & 0x7FFFFFFF) % tab.length），如果数组中该位置已经有元素了，那么先遍历该位置的链表，如果链表中key相同，则将values进行替换，如果key不相同，则加入到该条链表的头部，最先加入的在尾部；如果数组中该位置没有元素，则将该元素放入到数组的该位置。HashTable.get方法实现与HashMap.get相同，获取数组位置的算法为：(hash & 0x7FFFFFFF) % tab.length）。
3、HashTable的rehash原理：同HashMap的resize原理；
4、HashTable与HashMap的区别：
| HashTable | HashMap |
|---|---|
| HashTable基于Dictionary类 | HashMap基于AbstractMap类 |
| HashTable的key和values都不允许为空，否则会抛空指针异常 | HashMap的key和values都允许为空 |
| HashTable是线程安全的,public方法用synchronized修饰 | HashMap是线程不安全的 |
其中，Dictionary 是任何可将键映射到相应值的类的抽象父类,AbstractMap 是基于 Map 接口的实现，它以最大限度地减少实现此接口所需的工作。通常，涉及到多线程时通常用HashTable，不涉及多线程时常用HashMap。
四、LinkedHashMap、LinkedHashSet集合
LinkedHashMap、LinkedHashSet分别是HashMap、HashSet的有序存储形式，序列的维护是通过双向链表实现的。
五、ArrayList集合
1、ArrayList结构：底层是靠一个数组来实现，每个数组元素是一个对象，且可以为空，数组的容量可以动态变化，实现了List接口。
2、方法实现原理：ArrayList的正常改查都是对数组的操作，不做分析。
3、ArrayList的resize原理：每次向数组中添加数据前，都会判断数组是否容得下，容不下就扩大容量，每次扩大后的容量大约是原来的1.5倍，这个过程是将原数组拷贝到新的数组中，因此很耗费资源，所以在创建ArrayList时如果能预测元素个数 ，最好指定容量。
4、Fail-Fast机制：ArrayList是线程不安全的，Fail-Fast机制同HashMap。
六、LinkedList集合：
1、LinkedList结构：底层是基于链表实现的，存取更加高效，而且不用扩充容量，实现了List接口，没有应用Fail-Fast机制。只要掌握了链表的增删改查，就可以掌握LindedList的使用。