一、List
1、subList
不会返回新的list对象--与String的subString不同
返回原来list的从[fromIndex,toIndex)之间这一部分的视图，实际上，返回的list是靠原来的list支持的。
对原来的list和返回的list做的“非结构性修改”(non-structuralchanges)，都会影响到彼此。
补充：如何删除List某个区间的数据
list.subList(from,to).clear();--将元素释放并清空内部属性
2、链表与顺序表
增删时哪个快慢由元素位置决定
3、List实现RandomAccess接口
表示支持快速随机访问
并根据是否实现此接口，决定采用序列二分查找（for循环遍历）还是迭代器二分查找
indexedBinarySerach/iteratorBinarySerach
ArrayList中for循环遍历比迭代器遍历快
4、ArrayList的扩容
（1）使用add时首先调用ensureCapacityInternal方法，传入size+1进去，检查是否需要扩充elementData数组的大小；
（2）newCapacity=扩充数组为原来的1.5倍
（3）使用grow方法扩容
（4）使用System.arraycopy将原数组复制到copy数组中
5、Array和ArrayList
存储类型
是否指定大小
二、Map
1、HashMap底层
Jdk1.7：数组+链表【头插法】
Jdk1.8：数组+链表【尾插法，减少线程安全】/红黑树（链表8个元素&数组长度>=64，以提高搜索效率）
注意：头插法不支持并发，可能会形成数据环，get数据时导致死循环
2、HashMap的put方法
存key-value时，先计算key的hash值
Hash值相同且key值相同，则用新的entry键值对覆盖原有的value值
hash值相等但key值不等，则进行插入（链表/红黑树）
3、HashMap的get方法
通过key的hash值找到在table数组中的索引处的Entry，返回key对应的value
Entry作为键值对，整体存储
4、HashMap的resize方法
（1）调用时机
首次put时，初始化默认table大小为16
扩容时会调用，即size>threshold时，数组翻倍
（2）扩容变化
移动到新表，一部分位置不变，一部分变到原来的i+n位置处
5、size是2的整数次方
为了计算key对应的位置，即hash(KEY)%数组长度length
通常使用&运算比取余速度快，为了保证结果相等，即hash(KEY)&(length-1)
偶数对应二进制最后一位是0时，len-1为奇数，与运算后结果可能为0/1，否则浪费了一般的空间
为了使不同hash值发生碰撞的概率较小，使元素在哈希表中均匀地散列。
6、HashMap多线程死循环
HashMap元素达到一定长度时（长度*负载因子0.75）需要扩容，扩容时进行Rehash操作
多线程同时put时，使用头插法进行操作，与其他线程的节点顺序不一致，会导致HashMap中的链表中出现循环节点，进而使得后面get的时候，会死循环。
7、线程不安全
（1）多线程使用put添加元素
Key碰撞，会添加到同一个位置，容易导致某个线程的数据被覆盖
（2）多线程同时检测到超过数组大小*loadFactor
多线程同时对hash数组扩容，重新计算元素位置以及复制数据，但是只有一个线程扩容后的数组会赋给table，其他线程的都会丢失。各自线程put的数据也丢失，且会引起死循环的错误。
8、get判断是否存在
不能判断某个元素是否在map中
不能，返回null时，无法判断key为空还是value为空
注意：HashMap允许key为空，也允许value为空
9、HashMap实现线程安全
（1）使用Hashtable，多线程访问同步方法，容易阻塞，效率较低（例如put时不能get）
（2）使用工具类的方法实现同步，即Collections.synchronizeMap(hashMap);
补充：如何保证线程安全？
添加synchronized来保证
（3）使用ConcurrentHashMap
10、HashMap与HashTable
（1）分别基于AbstractMap和Dictionary类
（2）HashTable不允许key和value为null，而HashMap均允许为空
（3）Hashtable线程安全，但所有操作都是synchronized的，实现代价高（串行化易阻塞，不利于并发）
11、HashMap与ConcurrentHashMap
HashMap不是线程安全的，而ConcurrentHashMap是线程安全的。
ConcurrentHashMap在对象中保存了一个Segment数组，使用分段锁，将整个Hash桶分为多个segment片段
在元素插入时，需要获取segment锁，在片段上践行插入，减小了锁的粒度
12、HashTable和ConcurrentHashMap
HashTable使用synchronized关键字对整张哈希表加锁，让线程独占整张表，效率低
ConcurrentHashMap对对象中的每个segment分别加锁，可以实现多线程put操作。
13、ConcurrentHashMap实现原理
（1）JDK7中采用了数组+Segment+分段锁的方式实现。
Segment继承了ReentrantLock，是一种可重入锁（ReentrantLock)。
（2）JDK8中参考了JDK8HashMap的实现，采用了数组+链表+红黑树的实现方式来设计，不再使用分段锁，而是利用CAS+Synchronized保证并发。
CAS：比较和交换
14、LinkedHashMap实现原理
基于HashMap实现，定义了一个Entryheader头结点
继承hashMap中的Entry，添加两个属性Entrybefore，after，和header结合起来组成一个双向链表，来实现按顺序排序。
LinkedHashMap定义了排序模式accessOrder，该属性为boolean型变量，对于访问顺序，为true；对于插入顺序，则为false。迭代顺序默认为插入顺序。
三、Set
1、HashSet实现原理
依赖于HashMap实现，其构造中会初始化一个HashMap对象，而其值不允许重复
因此，HashSet的值在HashMap中的Entry数组以key的形式存放，当要存储的值已经存在时返回FALSE。
2、HashSet保证不重复
值作为map的key，map的value是PRESENT变量
PRESENT变量以占位符的形式存放
添加元素时，调用booleanadd(Ee)，并returnmap.put(e,PRESENT)==null;
四、其他
1、集合框架介绍
2、Iterator介绍
（1）介绍
是一种设计模式，作为迭代器对象，可以遍历并选择序列中的元素
轻量级对象&单向移动
（2）使用
第一次调用Iterator的next()方法时，它返回序列的第一个元素
使用remove()将迭代器新返回的元素删除。
3、Iterator和ListIterator
Iterator可用来遍历Set和List集合，但是ListIterator只能用来遍历List
Iterator只能前向遍历，ListIterator可以前向或后向
ListIterator实现了Iterator接口，并包含其他功能：
增加元素、替换元素、获取前后一个元素的索引
4、Iterator和Enumeration接口
（1）Iterator更安全，阻止集合遍历时被其他线程所修改，否则会抛出ConcurrentModificationException异常，即fail-fast机制（集合类的一种错误检测机制）
（2）Iterator的方法名更科学
（3）Iterator能够删除元素，而Enumeration不能。
5、fail-fast与fail-safe
（1）java.util.*的集合类（fail-fast快速失败）：Iterator的fail-fast属性与集合共同起作用，正在遍历的集合的结构被改变时，fail-fast迭代器抛出ConcurrentModificationException异常
（2）JUC的集合类（fail-safe安全失败）：不会抛出ConcurrentModificationException异常。先复制集合内容，在拷贝的集合上进行遍历
6、Collection和Collections
Collection：是最基本的集合接口，一个Collection代表一组Object，即Collection的元素。它的直接继承接口有List，Set和Queue。
Collections：不属于Java的集合框架，是集合的工具类。不能被实例化，包含有关集合操作的静态多态方法，实现对集合的搜索、排序、线程安全等操作。
