JDK源码学习（jdk1.8.0_20）

本是古典何须时尚 2022-05-26 06:09 228阅读 0赞

## 集合框架 ##

### ArrayList ###

基于jdk1.8.0\_20

继承关系图   
![这里写图片描述][70]   
ArrayList的定义

public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable

ArrayList的底层使用Object数组来存储的

transient Object[] elementData;

以前听说ArrayList的初始大小为10，应该是以前的版本，我这个版本中ArrayList如果不指定大小时默认为空

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

在这里主要关注一下自动扩容的实现

public boolean addAll(Collection<? extends E> c) {
        Object[] a = c.toArray();
        int numNew = a.length;
        //确保数组大小超过size + numNew
        ensureCapacityInternal(size + numNew);
        //实现数组复制，a是源数组，0是源数组要复制的起始位置，elementData是目的数组
        //size是目的数组放置的起始位置，numNew复制的长度
        System.arraycopy(a, 0, elementData, size, numNew);
        size += numNew;
        //如果c为空则返回false,不为空则返回true
        return numNew != 0;
    }

public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

增加一个元素或者增加好几个元素都会在调用ensureCapacityInternal方法来确保数组大小足够大，可以确定在ensureCapacityInternal方法里面实现了自动扩容

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    private static final int DEFAULT_CAPACITY = 10;

private void ensureCapacityInternal(int minCapacity) {
    
        //目前数组为空
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            //要求的容量大小和10取最大值
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }
    
        ensureExplicitCapacity(minCapacity);
    }

private void ensureExplicitCapacity(int minCapacity) {
        modCount++;
    
        //这个是出于2种考虑
        //如果需要的容量大于目前的容量，就需要扩容
        //如果minCapacity溢出，即minCapacity为负数，就不扩容
        //minCapacity为负数的一种情况是addAll(Collection<? extends E> c)传入的参数已经溢出了
        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

//之所以定义为Integer.MAX_VALUE - 8，是因为VM会保留一些头结点在数组开头
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        //>>是右移运算符，相当于除以2，因此新容量是旧容量的1.5倍
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        //这里需要分为2种情况
        //1.扩容还不满足，直接将新容量设为需要的容量
        //2.newCapacity溢出，变为负数，扩充容量扩的太大了
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

private static int hugeCapacity(int minCapacity) {
        //溢出了，minCapacity的值大于int能存储的最大值，用int存储会变为负数
        //这里minCapacity之所以为负数，可能是因为vm进行了一些操作
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

这个类实现数组复制用的是System.arraycopy方法，这个方法复制比较快，因为是对内存直接进行复制，减少了for循环中的寻址时间

//实现数组复制，a是源数组，0是源数组要复制的起始位置，elementData是目的数组
    //size是目的数组放置的起始位置，numNew复制的长度
    System.arraycopy(a, 0, elementData, size, numNew);

### LinkedList ###

基于jdk1.8.0\_20

继承关系图   
![这里写图片描述][70 1]   
LinkedList的定义

public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable

LinkedList采用的双向链表结构，因此在LinkedList中定义了一个静态内部类

private static class Node<E> {
    
        //存放元素
        E item;
        //相当于后向指针，指向链表中当前元素的后一个元素
        Node<E> next;
        //相当于前向指针，指向链表中当前元素的前一个元素
        Node<E> prev;
    
        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }

定义的变量为

//链表的长度
    transient int size = 0;
    //链表的头结点
    transient Node<E> first;
    //链表的尾结点
    transient Node<E> last;

增加元素的方法，addFirst，addLast，add都很类似，分析一个

public void addFirst(E e) {
        linkFirst(e);
    }

private void linkFirst(E e) {
    
        //把链表的头结点放到f这个中途变量
        final Node<E> f = first;
        //构造结点，前向指针为null，元素为e，后向指针指到f
        final Node<E> newNode = new Node<>(null, e, f);
        //插入的结点编程头结点
        first = newNode;
        //如果原先头结点为空
        if (f == null)
            //构造的结点不仅为头结点，也是尾结点
            last = newNode;
        else
            //原先头结点的前向指针指向构造的结点
            f.prev = newNode;
        //元素个数加1
        size++;
        //每次对元素进行操作时，这个都会增加1，主要为了迭代器校验错误使用
        modCount++;
    }

删除元素的方法

public boolean remove(Object o) {
        if (o == null) {
            for (Node<E> x = first; x != null; x = x.next) {
                if (x.item == null) {
                    unlink(x);
                    return true;
                }
            }
        } else {
            for (Node<E> x = first; x != null; x = x.next) {
                if (o.equals(x.item)) {
                    unlink(x);
                    return true;
                }
            }
        }
        return false;
    }

E unlink(Node<E> x) {
        // assert x != null;
        final E element = x.item;
        final Node<E> next = x.next;
        final Node<E> prev = x.prev;
    
        //如果前向指针为空，则说明它是头结点，删除时只要把它的下一个结点赋值为头结点即可
        if (prev == null) {
            first = next;
        } else {
            //前向结点的后向指针直接指向后向结点，从开头遍历不到这个结点
            prev.next = next;
            x.prev = null;
        }
    
        //如果后向指针为空，则说明它是尾结点，删除时只要把它的上一个结点赋值为尾结点即可
        if (next == null) {
            last = prev;
        } else {
            //后向结点的前向指针直接指向前向结点，从结尾遍历不到这个结点
            next.prev = prev;
            x.next = null;
        }
    
        //把x.prev和x.next赋值为null，LZ猜是为了加速垃圾回收，但没有实际测试
        x.item = null;
        size--;
        modCount++;
        return element;
    }

获取元素的方法

public E get(int index) {
        //检查下标是否越界
        checkElementIndex(index);
        return node(index).item;
    }

Node<E> node(int index) {
        // assert isElementIndex(index);
        //size >> 1和size / 2一个效果，因为将位右移一位相当于除2
        //在前半段，正向遍历
        if (index < (size >> 1)) {
            Node<E> x = first;
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        //在后半段，反向遍历
        } else {
            Node<E> x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }

分析源码可知，通过get方式遍历LinkedList是一种很低效的方式，因为每找一个元素都是从头或者尾开始的，最好采用foreach或迭代器方式

## Hashtable ##

基于jdk1.7.0\_80

![这里写图片描述][70 2]   
构造函数，默认初始容量为11

public Hashtable(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+
                    initialCapacity);
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal Load: "+loadFactor);
    
        if (initialCapacity==0)
            initialCapacity = 1;
        this.loadFactor = loadFactor;
        table = new Entry[initialCapacity];
        threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
        initHashSeedAsNeeded(initialCapacity);
    }

public Hashtable() {
        this(11, 0.75f);
    }

put

public synchronized V put(K key, V value) {
        //value为null抛出空指针异常
        if (value == null) {
            throw new NullPointerException();
        }
    
        // Makes sure the key is not already in the hashtable.
        Entry tab[] = table;
        int hash = hash(key);
        //7FFFFFFF的二进制为1111111111111111111111111111111
        //hash & 0x7FFFFFFF是为了保hash值始终为正数
        int index = (hash & 0x7FFFFFFF) % tab.length;
        for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
            if ((e.hash == hash) && e.key.equals(key)) {
                V old = e.value;
                e.value = value;
                return old;
            }
        }
    
        modCount++;
        //数量已经达到阈值
        if (count >= threshold) {
            // Rehash the table if the threshold is exceeded
            rehash();
            //table的值已经变化
            tab = table;
            //重新进行hash
            hash = hash(key);
            index = (hash & 0x7FFFFFFF) % tab.length;
        }
    
        //取出目前链表第一位
        Entry<K,V> e = tab[index];
        //将新增加的值变为第一个值
        tab[index] = new Entry<>(hash, key, value, e);
        count++;
        return null;
    }

和HashMap的区别

<table style="border-spacing:0px;width:852px;text-align:center;color:rgb(51,51,51);font-family:'-apple-system', 'SF UI Text', Arial, 'PingFang SC', 'Hiragino Sans GB', 'Microsoft YaHei', 'WenQuanYi Micro Hei', sans-serif, SimHei, SimSun;font-size:14px;background-color:rgb(255,255,255);"> 
 <thead> 
  <tr> 
   <th style="margin:0px;vertical-align:middle;">关注点</th> 
   <th align="left" style="margin:0px;vertical-align:middle;">Hashtable</th> 
   <th align="left" style="margin:0px;vertical-align:middle;">HashMap</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td style="margin:0px;vertical-align:middle;">是否线程安全</td> 
   <td align="left" style="margin:0px;vertical-align:middle;">是</td> 
   <td align="left" style="margin:0px;vertical-align:middle;">否</td> 
  </tr> 
  <tr> 
   <td style="margin:0px;vertical-align:middle;">key和vlaue</td> 
   <td align="left" style="margin:0px;vertical-align:middle;">均不允许为空</td> 
   <td align="left" style="margin:0px;vertical-align:middle;">都可以为空</td> 
  </tr> 
  <tr> 
   <td style="margin:0px;vertical-align:middle;">求index的方法</td> 
   <td align="left" style="margin:0px;vertical-align:middle;">(hash &amp; 0x7FFFFFFF) % table.length;</td> 
   <td align="left" style="margin:0px;vertical-align:middle;">hash &amp; (table.length - 1)</td> 
  </tr> 
  <tr> 
   <td style="margin:0px;vertical-align:middle;">扩容的时机</td> 
   <td align="left" style="margin:0px;vertical-align:middle;">count &gt;= threshold</td> 
   <td align="left" style="margin:0px;vertical-align:middle;">(size &gt;= threshold) &amp;&amp; (null != table[bucketIndex])</td> 
  </tr> 
  <tr> 
   <td style="margin:0px;vertical-align:middle;">扩容的大小</td> 
   <td align="left" style="margin:0px;vertical-align:middle;">table.length&lt;&lt;1+1</td> 
   <td align="left" style="margin:0px;vertical-align:middle;">2 * table.length</td> 
  </tr> 
 </tbody> 
</table>

get

public synchronized V get(Object key) {
        Entry tab[] = table;
        int hash = hash(key);
        int index = (hash & 0x7FFFFFFF) % tab.length;
        for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
            if ((e.hash == hash) && e.key.equals(key)) {
                return e.value;
            }
        }
        return null;
    }

这里put和get方法都没有对key进行空值判断，是因为key为null调用hash会抛出空指针异常

private int hash(Object k) {
        // hashSeed will be zero if alternative hashing is disabled.
        return hashSeed ^ k.hashCode();
    }

## ConcurrentHashMap ##

基于jdk1.7.0\_80   
![这里写图片描述][70 3]

[70]: /images/20220526/448fbdf7a0534838afde7dc0d0566efb.png
[70 1]: /images/20220526/2ce56082c3e64c60b40b867aaed5d072.png
[70 2]: /images/20220526/1cd23f5c1f654bb897e414c8a5f969d3.png
[70 3]: /images/20220526/5965c248f8434598a846cd8324e6ad81.png