Stack源码分析（JDK1.8）

作者: 阿狸404 | 来源:发表于2018-02-06 15:53 被阅读10次

Stack源码分析（JDK1.8）
深入ArrayList源码分析（JDK1.8）
ArrayList源码分析(基于jdk1.8)（二）：subLi
搞懂 Java HashMap 源码
JDK1.8 ConcurrentHashMap源码分析(一)
Stack简介
ConcurrentHashMap
Java是如何实现Future模式的？万字详解！26
ConcurrentHashMap源码分析
HashMap源码分析——JDK1.8

这篇文章，实际上不应该算是源码分析，这是在源码的思想基础上自己实现的Stack.但是方法与思想是一致。这里先介绍一下栈的特点：先进后出，后进先出。

Stack变量以及常量分析

        /**
     * 存储数据
     */
    Object[] elementData;
    /**
     * 数据大小：这样elementData[0]可以作为栈底。elementData[elementCount-1]可以作为栈顶
     */
    int elementCount;
    /**
     * 容量增长系数
     */
    int capacityIncrement;
    
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

这应该不算是一种源码分析，而是参照源码的思想实现的一种栈。

Stack的常见创建方式
2.1 空构造函数

public SimpleStack() {
        this(10, 0);
}

2.2 带参数的构造函数

public SimpleStack(int initialCapacity, int capacityIncrement){
        if (initialCapacity < 0 ) {
            throw new IllegalArgumentException("Illegal Capacity: "+
                    initialCapacity);
        }
        this.capacityIncrement = capacityIncrement;
        this.elementData = new Object[initialCapacity];
    }

从无参构造函数知道：无参构造函数默认数组长度为10.

集合扩容操作

/************************************************************扩容操作 *********************************************************************/
    /**
     * 扩容
     */
    public synchronized void ensureCapacityHelper(int minCapacity){
        //什么时候需要扩容呢？
        if (minCapacity > elementData.length) {
            grow(minCapacity);
        }
    }
    /**
     * 如何扩容
     * @param minCapacity
     */
    public synchronized void grow(int minCapacity){
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + ((capacityIncrement > 0) ? capacityIncrement : oldCapacity);//扩容为原来的一倍
        if (newCapacity < minCapacity ) {
            newCapacity = minCapacity;//如果扩容之后的大小还不足以添加元素，则扩容为最大的那个
        }
        if (newCapacity > MAX_ARRAY_SIZE) {
            newCapacity = hugeCapacity(minCapacity);
        }
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
    
    public synchronized int hugeCapacity(int minCapacity){
        if (minCapacity < 0) {
            throw new OutOfMemoryError();
        }
        return minCapacity > MAX_ARRAY_SIZE ?Integer.MAX_VALUE:MAX_ARRAY_SIZE;
    }

这里我们可以知道，其实Stack扩容就是增加了原来数组长度的一倍。

集合操作：增加元素

/******************************************************************基本操作***********************************************************************/
    /**
     * 添加元素
     * @param e
     */
    public synchronized void addElement(E e){
        //第一步：扩容
        ensureCapacityHelper(elementCount+1);
        //第二步：添加
        elementData[elementCount++] = e;//基于数组的，所以是线性顺序的。
    }
    /**
     * 取出元素
     * @return
     */
    public E getElement(){
        if (elementData == null) {
            return null;
        }
        
        int head = elementCount -1;
        E obj = elementData(head);
        //需要删除该位置元素
        removeElementAt(head);
        return obj;
    }
    /**
     * 获取指定位置的元素
     * @param index
     * @return
     */
    @SuppressWarnings("unchecked")
    public E elementData(int index){
        return (E) elementData[index];
    }
    /**
     * 删除指定位置的元素
     * @param index
     * @return
     */
    public synchronized E removeElementAt(int index){
        if (index < 0 ) {
            throw new ArrayIndexOutOfBoundsException();
        }
        E oldElement = elementData(index);
        int j = elementCount - index -1;
        if (j > 0) {
            System.arraycopy(elementData, index + 1, elementData, index, j);
        }
        elementCount --;
        return oldElement;
    }

完整源码

package com.wang.list;

import java.util.AbstractList;
import java.util.Arrays;
import java.util.List;
import java.util.RandomAccess;

/**
 * 栈：入栈，出栈。先进后出（字符串反转:'i love you'）
 * @author Administrator
 *
 */
public class SimpleStack<E> extends AbstractList<E>
                implements List<E>, RandomAccess, Cloneable, java.io.Serializable{

    private static final long serialVersionUID = 5960789704116302371L;
    
    /***************************************************************变量,常量，构造器*********************************************************************/
    /**
     * 存储数据
     */
    Object[] elementData;
    /**
     * 数据大小：这样elementData[0]可以作为栈底。elementData[elementCount-1]可以作为栈顶
     */
    int elementCount;
    /**
     * 容量增长系数
     */
    int capacityIncrement;
    
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
    
    public SimpleStack(int initialCapacity, int capacityIncrement){
        if (initialCapacity < 0 ) {
            throw new IllegalArgumentException("Illegal Capacity: "+
                    initialCapacity);
        }
        this.capacityIncrement = capacityIncrement;
        this.elementData = new Object[initialCapacity];
    }
    
    public SimpleStack() {
        this(10, 0);
    }
    /************************************************************扩容操作 *********************************************************************/
    /**
     * 扩容
     */
    public synchronized void ensureCapacityHelper(int minCapacity){
        //什么时候需要扩容呢？
        if (minCapacity > elementData.length) {
            grow(minCapacity);
        }
    }
    /**
     * 如何扩容
     * @param minCapacity
     */
    public synchronized void grow(int minCapacity){
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + ((capacityIncrement > 0) ? capacityIncrement : oldCapacity);//扩容为原来的一倍
        if (newCapacity < minCapacity ) {
            newCapacity = minCapacity;//如果扩容之后的大小还不足以添加元素，则扩容为最大的那个
        }
        if (newCapacity > MAX_ARRAY_SIZE) {
            newCapacity = hugeCapacity(minCapacity);
        }
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
    
    public synchronized int hugeCapacity(int minCapacity){
        if (minCapacity < 0) {
            throw new OutOfMemoryError();
        }
        return minCapacity > MAX_ARRAY_SIZE ?Integer.MAX_VALUE:MAX_ARRAY_SIZE;
    }
    /******************************************************************基本操作***********************************************************************/
    /**
     * 添加元素
     * @param e
     */
    public synchronized void addElement(E e){
        //第一步：扩容
        ensureCapacityHelper(elementCount+1);
        //第二步：添加
        elementData[elementCount++] = e;//基于数组的，所以是线性顺序的。
    }
    /**
     * 取出元素
     * @return
     */
    public E getElement(){
        if (elementData == null) {
            return null;
        }
        
        int head = elementCount -1;
        E obj = elementData(head);
        //需要删除该位置元素
        removeElementAt(head);
        return obj;
    }
    /**
     * 获取指定位置的元素
     * @param index
     * @return
     */
    @SuppressWarnings("unchecked")
    public E elementData(int index){
        return (E) elementData[index];
    }
    /**
     * 删除指定位置的元素
     * @param index
     * @return
     */
    public synchronized E removeElementAt(int index){
        if (index < 0 ) {
            throw new ArrayIndexOutOfBoundsException();
        }
        E oldElement = elementData(index);
        int j = elementCount - index -1;
        if (j > 0) {
            System.arraycopy(elementData, index + 1, elementData, index, j);
        }
        elementCount --;
        return oldElement;
    }
    
    /*******************************************************************未实现**********************************************************/
    @Override
    public E get(int index) {
        // TODO Auto-generated method stub
        return null;
    }

    @Override
    public E set(int index, E element) {
        // TODO Auto-generated method stub
        return null;
    }

    @Override
    public E remove(int index) {
        // TODO Auto-generated method stub
        return null;
    }

    @Override
    public int size() {
        // TODO Auto-generated method stub
        return 0;
    }
    
    public void print(){
        for (int i = 0; i < elementData.length; i++) {
            System.out.print(elementData[i]);
            System.out.print(",");
        }
    }
    
    
    public static void main(String[] args){
        //逆序输出
        String testStr = "hello word!";
        char[] testChars = testStr.toCharArray();
        SimpleStack<Character> stack = new SimpleStack<Character>(); 
        for (int i = 0; i < testChars.length; i++) {
            stack.addElement(testChars[i]);
        }
        
        stack.print();
        System.out.println();
        
        for (int i = 0; i < testChars.length; i++) {
            System.out.print(stack.getElement()+",");
        }
        
    }
    
}

总结

6.1 特点

基于数组实现的。
有序集合，而且允许null值存在。
线程安全，对于具有修改属性的方法都加了synchronized关键字。
其实，分析完ArrayList再来分析Stack就简单多了，因为Stack的实现很大程度借鉴了ArrayList的思想，包括底层数组实现，都需要扩容等等。那下面我们来详细来分析一下。

6.2 区别ArrayList与Stack

构造方法相似（无参构造，有参构造（数组大小））
无参构造时，Stack默认数组大小为10。ArrayList默认为空数组。
底层都是数组来实现

    /**
     * 存储数据
     */
    Object[] elementData;

添加操作都需要扩容处理
6.1.1 判断是否需要扩容方法不一致
由于在无参构造的时候，我们默认ArrayList数组大小为0，那么扩容的时候首先需要判断一下是否为空数组，然后再考虑什么情况下需要扩容

public void ensureCapacityInternal(int minCapacity) {
        // 解决第一个问题：什么时候需要扩容?如果为空数组，默认数组长度为10
        if (elementData == EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }

        ensureExplicitCapacity(minCapacity);
    }
private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        if (minCapacity > elementData.length) {
            // 如果扩容大于新建数组的长度（数组的长度，非集合中元素的大小），这个时候需要扩容。
            grow(minCapacity);
        }
    }

而Stack默认数组大小为10，所以扩容开始时需要判断什么情况下需要扩容。

    /**
     * 扩容
     */
    public synchronized void ensureCapacityHelper(int minCapacity){
        //什么时候需要扩容呢？
        if (minCapacity > elementData.length) {
            grow(minCapacity);
        }
    }

6.1.2 扩容大小不一致
每一次扩容大小是不一致的，ArrayList每次扩容为原来的一半，就是说新扩容后的大小是原来的1.5倍。而Stack扩容之后新扩容后的大小是原来大小的2倍。
ArrayList扩容代码如下：

/**
     * 实际扩容操作
     * 
     * @param minCapacity
     */
    private void grow(int minCapacity) {
        int oldCapacity = elementData.length; // 原来数组长度
        int newCapacity = oldCapacity + (oldCapacity >> 1);// 扩容新数组大小，为什么选择扩容原来的1.5倍？难道是这是为了节省空间最佳方案。
        if (newCapacity - minCapacity < 0) {
            newCapacity = minCapacity; // 从这里可以看出来，实际扩容大小，有可能不止1.5倍大小。
        }
        if (newCapacity - MAX_ARRAY_SIZE > 0) {
            // 如果MAX_ARRAY_SIZE大小都不能满足扩容之后的新容量大小，则需要进一步扩容
            newCapacity = hugeCapacity(minCapacity);
        }

        elementData = Arrays.copyOf(elementData, newCapacity);// 最后一步最重要的是，把原来数组复制到扩容之后的数组中。这里需要使用到jdk本地库，
                                                                // 不可避免需要IO操作，如果频繁的扩容，会影响ArrayList的性能，因此如果我们知道list大小，可以直接构造出指定容量的数组
    }

Stack扩容代码如下：

public synchronized void grow(int minCapacity){
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + ((capacityIncrement > 0) ? capacityIncrement : oldCapacity);//扩容为原来的一倍
        if (newCapacity < minCapacity ) {
            newCapacity = minCapacity;//如果扩容之后的大小还不足以添加元素，则扩容为最大的那个
        }
        if (newCapacity > MAX_ARRAY_SIZE) {
            newCapacity = hugeCapacity(minCapacity);
        }
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

Stack是线程安全的，而ArrayList是非线程安全的，多线程环境下容易引起问题。但是Stack由于有修改操作方法都添加了Syschronized关键字，因此执行效率比较低。

Stack源码分析（JDK1.8）
这篇文章，实际上不应该算是源码分析，这是在源码的思想基础上自己实现的Stack.但是方法与思想是一致。这里先介绍一...
深入ArrayList源码分析（JDK1.8）
深入ArrayList源码分析（JDK1.8） Java 集合系列源码分析文章：深入TreeMap源码解析（JD...
ArrayList源码分析(基于jdk1.8)（二）：subLi
在上文ArrayList源码分析(基于jdk1.8)（一）：源码及基本操作中对ArrayList源码进行了分析，那...
搞懂 Java HashMap 源码
HashMap 源码分析前几篇分析了 ArrayList ， LinkedList ，Vector ，Stack...
JDK1.8 ConcurrentHashMap源码分析(一)
JDK1.8 ConcurrentHashMap源码分析(一) 前面几篇文章分析了HashMap和LongAdde...
Stack简介
Stack简介 Stack基于Vector实现,支持LIFO 后进先出源码分析 jdk1.7.0_71 默认构造...
ConcurrentHashMap
基于JDK1.8的ConcurrentHashMap的源码分析： ConcurrentHashMap是线程安全的，...
Java是如何实现Future模式的？万字详解！26
JDK1.8源码分析项目（中文注释）Github地址： https://github.com/yuanmabiji...
ConcurrentHashMap源码分析
前言本文中的ConcurrentHashMap源码分析版本是jdk1.8; 问题在对ConcurrentHas...
HashMap源码分析——JDK1.8
HashMap源码分析——JDK1.8 转载：http://blog.csdn.net/u010498696/ar...