jdk源码阅读笔记（1.9版，2018年2月12日）

ArrayList

1. 容器默认大小为10，位置不够了自动扩增，每次增加当前长度的50%。

   

2. 数组容量扩增到Integer.MAX_VALUE-8的时候，就会开始限制数组扩充，超过Integer.MAX_VALUE,抛内存溢出异常。

1. clone是浅拷贝，List中的引用指向的还是相同数据

1. 线程不安全

2. 迭代器中的expectedModCount和modCount：迭代器初始化时，会用modCount去初始化expectedModCount，在迭代器的操作中都要检查这两个值的等值性，不相等抛出ConcurrentModificationException异常表示当前List正在被修改，为什么呢？如下：

   ​ List本身的add和remove操作时都会修改modCount的值，如果在迭代器循环迭代过程中调用了List本身的add和remove方法就会导致两个值不想等而抛出异常，而迭代器本身的remove则不会有这个问题，它会在remove完成后重新更新一遍expectedModCount保持两个值的等值性。

1. ListIterator和普通迭代器类似，只是多了双向迭代的功能。

1. ArrayList本身的sort其实是调用Arrays.sort传入比较器实现的

   

LinkedList

1. LinkedList是一个双向链表，用index查找某个位置的元素，相当于遍历链表，速度非常慢。!

2. 在添加删除等操作时，需要维护first,last,size三个重要的变量

   

   ​

   1. 线程不安全
   2. 链表支持头增删，尾增删，指定结点前或后增删
   3. List中的Node为private内部类，无法手动创建，这是为了保证用户拿到的所有Node都是LinkedList生成的，即其成员next和pre为正确指定的值。
   4. LinkedList中的Element元素支持插入空值，和HashMap一样
   5. LinkedList的迭代器中也有expectedModCount检测链表的修改状态，迭代器循环迭代时只能用迭代器的remove方法。
   6. clone为浅拷贝
   7. LinkedList可以当Deque用，因为有实现相应接口。

HashMap

1. HashMap支持null的key和value；
2. Equals会比较两个Map地址，若地址不等，则迭代比较每个元素，都相同才返回true；

1. Hashcode为每个元素Entry的hashcode的和。（也是在抽象MAP中）

2. Entry是一个键值对封装体，都复写了Object的很多相应方法，建立了K-V映射关系

3. Clone浅拷贝

4. HashMap默认大小16，最大大小2的30次方

5. 结构：一开始使用数据结构书中的以链表为元素的数组存储元素，元素得到的哈希值相同的放在数组中哈希值对应位置的链表的末尾，操作很简单，但是有弊端，当同一个哈希值存在的元素过多的话，查询速度很差，这不是是同哈希表想看到的结果，这时候采取的是转换成红黑树的办法。

6. 填充比：哈希表中插入的记录数占地址区间长度的比率称为装填因子α，α=表中填入的记录数/地址区间长度。默认0.75，超过之后就会扩容。

7. 线程不安全

8. hashCode

9. put()方法步骤：
   （1）检查表是否需要扩容；
   （2）检查hashCode指定位置是否需要newNode；
   （3）数组中指定位置已经有节点了，先检查和第一个节点是否一致，一致则找到节点；
   （4）不一致，检查是否为红黑树，通过红黑树查找节点；
   （5）不是红黑树的，接着链表查找，找到元素节点或者找不到新建节点，并检查是否需要转换成红黑树；
   （6）若找到的节点不为空，赋值Value；
   （7）检查数组是否需要扩容；
   （8）返回oldValue；

10. resize()：重新调整数组大小，新旧数组复制，较耗时。

    因为hashMap容器的容量始终为2的n次幂，根据上面的hashCode()算法，每次扩容，相当于当前元素对象多一个位可以运算，要么就在原来的index，要么循环增加2的(n-1)次幂。例如原来是16，后来扩容为32，那么原本在index=8的元素，要么还在8，要么在（8+16）的位置，这样可以加快扩容之后复制数组的效率

11. get()方法：计算key的hashCode，从而找到数组位置，对比数组中元素第一个节点和key是否一致，一致返回该节点，否则判断节点是否是红黑树节点来分类讨论（红黑树按照红黑树的方式查找该key，链表则循环下去接着找），如果找到key一致的则返回，否则返回null，表示该key暂时还没有值

12. Remove()方法：通过hashCode找到数组位置，对比第一个节点，再对比红黑树或链表，找到节点之后删除节点并返回

13. HashMap的增删方法也和List一样有ConcurrentModificationException异常，使用迭代器需注意

LinkedHashMap

1、 HashMap的子类
2、 存储方式和HashMap都一样，只是在put元素的时候顺带存储了元素的存入先后顺序（entryKey），在迭代器遍历的时候，输出的结果顺序是和插入元素时的插入先后顺序一致的
3、 有ConcurrentModificationException
4、 可以设置插入元素时自动删除最旧的元素

TreeMap

1. 实现了NavigableMap接口（是SortedMap的子接口）；
2. 使用红黑树作为底层实现，排序平衡树，有序，提供一系列有序集合才有的方法（获取第一个，获取某一范围内的），排序按照Key为标准进行比较（subMap）
3. 默认为升序排序，descendingMap()返回降序排序的实例
4. 维护了比较器comparator、树根节点root、size属性
5. putAll方法时，先判断传入的集合是否是SortedMap，是的话利用比较器直接通过红黑树批量插入再调整红黑树，较为高效，若不是，则遍历整个集合把每个元素一一插入
6. 元素间比较：若内部比较器不为空，则用内部比较器进行key的比较，否则元素本身要实现Comparable接口以提供比较
7. 不允许key为空
8. Entry就是红黑树的节点
9. Put：按照排序树查找key，找到直接修改value，没找到就插入一个节点，并进行红黑树调整
10. Remove：按照key查找相应的Entry，再把这个节点从红黑树中删除，并进行红黑树调整
11. 浅拷贝

HashTable

1. Dictionary的子类（过时的）
2. 浅拷贝
3. 
4. Map操作是方法粒度的线程安全的
5. 
6. 不允许key为空或value为空
7. 遍历迭代器使用Enumeration方式
8. HashMap的get方法返回null表示没有该key或者该key对应的value为空；而HashTable的get返回空则一定是没有该key

IdentityHashMap

1. 和WeakHashMap一样，用一个特殊值表示null的key
2. 线程不安全
3. 浅拷贝
4. hash()

1. 只有当两个对象==才是相等，而HashMap只要key.equals(k)=true
2. 底层用一个数组实现存储，下标0,2,4,6…存储key，下标1,3,5,7…存储value，
   remove时，将相应位置的值赋空，并把后面的元素往前移；
   put时一次递增两个位置下标来查找；
   hashCode采用native底层实现，根据内存地址计算哈希值，两个key只有==时才算相同，在字符串常量池和堆区的两个相同字符串不算相等

HashSet

底层由HashMap提供支持，实现容器中元素单一出现的目的。

TreeSet

1. 有序的Set，元素需要实现Comparable接口，要求compareTo和equals的返回结果一致；
2. Comparator负责提供给TreeMap比较器
3. 具有有序集合的一些性质：比如提取比某个值大的子集合，提取在某一范围内的子集合等有序才具有的操作
4. 实现了NavigableSet接口，NavigableSet是SortedSet的子接口
5. 底层为TreeMap提供支持，Set中的元素就是Map的Key
6. 浅拷贝
7. PRESENT：Set提供给底层Map的Value，所有Key共用通过一个Value

Queue

单向队列，队头取出，队尾加入。

Deque

双向队列，双向添加删除，分别有两个方向的迭代器。

Vector

和ArrayList都一样，但是提供了方法粒度级别的同步机制

Stack

1. 继承于Vector，线程安全，底层数组实现，自动扩张
2. 栈顶增删查操作，并提供整栈元素搜索功能

WeakHashMap

1. 底层实现跟HashMap基本一致
2. 弱引用：不能保证引用还存在时避免引用指向的内存不被垃圾回收机制回收
3. Entry在new的时候创建了一个弱引用对象并加入弱引用队列中，该弱引用指向的内存空间随时可能被回收，被回收后再使用该弱引用返回null，并且内部的多数Map操作都附带了弱引用回收操作，把那些已经被回收的弱引用从弱引用队列中移除，不影响该弱引用在hashTable中链表指向的下一个节点

Collections

1. 封装了集合的很多常用工具静态方法，二分查找、排序、子集合、替换、比较等
2. synchronizedCollection等一系列的方法提供了将普通集合转换成代码块粒度的同步，使用mutex进行同步
3. singleton提供了集合中单元素的集合静态方法
4. unmodifiableCollection提供了将所给集合变成不可写的集合的方法

Arrays

1. 数组的常用工具静态方法，排序，二分查找，数组填充，子数组提取，深equals，深hashCode，数组复制等
2. 基本数据类型使用插入排序（长度小于7）和快速排序（长度大于7）
3. Object的数组使用归并排序（稳定排序）

Array

​ 反射包中的Array，表示所有的数组，由native本地方法实现，一个数组就相当于是一个Object。原生数组中的相关调用就相当于是调用这个类中的相关方法。

String

1. 对char数组的封装，相当于是一个元素为char的ArrayList，没有长度自动伸缩功能；
2. 封装了字符串操作的常用方法，底层实现都是在反复操纵char[]；
3. Equals重写成了char[]的各个元素；
4. hashCode重写成char[]计算的哈希值；
5. split通过不断查找切割子串的位置来substring字符串得到字符串分割结果数组；
6. String长度创建后不变，改变的话就是整个char[]变了，不能对char[]数组中的指定下标进行随机修改；

注:String内部使用byte数组存储，解析的时候使用char数组，当出现中文时，因为char是两个字节的，所以中文只能存储Unicode的部分（char数组也是只能存储BMP部分，有少量汉字无法存储）。

StringBuilder

1. 底层char[]实现，相当于ArrayList的char元素的实现，提供元素增删改查
2. 线程不安全
3. 可设定初始长度，防止扩充长度的资源消耗
4. 可修改指定下标的char值
5. 动态修改动态添加，长度可变

StringBuffer

与StringBuilder继承相同抽象类，底层相同实现(都是可以随机修改char数组中的指定下标元素而不创建新对象)，但是StringBuffer是线程安全的

ThreadLocal

1. 多线程同时访问统一共享属性的时候产生的线程安全问题的一种解决方案，适用于每个线程对这个共享属性的修改都不会影响到其他线程，即不需要线程间通信的这种情况；这样做是为了避免使用同步锁导致的效率问题（每个线程各创建一个共享数据的副本分别服务于各自的线程）；
2. 每个Thread内部有两个类似Map的属性ThreadLocalMap，通过Thread.currentThread();获取当前的线程实例，再获取本线程中的Map实例，通过对这个Map中进行数据的增删，实现共享数据的副本和线程绑定的目的，从而在一定程度上避免线程安全问题。

Comparable和Comparator

Comparable是Entity元素的可实现接口，实现该接口的Entity在和本类型的其他Entity比较时就是通过该接口的compareTo方法进行比较；
Comparator：提供给集合的比较器接口，该比较器可以通过传入相同类型的两个对象进行compare比较并返回相应值判断出大小关系（通常保证比较结果要和该类型的equals返回结果相一致）。