集合

• 框架体系
• Conllection接口
• • 常用方法
  • 遍历方式（Iterator迭代器）
  • • 迭代器执行原理
• List接口
• • 常用方法
  • 3种遍历方式
  • ArrayList源码分析
  • • 通俗易懂的分析
  • Vector源码分析
• Set
• • HashSet
• HashMap
• • HashMap底层原理
  • HashMap的put方法执行流程
  • hashMap中添加数据时，有三个条件会触发他的扩容机制

框架体系

集合:

• 单列集合（List Set) 存放数据都一个一个的
• 双列集合(Map) 存放数据是 key-value

Conllection接口

• Conllection实现子类可以存放多个元素，每个元素可以是Object
• 有些Conllection的实现类，可以存放重复元素，有些不可以
• 有些Conllection的实现类，有些是有序的（List) ，有些不是有序 （Set)
• Conllection接口没有直接的实现子类，是通过它的子接口Set和List来实现的

常用方法

// 因为Conllection是接口，所以使用List接口下面的ArrayList来实现List list = newArrayList();
// add:添加单个元素list.add("jack");list.add(10);//list.add(new Integer(10))list.add(true);System.out.println("list=" + list);
// remove:删除指定元素
//list.remove(0);//删除第一个元素list.remove(true);//指定删除某个元素System.out.println("list=" + list);
// contains:查找元素是否存在System.out.println(list.contains("jack"));//T
// size:获取元素个数	System.out.println(list.size());//2	
// isEmpty:判断是否为空System.out.println(list.isEmpty());//F
// clear:清空list.clear();System.out.println("list=" + list);
// addAll:添加多个元素ArrayList list2 = new ArrayList();list2.add("红楼梦");list2.add("三国演义");list.addAll(list2);System.out.println("list=" + list);
// containsAll:查找多个元素是否都存在	System.out.println(list.containsAll(list2));//T
// removeAll：删除多个元素	list.add("聊斋");list.removeAll(list2);System.out.println("list=" + list);//[聊斋]

遍历方式（Iterator迭代器）

1. Iterator对象称为迭代器，主要用于遍历Collection集合中的元素
2. 所有实现了Collection接口的集合类都有一个Iterator()方法
3. Iterator仅用于遍历集合，本身并不存放对象

迭代器执行原理

Iterator iterator = coll.iterator();      //得到一个迭代器
while(iterator.hasNext(){                //hasNext() 判断是否还有下一个元素 System.out.println(iterator.next()); //next的作用：1.下移，2将下移以后集合位置上的元素返回
}

List接口

1. List集合类中元素 有序可重复
   有序：添加顺序和取出顺序一致
2. List集合中每个元素都有其对应的顺序索引，仅支持索引（从0开始）
3. List容器中的元素都对应一个整数型的序号记载其在容器中的位置
4. 常用实现类：ArrayList LinkedList Vector

常用方法

		
//		void add(int index, Object ele):在 index 位置插入 ele 元素//在 index = 1 的位置插入一个对象list.add(1, "韩顺平");//		boolean addAll(int index, Collection eles):从 index 位置开始将 eles 中的所有元素添加进来List list2 = new ArrayList();list2.add("jack");list2.add("tom");list.addAll(1, list2);//		Object get(int index):获取指定 index 位置的元素	
//		int indexOf(Object obj):返回 obj 在集合中首次出现的位置System.out.println(list.indexOf("tom"));//2//		int lastIndexOf(Object obj):返回 obj 在当前集合中末次出现的位置list.add("xixi");System.out.println("list=" + list);System.out.println(list.lastIndexOf("xixi"));
//		Object remove(int index):移除指定 index 位置的元素，并返回此元素list.remove(0);//		Object set(int index, Object ele):设置指定 index 位置的元素为 ele , 相当于是替换.list.set(1, "玛丽");System.out.println("list=" + list);
//		List subList(int fromIndex, int toIndex):返回从 fromIndex 到 toIndex 位置的子集合
// 		注意返回的子集合 fromIndex <= subList < toIndexList returnlist = list.subList(0, 2);System.out.println("returnlist=" + returnlist

3种遍历方式

1. Iterator

	List list = new ArrayList();list.add("飞飞");list.add("李四");Iterator iterator = list.iterator();while (iterator.hasNext()) {System.out.println(iterator.next());}

2. foreach

		for(Object o:list){System.out.println(o);}

3. 普通for

		for(int i=0;iSystem.out.println(list.get(i));}

ArrayList源码分析

public class ArrayList extends AbstractListimplements List, RandomAccess, Cloneable, java.io.Serializable
{private static final long serialVersionUID = 8683452581122892189L;// 默认容量private static final int DEFAULT_CAPACITY = 10;// 空数据private static final Object[] EMPTY_ELEMENTDATA = {};// 默认容量空数据private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};// 存储数据的数组transient Object[] elementData;// 数组大小private int size;

    //无参构造方法public ArrayList() {//创建一个空数组this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;}//有参构造方法public ArrayList(int initialCapacity) {//当初始容量<0,抛出异常 IllegalArgumentExceptionif (initialCapacity > 0) {this.elementData = new Object[initialCapacity];} else if (initialCapacity == 0) {this.elementData = EMPTY_ELEMENTDATA;} else {throw new IllegalArgumentException("Illegal Capacity: "+initialCapacity);}}public boolean add(E e) {//确保有足够的容量，假如你是5个，你必须得有6个容量才能保证你下一次能够加入ensureCapacityInternal(size + 1);  //这个size就是数组大小//在数据中正确的位置上放上元素e，并且size++elementData[size++] = e;return true;}//这是的 minCapacity 就是上面的 size+1,private void ensureCapacityInternal(int minCapacity) {//判断elementData是不是空的数组if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {// DEFAULT_CAPACITY = 10,上面定义了，这句话的意思就是把需要的最小容量和10进行比较，把最大值赋值给minCapacity minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);}ensureExplicitCapacity(minCapacity);}private void ensureExplicitCapacity(int minCapacity) {modCount++;//判断elementData是否够用，不够进行扩容if (minCapacity - elementData.length > 0)grow(minCapacity);}private void grow(int minCapacity) {int oldCapacity = elementData.length;int newCapacity = oldCapacity + (oldCapacity >> 1); // 1.5倍扩容if (newCapacity - minCapacity < 0)//如果扩大1.5倍还不行，则进行大容量分配newCapacity = minCapacity;if (newCapacity - MAX_ARRAY_SIZE > 0)newCapacity = hugeCapacity(minCapacity);elementData = Arrays.copyOf(elementData, newCapacity); //最后将扩容后的长度复制给数组}private static int hugeCapacity(int minCapacity) {if (minCapacity < 0) // overflowthrow new OutOfMemoryError();return (minCapacity > MAX_ARRAY_SIZE) ?Integer.MAX_VALUE :MAX_ARRAY_SIZE;}

通俗易懂的分析

1.使用无参构造器刚开始是创建一个elementData空数组调用add方法确定是否进行扩容，调用ensureCapacityInternal方法把数组需要的最小容量传进去（minCapacity) （这里的minCapacity就是上面的size+1),这个size就是数组大小，初始为0然后进行判断这个数组是否是个空的，然后将minCapacity和默认容量10进行比较，把最大值赋值给minCapactity然后执行ensureExplicitCapacity(minCapacity)方法，再进行比较，如果需要的最小容量还是比数组长度大，就调用grow(minCapacity)方法进行扩容，1.5扩容（第一次是10，第二次开始就是1.5倍），最后将扩容后的长度复制给数组2.使用有参构造器刚开始就是创建一个指定大小容量的数组，后面和上面的一样

• ArrayList 具有 fail-fast 快速失败机制，能够对ArrayList 作出失败检测。当迭代集合的过程中该集合在结构上发生改变时，就有可能会发生 fail-fast，即抛出 ConcurrentModificationException异常。

jdk1.7不同的就是
1.7类似单例的饿汉式（管你要不要，直接给你）
1.8类似单例的懒汉式（你需要就给你） 延迟了数组的创建，节省内存。

• 无参构造：刚开始就是一个长度为10 的数组

• 有参构造：指定的容量必须>10，否则抛出异常

  扩容的时候，减少了ensureExplicitCapacity(minCapacity)方法，在ensureCapacityInternal方法中不再判断数组是否为空，直接进行扩容（之前是在ensureExplicitCapacity(minCapacity)方法中进行扩容的）

Vector源码分析

底层也是数组，线程都是安全的

public synchronized boolean add(E e) {modCount++;//增加元素前，检查容量是否够用ensureCapacityHelper(elementCount + 1);elementData[elementCount++] = e;return true;
}
// minCapacuty = elementCont +1 
private void ensureCapacityHelper(int minCapacity) {// minCapacity就是最小需要的容量if (minCapacity - elementData.length > 0)// 最小需要的容量都比数组长度大，就进行扩容grow(minCapacity);
}//扩容
private void grow(int minCapacity) {int oldCapacity = elementData.length;// capacityIncrement 容量增量 // 如果增量>0就增长 capacityIncrement 长度，否则 2倍扩容int newCapacity = oldCapacity + ((capacityIncrement > 0) ?capacityIncrement : oldCapacity);if (newCapacity - minCapacity < 0)newCapacity = minCapacity;if (newCapacity - MAX_ARRAY_SIZE > 0)newCapacity = hugeCapacity(minCapacity);elementData = Arrays.copyOf(elementData, newCapacity); //最后把扩容后的长度复制给数组
}

Set

HashSet

• 底层是一个HashMap，非线程安全，初始化容量是16，2倍扩容，默认加载因子 0.75 （意思就是说，当数组的个数到达容量的0.75
  时，就会进行扩容）

• Java8中，如果一条链表的元素个数到达8个并且table>=64，就会进行树化（红黑树），否则仍然采用数组扩容机制

• key 和value 都允许null

HashMap

HashMap底层原理

Java8之前使用拉链法，底层使用数组+链表，8之后 底层使用数组+链表+红黑树
HashMap是基于哈希算法来确定元素的位置（槽）的,当我们向集合中存入数据时,它会计算传入的Key的哈希值,并利用哈希值取余来确定槽的位置。如果元素发生碰撞,也就是这个槽已经存在其他的元素了,则HashMap会通过链表将这些元素组织起来。如果碰撞进一步加剧,某个链表的长度达到了8,则HashMap会创建红黑树来代替这个链表,从而提高对这个槽中数据的查找的速度。
HashMap中,数组的默认初始容量为16，当数组中的元素达到一定比例的时候HashMap就会2倍扩容,这个比例叫做负载因子,默认为0.75。自动扩容机制,是为了保证HashMap初始时不必占据太大的内存,而在使用期间又可以实时保证有足够大的空间。采用2的指数进行扩容,是为了利用位运算,提高扩容运算的效率

HashMap的put方法执行流程

首先会先判断该数组是否为null，如果为空进行扩容，然后根据key计算hash值，得到插入的位置，
如果该位置为空，直接进行插入，否则就判断key是否相等，如果相等直接进行覆盖，
不相等就判断它是否为红黑树，如果是红黑树就直接在树中进行插入，
否则就遍历链表，遍历的过程中，若发现key相等就进行覆盖，
不相等就判断链表长度是否>8,如果>8就把链表转换为红黑树，在树中进行插入，
插入成功后再判断是否超过了阈（域）值，超过了就进行扩容，没有就结束。

1. 先判断键值对数组table[i]是否为空或为null，是则执行resize(进行扩容;
2. 然后根据键值key计算hash值得到插入的数组索引i，如果table[i]==null，直接新建节点添加，转向⑥，如果table[i]不为空，转向③;
3. 接着判断key是否存在，存在就直接覆盖value，否则转向④，这里的相同指的是hashCodel以及equals
4. 就判断table[i]是否为treeNode，即table[i]是否是红黑树，如果是红黑树，则直接在树中插入键值对，否则转向⑤
5. 就进行遍历，判断链表长度是否大于8，大于8的话把链表转换为红黑树，在红黑树中执行插入操作，否则进行链表的插入操作;遍历过程中若发现key已经存在直接覆盖value即可
6. 插入成功后，判断实际存在的键值对数量size是否超过了最大容量threshold，如果超过，进行扩容，反之结束

hashMap中添加数据时，有三个条件会触发他的扩容机制

1. 如果数组为空,则进行首次扩容。
2. 将元素接入链表后,如果链表长度达到8,并且数组长度小于64,则扩容。 
3. 添加元素后,如果数组中元素超过阈值,也就是加载因子0.75就进行扩容