Java集合源码分析_java集合体系源代码讲解

框架体系

集合:

• 单列集合（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);//[聊斋]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

遍历方式（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将下移以后集合位置上的元素返回
}
1
2
3
4

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 < toIndex
			List returnlist = list.subList(0, 2);
			System.out.println("returnlist=" + returnlist

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

3种遍历方式

1. Iterator

	List list = new ArrayList();
        list.add("飞飞");
        list.add("李四");

        Iterator iterator = list.iterator();
        while (iterator.hasNext()) {
            System.out.println(iterator.next());
        }
    
1
2
3
4
5
6
7
8
9

2. foreach

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

3. 普通for

		for(int i=0;i<list.size();i++){
            System.out.println(list.get(i));
        }
1
2
3

ArrayList源码分析

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, 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;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

    //无参构造方法
    public ArrayList() {
        //创建一个空数组
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

    //有参构造方法
    public ArrayList(int initialCapacity) {
    //当初始容量<0,抛出异常 IllegalArgumentException
        if (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) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
                Integer.MAX_VALUE :
                MAX_ARRAY_SIZE;
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

通俗易懂的分析

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

• 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); //最后把扩容后的长度复制给数组
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

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
2
3
4
5
6

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就进行扩容
1
2
3