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

摘要：加载因子是哈希表在其容量自动增加之前可以达到多满的一种尺度。当哈希表中的条目数超出了加载因子与当前容量的乘积时，则要对该哈希表进行操作即重建内部数据结构，从而哈希表将具有大约两倍的桶数。成员变量每个对由封装，存在了对象数组中。

虽是读书笔记，但是如转载请注明出处 http://segmentfault.com/blog/exploring/
.. 拒绝伸手复制党

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

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

Collection 统一定义的结构包括：
int size();
boolean isEmpty();
boolean contains(Object o);
Iterator iterator();
Object[] toArray();
T[] toArray(T[] a);
boolean add(E e);
boolean remove(Object o);
booelan containsAll(Collection c);
boolean addAll(Collection 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 implements Collection
对Collection接口进行最简单而且必要的实现(iterator()接口仍然保持为抽象，没有提供实现)，类似AbstractMap。
接口List：
public interface List extends Collection
定义了一种有序的结合，也就是我们所知的序列，与Set不同的是，List允许元素重复。

Collection的简要继承结构可以描述为：
Collection
├List
│├LinkedList
│├ArrayList
│└Vector
│　└Stack
└Set

下面进入正题，ArrayList源码分析：
public class ArrayList extends AbstractList implements List, RandomAccess, Cloneable, java.io.Serializable
ArrayList类只有两个私有属性：
private transient Object[] elementData，存储元素的数组
private int size，数组中存储的元素个数
关于transient关键字的说明，参见博文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相同，节省空间。

图片摘自

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

关于 容量和装载因子

从HashMap 成员变量的定义中可以看到这么几个定义：
1. capacity 数组容量（hashmap容量）
2. size 数组中实际填充的键值对数量 （size 超过 thesold 就数组扩容）
3. thesold 数组中能够填充的元素最大值 thesold = capacity * loadfactor
4. 装载因子 loadfactor

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

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

成员变量：Entry[] table

每个对由Entry封装，存在了 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 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内数据集中，链表过长，影响查找效率。

方法列表：

想更一进步的支持我，请扫描下方的二维码，你懂的~