List

List实现Collection接口,它的数据结构是有序可以重复的集合,它有三个实现类,ArrayList,LinkList,Vector三个实现类;
三个实现类之间的区别.

• ArrayList:底层数据结构是数组结构,查询速度快,增删改慢.
• LinkList:底层使用链表结构,增删速度快,查询稍慢.
• Vector:底层是数组结构,线程同步ArrayList是线程不同步的.

ArrayList

• ArrayList是List接口的可变数组的非同步实现,并允许包括null在内的所有元素.
• 底层使用数组实现
• 该集合是可变长度数组,数组扩容时,会将来数组中的元素重新拷贝一份到新的数组中,每次数组的容量增长大约是其容量的1.5倍,这种操作的代价是很高的.
• 采用了Fail-Fast机制,面对并发的修改时,迭代器很快就会完全失败,而不是冒着在将来的某个不确定的时间发生不确定行为的风险.
• remove方法会让下标到数组末尾的元素向前移动一个单位,并把最后一位的值置空.方便GC.

LinkedList

• LinkedList是List接口的双向链表的非同步实现,并允许包括null在内的所有元素.
• 底层的数据结构是基于双向链表的,该数据结构我们称为节点.
• 双向链表节点对应类Node的实例,Node中包含成员变量：prev，next，item。其中，prev是该节点的上一个节点，next是该节点的下一个节点，item是该节点所包含的值。
• 查找是分两半查找,index在哪一半,然后再去区域查找,这样最多只要遍历链表的一半节点即可找到.

HashMap

• 基于哈希表的Map接口非同步实现 允许使用null键与null值,但不保证映射的顺序.
• 底层使用数组实现,数组中的每一项是个单向链表,即数组和链表的结合体,当链表的长度大于一定的阈值,链表转换成红黑树,这样减少链表的查询时间.
• 其在底层将键值对当成一个整体进行处理,这个整体就是一个Node对象.底层使用一个Node[]数组来保存所有的键值对,根据equals方法决定其在数组中的存储位置,再使用equals方法从该位置上的链表中取出该Node
• HashMap进行数组扩容需要重新计算扩容后的每个元素在数组中的位置很耗性能
• 采用了Fail-Fast机制，通过一个modCount值记录修改次数，对HashMap内容的修改都将增加这个值。迭代器初始化过程中会将这个值赋给迭代器的expectedModCount，在迭代过程中，判断modCount跟expectedModCount是否相等，如果不相等就表示已经有其他线程修改了Map，马上抛出异常
  HashTable实现原理要点概括
• Hashtable是基于哈希表的Map接口的同步实现,不允许null值键.
• 底层中使用数组实现,数组中的每一项是个单链表,即数组与链表的结合体
• Hashtable在底层将key-value当成一个整体进行处理，这个整体就是一个Entry对象。Hashtable底层采用一个Entry[]数组来保存所有的key-value对，当需要存储一个Entry对象时，会根据key的hash算法来决定其在数组中的存储位置，在根据equals方法决定其在该数组位置上的链表中的存储位置；当需要取出一个Entry时，也会根据key的hash算法找到其在数组中的存储位置，再根据equals方法从该位置上的链表中取出该Entry。
• synchronized是针对整张Ha表的,即每次锁住整张表让线程独占.

HashSet实现原理要点概括

• HashSet是由哈希表支持 不保证set迭代顺序,允许使用null元素.
• 基于HashMap实现 api也是对HashMap的行为进行封装