Java笔记-容器源码(持续更新)

阅读量：5846 次

发布时间：2019-06-19

本文共 7798 字，大约阅读时间需要 25 分钟。

虽是读书笔记，但是如转载请注明出处

.. 拒绝伸手复制党

LinkedList

LinkedList 与 ArrayList 一样实现 List 接口，只是 ArrayList 是 List 接口的大小可变数组的实现，LinkedList 是 List 接口链表的实现。

LinkedList 可以被当做堆栈、队列（实现List接口）或双端队列（实现Deque接口）进行操作。

LinkedList 是非同步的。

属性：

transient int size = 0;transient Node
    
      first;transient Node
     
       last;

构造函数

LinkedList提供了2种构造函数，默认的和使用另外一个 collection 来初始化的方式。

使用Collection来初始化，实际上是调用了addAll函数将Collection全部添加到链表中。

indexOf

public int indexOf(Object o) {        int index = 0;        if (o == null) {            for (Node
    
      x = first; x != null; x = x.next) {                if (x.item == null)                    return index;                index++;            }        } else {            for (Node
     
       x = first; x != null; x = x.next) {                if (o.equals(x.item))                    return index;                index++;            }        }        return -1;    }

与ArrayList对比，这两个类的indexOf方法足以说明这两个类的区别，以及两个容器类操作的精华。

public int indexOf(Object o) {        if (o == null) {            for (int i = 0; i < size; i++)                if (elementData[i]==null)                    return i;        } else {            for (int i = 0; i < size; i++)                if (o.equals(elementData[i]))                    return i;        }        return -1;    }

ArrayList

在分析ArrayList的源代码之前，先学习一下Collection接口及其继承体系，毕竟ArrayList是Collection的一种实现，了解Collection定义的接口和实现，对整体把握Collection的功能总是有帮助的。

首先，看看Collection接口的定义：

public interface Collection<E> extends Iterable<E>

Collection接口继承了Iterable，回顾一下迭代器模式，这就说明Collection的各种实现必须提供一个迭代器的功能，让用户可以在不知道Collection内部元素的情况下，获取一种访问内部元素的方法，具体的访问顺序由迭代器的实现决定，比如List内常用的iterator支持顺序的访问，LinkedList的listIterator支持双向访问。

Collection 统一定义的结构包括：

int size();

boolean isEmpty();

boolean contains(Object o);

Iterator<E> iterator();

Object[] toArray();

<T> T[] toArray(T[] a);

boolean add(E e);

boolean remove(Object o);

booelan containsAll(Collection<?> c);

boolean addAll(Collection<? extends E> c);

boolean removeAll(Collection<?> c);

boolean retainAll(Collection<?> c);

void clear();

boolean equals();

int hashCode();

这些接口的功能顾名思义，不再一一介绍，值得注意的是当添加一个元素时，使用的是模板参数E，而contain和remove时，提供的确实Object类型对象，类似的情况在HashMap的源码中put(K key, V value), get(Object key)也有出现，参考stackoverflow上的相关解答，觉得可以接受的原因描述为：

当对一个参数进行的contains， remove操作在Collection内部都需要调用equals()函数来判断参数和Colletion内元素的相等关系，但是equals()函数是属于Object类的方法，并不要求进行比较的两个元素是同一个类的对象，所以当传入参数的过程中也就不要求和Collection内部泛型参数类型相同。但是对于put，add等操作，编译器会在编译过程中进行类型检查，需要保证插入的对象是同一个类或者其子类的对象。

说完了Collection接口，下面看看继承和实现该接口的一些相关类：

抽象类AbstractCollection：

public abstract class AbstractCollection <E> implements Collection<E>

对Collection接口进行最简单而且必要的实现(iterator()接口仍然保持为抽象，没有提供实现)，类似AbstractMap。

接口List：

public interface List<E> extends Collection<E>

定义了一种有序的结合，也就是我们所知的序列，与Set不同的是，List允许元素重复。

Collection的简要继承结构可以描述为：

Collection

├List

│├LinkedList

│├ArrayList

│└Vector

│　└Stack

└Set

下面进入正题，ArrayList源码分析：

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

ArrayList类只有两个私有属性：

private transient Object[] elementData，存储元素的数组

private int size，数组中存储的元素个数

关于transient关键字的说明，参见博文

构造函数：

ArrayList提供了三种构造函数，默认的，指定数组大小的以及使用另外一个collection来初始化的方式。重点来看第三种，首先将参数集合转换成数组，赋值给当前集合的数组，设置数组元素个数。如果参数集合返回的不是Object数组，这调用 Arrays.copyOf将数组转换为Object类型。

常用接口：

contains()
判断一个元素是否在集合内，根据参数指定的对象在对象数组的索引位置来判断。

get()
获取参数位置指定的元素，首先检查参数的合法性，然后直接使用索引作为数组下标访问目标元素

set()
替换指定位置的元素

add()
添加一个元素，首先判断添加一个元素之后是否需要对数组进行扩容，如果需要则创建一个新的数组，并把原来数组的元素拷贝到新数组内，再将待添加的元素放在数组的末尾，也就是add添加元素是将元素插入数组的尾端。添加一个元素会触发对ArrayList修改次数的增加，即modCount++, 这个步操作的作用是用来“同步”对ArrayList的修改。最常见的使用是在迭代器中，当我们使用迭代器访问一个ArrayList的过程中，如果意外更改了此字段的值，则迭代器将抛出ConcurrentModificationException来响应next, remove, previous, set和add操作，在迭代期间面临并发修改时，它提供了快速失败行为，而不是非确定性行为。

remove()
移除一个元素，提供了两种移除元素的方法，首先是移除指定位置的元素，并将index后的元素前移一位。然后是移除指定元素，先确定参数指定的元素在ArrayList的索引位置，再调用fastRemove方法按照索引移除一个元素，这边没有直接调用remove是为了避免索引位置的越界检查过程。

iterator()

剩下基本的操作功能还有addAll, removeAll, retainAll等在集合之间进行的操作，不再一一描述。除了这些在集合上的操作，ArrayList还提供了两种迭代器来访问List内的元素：Iterator和ListIterator, 前一种迭代器的实现是从List头部开始顺序的访问内部元素，而ListIterator提供了一种更灵活的实现，支持从指定位置开始访问、访问前驱节点的功能。

subList()

除此之外，ArrayList实现了一个私有内部类SubList，支持对List上获取子序列的操作
从类的属性和构造函数我们也发现，子序列没有在内容上作出拷贝，而是通过在原始序列上的偏移量来控制元素的访问，获取原始序列的一小段视图。所以，在SubList执行的修改序列结构的操作比如add,set都将映射到原始序列上。

toArray
ArrayList 提供了 2 个 toArray() 函数：
```
Object[] toArray()
      
        T[] toArray(T[] contents)
      
```
调用 toArray() 函数会抛出 “java.lang.ClassCastException” 异常，但是调用 toArray(T[] contents) 能正常返回 T[]。

toArray() 会抛出异常是因为 toArray() 返回的是 Object[] 数组，将 Object[] 转换为其它类型 (如如，将 Object[] 转换为的 Integer[]) 则会抛出 “java.lang.ClassCastException” 异常，因为 Java 不支持向下转型。具体的可以参考前面 ArrayList.java 的源码介绍部分的 toArray()。

解决该问题的办法是调用 T[] toArray(T[] contents) ，而不是 Object[] toArray()。

调用 toArray(T[] contents) 返回 T[] 的可以通过以下几种方式实现。

// toArray(T[] contents)调用方式一public static Integer[] vectorToArray1(ArrayList
    
      v) {    Integer[] newText = new Integer[v.size()];    v.toArray(newText);    return newText;}// toArray(T[] contents)调用方式二。最常用！public static Integer[] vectorToArray2(ArrayList
     
       v) {    Integer[] newText = (Integer[])v.toArray(new Integer[0]);    return newText;}// toArray(T[] contents)调用方式三public static Integer[] vectorToArray3(ArrayList
      
        v) {    Integer[] newText = new Integer[v.size()];    Integer[] newStrings = (Integer[])v.toArray(newText);    return newStrings;}

Some other thing

从ArrayList的源码中我们不难发现，当我们插入，删除元素的过程都将触发对象数组elementData内容的复制，这是比较耗时的操作，所以ArrayList在元素的插入删除方面没有优势，而元素的随机访问就很快。ArrayList上元素的拷贝常用到的函数是Arrays.copyOf() 和System.arrayCopy(), 而Arrays.copyOf在创建了新的数组之后，最终也是要调用System.arrayCopy()进行内容的拷贝，所以System.arrayCopy就直接决定的数组拷贝的效率，在 java的实现中，这个函数是一个native方法，也就是通过其他语言比如C++来获取更高的执行效率。

trimToSize()，由于elementData的长度会被拓展，size标记的是其中包含的元素的个数。所以会出现size很小但elementData.length很大的情况，将出现空间的浪费。trimToSize将返回一个新的数组给elementData，元素内容保持不变，length很size相同，节省空间。

HashMap

原理

HashMap 实现原理是基于数组+链表。

HashMap 就是一个大数组，在这个数组中，通过key的哈希值来寻找存储在数组的index; 如果遇到多个元素的 hash 值一样，那么怎么保存，这就引入了链表，在同一个 hash 的位置，保存多个元素（通过链表关联起来）。HashMap 所实现的基于 <key, value> 的键值对形式，是由其内部内 Entry 实现。

something

关于 容量和装载因子

从HashMap 成员变量的定义中可以看到这么几个定义：

1. capacity 数组容量（hashmap容量）

2. size 数组中实际填充的键值对数量（size 超过 thesold 就数组扩容）

3. thesold 数组中能够填充的元素最大值 thesold = capacity * loadfactor

4. 装载因子 loadfactor

HashMap的对象有两个参数影响其性能：初始容量和装载因子。初始容量只是哈希表在创建时的容量。加载因子是哈希表在其容量自动增加之前可以达到多满的一种尺度。当哈希表中的条目数超出了加载因子与当前容量的乘积时，则要对该哈希表进行 rehash 操作（即重建内部数据结构），从而哈希表将具有大约两倍的桶数。

HashMap 在扩容的时候，会重新计算 hash 值，并对 hash 的位置进行重新排列，因此，为了效率，尽量给 HashMap 指定合适的容量，避免多次扩容。

成员变量：Entry<K,V>[] table

每个<key,value>对由Entry<K,V>封装，存在了 Entry对象数组table中。这也是hashmap的bucket.

put方法

寻找链表插入位置：

if (e.hash == hash && ((k = e.key) == key || key.equals(k)))

Map的key可以是任意类型的，比如如果一个key是基本的数据类型比如int这些，==可以直接比较，而如果使用一些自定义类作为key，需要自己提供equals功能来判断两个key对象是不是一致的。

put 方法流程是：

看以table[i]为首的链表是否存在插入节点的key的entry;

如果存在：替换value；如果不存在：使用头插法插入在table[i]位置;

还需要判断hashmap的数组是否满了，若满，table数组扩容2倍。

HashMap 之所以不能保持元素的顺序有以下几点原因：第一，插入元素的时候对元素进行哈希处理，不同元素分配到 table 的不同位置；第二，容量拓展的时候又进行了 hash 处理；第三，复制原表内容的时候链表被倒置

HashMap 只允许一个为 null 的 key。

get方法

get(Object key) 根据 key 对应的 hash 值计算在 table 数组中的索引位置，然后遍历该链表判断是否存在相同的 key 值

for (Entry<K,V> e = table[indexFor(hash, table.length)];

if (e.hash == hash && ((k = e.key) == key || key.equals(k)))

key 的定位

在HashMap中，在获取一个键的hash码后在查找对应bucket的过程中使用到了一个indexFor函数

static int indexFor(int h, int length) {

return h&(length-1);

}

参考他人分析，弄懂了indexFor函数计算数组下标的原理，过程如下：

根据HashMap的源码，我们知道HashMap要求长度必须为2的冥，这里就是关键所在。它通过h&（length-1）确定hash值的索引下标，这是因为，当length是2的冥时，length-1就是全1的数字，h&(length-1)就是h%(length)，显然位运算更具有效率。同时如果长度不是2的冥，（length-1）的二进制位表示中叫出现部分0值，与h按位与的时候，这些位永远是0，那么这些为1的位置将会永远闲置，导致hash的分布不均匀，降低了查找效率。比如假设length是15，length-1就是14，其二进制位表示为： 1110。最后一位是1，所有的hash与1110按位与的时候得到的结果最后一位都是0，也就是说Entry[] table内0001,0011，0101， 0111,1001,1011，1101这些位置将永远不会被填充上数据，导致其他bucket内数据集中，链表过长，影响查找效率。

方法列表：