JdK源码阅读-集合类

Jdk源码阅读，把集合类的源码阅读了下，这里记下一些自己的理解；

ArrayList

使用数组存储数据；

    内部结构 transient Object[] elementData;

非线程安全
一些需要注意的函数

1. void trimToSize();
把elementData数组，变成只有size的大小数组;即当数组大小大于实际使用size的时候，把数组大小变小

2. void ensureCapacity(int minCapacity)
把数组扩容到可以支持minCapacity的大小；
默认扩大到 oldCapacity + oldCapacity << 1；即1.5倍
如果不够，则扩大到minCapacity

3.  <T> T[] toArray(T[] a)
如果a的size >= 数组的size，则返回的就是a；
不然返回的是一个新的Array

4. E set(int index, E element) 
set 对象的时候，会返回这个位置上的旧的元素 
add的时候不会
remove（index）的时候会返回

5. removeAll & retainAll(Collection<? extends E> c)
移除（保留）所有对象

6. ListIterator<E> listIterator(int index)
一个list的Iterator，可以返回next和preprevious的index
并且支持set 和 add

7. subList
ArrayList的sublist里维护一个parent，对subList操作，相当于对父对象操作；

8. modcount
通过这个来维护修改动作，如果arraylist操作过了，那之前放出去的Iterator，sublist都会失效

LinkedList

内部维护一个双向列表；

    transient LinkedList.Node<E> first;
    transient LinkedList.Node<E> last;   

然后就是实现了Queue接口；

HashMap

内部维护一个数组

transient Node<K,V>[] table;

放置一个对象时

1. 对key进行hash，然后放置在对应的位置上；
2. 这个时候如果冲突了，会在这个table[index]上相当于形成了一个列表；
3. 当这个列表过长是会转变成一个红黑树；

当table的size超过阈值的时候
会把这个table的size翻倍，然后把数组的对象重新分配；

HashSet

内部就是维护了一个HashMap

HashTable

线程安全

和HashMap很像，对于单个操作实现了synchronized
但是不会变成红黑树

LinkedHashMap

继承自HashMap

会维护一个双向列表(根绝accessOrder 设定维护的是什么)
1. accessOrder true ： 访问的时候，也会修改map的顺序
2. false : 插入顺序修改列表的顺序

遍历的时候，根据列表来遍历。所以这是有序的

Vector

实现了 线程安全的 ArrayList

总结图片