java 集合框架之List,Set,Map

List,Set,Map的区别

• List （顺序）：List接口存储一组不唯一，有序的对象
• Set（无序）：不允许重复的集合。不会有多个元素引用相同的对象。
• Map（key-value键值对）：Map会维护与Key有关联的值，两个key可以引用相同的对象，key不能重复，key可以是String也可以是任何对象。

ArrayList与LinkedList的区别

• ArrayList与LinkedList都不是同步的，均不保证线程安全。
• 底层数据结构：ArrayList使用Object数组，LinkedList底层使用双向链表，（jdk1.6之前使用双向循环链表，jdk1.7取消了循环）
• 插入删除元素是否受位置影响：ArrayList底层采用Object数组存储，所以插入和删除元素的时间复杂度受元素位置影响，add（E）会将元素追加到列表末尾，在指定位置i插入元素喝删除元素（add（int index,E element））的时间复杂度为O（n-i）。原因是，在位置i和i之后的所有元素都要进行向向后或者向前移位的操作。LinkedList采用链表存储，对于add（E e）方法的插入以及删除元素的时复杂度不受位置影响，如果要在指定位置i插入和删除元素（add（int index,E e））时间复杂度近似为o(n),需要先移动到指定位置再执行插入。
• 是否支持快速随机访问：LinkedList不支持，ArrayList支持，快速随机访问就是通过元素的序号快速获取对象get（int index）

双向链表与双向循环链表

• 双向链表：包含两个指针，一个prev指向前一个节点，一个next指向后一个节点。
  
• 双向循环链表：最后一个节点的next指向head，而head的prev指向最后一个节点形成一个环状结构。
  

ArrayList参与Vector的区别？为什么要用ArrayList取代Vector？

• Vector的所有方法都是同步的，多个线程可以安全的访问一个Vector对象，但是一个线程访问Vector对象要在线程同步操作上耗费大量时间。
• ArrayList不是同步的，在不需要保证线程安全的地方建议使用ArrayList。