底层结构
底层结构
Java里一些数据结构，基础语句的底层实现原理
System.out.println()
参考原文：https://blog.csdn.net/lierming__/article/details/88353608
部分解释
- System： 是一个类，位于java.lang包下
- out： 是System类的一个标准字节输出流成员变量，PrintStream类型，用final类型修饰，不能更改。
- 补充：另外一种“打印流”是 PrintWriter ，这是一个“字符输出流”
- println()：是位于PrintStream的一个成员方法
方法代码详解
public void println(Object x) {
String s = String.valueOf(x);
synchronized (this) {
print(s);
newLine();
}
// 利用类的toString方法获取对象的字符串表示
public static String valueOf(Object obj) { // java.lang.String
return (obj == null) ? "null" : obj.toString();
}
// 判空，若空则为null
public void print(String s) { // java.io.PrintStream
if (s == null) {
s = "null";
}
write(s);
}
// 刷新流的缓冲，将输出字节写入底层输出，如果发生异常，则调用当前线程的终端
private void write(String s) { // java.io.PrintStream下的
try {
synchronized (this) {
ensureOpen(); // 判断当前的输出流是否开着
textOut.write(s);
private BufferedWriter textOut;
textOut.flushBuffer();
charOut.flushBuffer();
private OutputStreamWriter charOut;
if (autoFlush && (s.indexOf('\n') >= 0))
private final boolean autoFlush
out.flush();
}
}catch (InterruptedIOException x) {
Thread.currentThread().interrupt();
} catch (IOException x) {
trouble = true; // PrintStream 里面的 private boolean trouble = false;
}
}
// 将光标往下移，如果发生异常，则调用当前线程的终端
private void newLine() { // java.io.PrintStream下的
try {
synchronized (this) {
ensureOpen(); // 判断当前的输出流是否开着
textOut.newLine();
textOut.flushBuffer();
charOut.flushBuffer();
if (autoFlush)
out.flush();
}
} catch (InterruptedIOException x) {
Thread.currentThread().interrupt();
} catch (IOException x) {
trouble = true;
}流程图解
String
参考文章：https://blog.csdn.net/ifwinds/article/details/80849184
底层代码
Serializable：Java为我们提供了Serializable接口，这是一个空接口；如果一个类实现了Serializable接口，那么就代表这个类是自动支持序列化和反序列化的
CharSequence：表示char值的一个可读序列
Comparable ：排序接口
public final class String
implements java.io.Serializable, Comparable<String>, CharSequence {
private final char value[];
private int hash; // Default to 0
...
}- String类被final关键字修饰，意味着String类不能被继承，并且它的成员方法都默认为final方法；字符串一旦创建就不能再修改。
- String类实现了Serializable、CharSequence、 Comparable接口。
- String实例的值是通过字符数组实现字符串存储的。
"+"拼接
其中字符串连接是通过 StringBuilder（或 StringBuffer）类及其append 方法实现的，对象转换为字符串是通过 toString 方法实现的
/**
* 测试代码
*/
public class Test {
public static void main(String[] args) {
int i = 10;
String s = "abc";
System.out.println(s + i);
}
}
/**
* 反编译后
*/
public class Test {
public static void main(String args[]) {
byte byte0 = 10;
String s = "abc";
System.out.println((new StringBuilder()).append(s).append(byte0).toString());
}
}
// 特殊情况，也就是当"+"两端均为编译期确定的字符串常量时，直接将两个字符串常量拼接好
//对于final修饰的变量，它在编译时被解析为常量值的一个本地拷贝存储到自己的常量池中或嵌入到它的字节码流中所以此时的"a" + s1和"a" + "b"效果是一样的。故结果为true。字符串常量池
在Java的内存分配中，总共3种常量池，分别是Class常量池、运行时常量池、字符串常量池
每当创建字符串常量时，JVM会首先检查字符串常量池，如果该字符串已经存在常量池中，那么就直接返回常量池中的实例引用。
String字符串的不可变性，常量池中一定不存在两个相同的字符串
内存
在HotSpot VM中字符串常量池是通过一个StringTable类实现的，它是一个Hash表，默认值大小长度是1009；这个StringTable在每个HotSpot VM的实例中只有一份，被所有的类共享；字符串常量由一个一个字符组成，放在了StringTable上。要注意的是，如果放进String Pool的String非常多，就会造成Hash冲突严重，从而导致链表会很长，而链表长了后直接会造成的影响就是当调用String.intern时性能会大幅下降（因为要一个一个找）。
在JDK6及之前版本，字符串常量池是放在Perm Gen区(也就是方法区)中的，StringTable的长度是固定的1009；在JDK7版本中，字符串常量池被移到了堆中，StringTable的长度可以通过-XX:StringTableSize=66666参数指定。至于JDK7为什么把常量池移动到堆上实现，原因可能是由于方法区的内存空间太小且不方便扩展，而堆的内存空间比较大且扩展方便。
intern
直接使用双引号声明出来的String对象会直接存储在字符串常量池中，如果不是用双引号声明的String对象，可以使用String提供的intern方法。intern 方法是一个native方法，intern方***从字符串常量池中查询当前字符串是否存在，如果存在，就直接返回当前字符串；如果不存在就会将当前字符串放入常量池中，之后再返回。
主要区别
1）String是不可变字符序列，StringBuilder和StringBuffer是可变字符序列。
2）执行速度StringBuilder > StringBuffer > String。
3）StringBuilder是非线程安全的，StringBuffer是线程安全的
Java引用类型原理剖析
参考文档：https://github.com/farmerjohngit/myblog/issues/10
java中一共有4种引用类型(其实还有一些其他的引用类型比如FinalReference)：强引用、软引用、弱引用、虚引用。
软引用、弱引用、虚引用的实现，这三种引用类型都是继承于Reference这个类，主要逻辑也在Reference中。
Reference
public abstract class Reference<T> {
//引用的对象
private T referent;
//回收队列，由使用者在Reference的构造函数中指定
volatile ReferenceQueue<? super T> queue;
//当该引用被加入到queue中的时候，该字段被设置为queue中的下一个元素，以形成链表结构
volatile Reference next;
//在GC时，JVM底层会维护一个叫DiscoveredList的链表，存放的是Reference对象，discovered字段指向的就是链表中的下一个元素，由JVM设置
transient private Reference<T> discovered;
//进行线程同步的锁对象
static private class Lock { }
private static Lock lock = new Lock();
//等待加入queue的Reference对象，在GC时由JVM设置，会有一个java层的线程(ReferenceHandler)源源不断的从pending中提取元素加入到queue
private static Reference<Object> pending = null;
}主要分为Native层和Java层两个部分。
Native层在GC时将需要被回收的Reference对象加入到DiscoveredList中（代码在referenceProcessor.cpp中process_discovered_references方法），然后将DiscoveredList的元素移动到PendingList中（代码在referenceProcessor.cpp中enqueue_discovered_ref_helper方法）,PendingList的队首就是Reference类中的pending对象。
数据结构
Java基本数据结构
java没有无符号整数
数据结构 长度
byte -2^7 ~ 2^7-1 -128 ~ 127 1字节
short -2^15 ~ 2^15-1 -32768 ~ 32767 2字节
int -2^31 ~ 2^31-1 -2147483648 ~ 2147483647 4字节
long -2^63 ~ 2^63-1 -9223372036854774808 ~ 9223372036854774807 8字节
float 4字节
double 8字节
char 2字节
ArrayList
参考文档：https://blog.csdn.net/zxt0601/article/details/77281231
- ArrayList 的底层是数组队列，相当于动态数组。
- 在添加大量元素前，应用程序可以使用ensureCapacity 操作来增加 ArrayList 实例的容量。这可以减少递增式再分配的数量。
- ArrayList 实现了RandmoAccess接口，即提供了随机访问功能。
- ArrayList 实现了Cloneable接口，即覆盖了函数clone()，能被克隆。
- ArrayList 实现java.io.Serializable接口，这意味着ArrayList支持序列化，能通过序列化去传输。
- ArrayList中的操作不是线程安全的！所以，建议在单线程中才使用ArrayList，而在多线程中可以选择Vector或者CopyOnWriteArrayList。
构造方法
构造函数走完之后，会构建出数组elementData和数量size
//默认构造函数里的空数组
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
//存储集合元素的底层实现：真正存放元素的数组
transient Object[] elementData; // non-private to simplify nested class access
//当前元素数量
private int size;
//默认构造方法
public ArrayList() {
//默认构造方法只是简单的将 空数组赋值给了elementData
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
//空数组
private static final Object[] EMPTY_ELEMENTDATA = {};
//带初始容量的构造方法
public ArrayList(int initialCapacity) {
//如果初始容量大于0，则新建一个长度为initialCapacity的Object数组.
//注意这里并没有修改size(对比第三个构造函数)
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {//如果容量为0，直接将EMPTY_ELEMENTDATA赋值给elementData
this.elementData = EMPTY_ELEMENTDATA;
} else {//容量小于0，直接抛出异常
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
//利用别的集合类来构建ArrayList的构造函数
public ArrayList(Collection<? extends E> c) {
//直接利用Collection.toArray()方法得到一个对象数组，并赋值给elementData
elementData = c.toArray();
//因为size代表的是集合元素数量，所以通过别的集合来构造ArrayList时，要给size赋值
if ((size = elementData.length) != 0) {
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)//这里是当c.toArray出错，没有返回Object[]时，利用Arrays.copyOf 来复制集合c中的元素到elementData数组中
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
//如果集合c元素数量为0，则将空数组EMPTY_ELEMENTDATA赋值给elementData
// replace with empty array.
this.elementData = EMPTY_ELEMENTDATA;
}
}常用API
// 每次 add之前，都会判断add后的容量，是否需要扩容。
// 1. 先判断是否越界，是否需要扩容。
// 2. 如果扩容， 就复制数组。
// 3. 然后设置对应下标元素值。
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;//在数组末尾追加一个元素，并修改size
return true;
}
private static final int DEFAULT_CAPACITY = 10;//默认扩容容量 10
private void ensureCapacityInternal(int minCapacity) {
//利用 == 可以判断数组是否是用默认构造函数初始化的
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;//如果确定要扩容，会修改modCount
// modCount就是修改次数，当集合在迭代时候，会以这个为标志，如果迭代器里的modCount与集合的不一致，会抛出异常
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
//需要扩容的话，默认扩容一半,如果扩容一半不够，就用目标的size作为扩容后的容量
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);//默认扩容一半
if (newCapacity - minCapacity < 0)//如果还不够 ，那么就用 能容纳的最小的数量。（add后的容量）
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);//拷贝，扩容，构建一个新数组，
}
public void add(int index, E element) {
rangeCheckForAdd(index);//越界判断 如果越界抛异常
ensureCapacityInternal(size + 1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1,
size - index); //将index开始的数据 向后移动一位
elementData[index] = element;
size++;
}
public boolean addAll(Collection<? extends E> c) {
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew); // Increments modCount //确认是否需要扩容
System.arraycopy(a, 0, elementData, size, numNew);// 复制数组完成复制
size += numNew;
return numNew != 0;
}
public boolean addAll(int index, Collection<? extends E> c) {
rangeCheckForAdd(index);//越界判断
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew); // Increments modCount //确认是否需要扩容
int numMoved = size - index;
if (numMoved > 0)
System.arraycopy(elementData, index, elementData, index + numNew,
numMoved);//移动（复制)数组
System.arraycopy(a, 0, elementData, index, numNew);//复制数组完成批量赋值
size += numNew;
return numNew != 0;
}
public E remove(int index) {
rangeCheck(index);//判断是否越界
modCount++;//修改modeCount 因为结构改变了
E oldValue = elementData(index);//读出要删除的值
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);//用复制 覆盖数组数据
elementData[--size] = null; // clear to let GC do its work //置空原尾部数据 不再强引用， 可以GC掉
return oldValue;
}
//根据下标从数组取值 并强转
E elementData(int index) {
return (E) elementData[index];
}
//删除该元素在数组中第一次出现的位置上的数据。 如果有该元素返回true，如果false。
public boolean remove(Object o) {
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
fastRemove(index);//根据index删除元素
return true;
}
} else {
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
}
//不会越界 不用判断 ，也不需要取出该元素。
private void fastRemove(int index) {
modCount++;//修改modCount
int numMoved = size - index - 1;//计算要移动的元素数量
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);//以复制覆盖元素 完成删除
elementData[--size] = null; // clear to let GC do its work //置空 不再强引用
}
//批量删除,当用来作为删除元素的集合里的元素多余被删除集合时，也没事，只会删除它们共同拥有的元素。
public boolean removeAll(Collection<?> c) {
Objects.requireNonNull(c);//判空
return batchRemove(c, false);
}
//批量移动
private boolean batchRemove(Collection<?> c, boolean complement) {
final Object[] elementData = this.elementData;
int r = 0, w = 0;//w 代表批量删除后 数组还剩多少元素
boolean modified = false;
try {
//高效的保存两个集合公有元素的算法
for (; r < size; r++)
if (c.contains(elementData[r]) == complement) // 如果 c里不包含当前下标元素，
elementData[w++] = elementData[r];//则保留
} finally {
// Preserve behavioral compatibility with AbstractCollection,
// even if c.contains() throws.
if (r != size) { //出现异常会导致 r !=size , 则将出现异常处后面的数据全部复制覆盖到数组里。
System.arraycopy(elementData, r,
elementData, w,
size - r);
w += size - r;//修改 w数量
}
if (w != size) {//置空数组后面的元素
// clear to let GC do its work
for (int i = w; i < size; i++)
elementData[i] = null;
modCount += size - w;//修改modCount
size = w;// 修改size
modified = true;
}
}
return modified;
}
// 不会修改modCount，相对增删是高效的操作。
public E set(int index, E element) {
rangeCheck(index);//越界检查
E oldValue = elementData(index); //取出元素
elementData[index] = element;//覆盖元素
return oldValue;//返回元素
}
public E get(int index) {
rangeCheck(index);//越界检查
return elementData(index); //下标取数据
}
E elementData(int index) {
return (E) elementData[index];
}
public void clear() {
modCount++;//修改modCount
// clear to let GC do its work
for (int i = 0; i < size; i++) //将所有元素置null
elementData[i] = null;
size = 0; //修改size
}
//普通的for循环寻找值，只不过会根据目标对象是否为null分别循环查找。
public boolean contains(Object o) {
return indexOf(o) >= 0;
}
//普通的for循环寻找值，只不过会根据目标对象是否为null分别循环查找。
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;
}
// 迭代器
public Iterator<E> iterator() {
return new Itr();
}
private class Itr implements Iterator<E> {
int cursor; // index of next element to return //默认是0
int lastRet = -1; // index of last element returned; -1 if no such //上一次返回的元素 (删除的标志位)
int expectedModCount = modCount; //用于判断集合是否修改过结构的 标志
public boolean hasNext() {
return cursor != size;//游标是否移动至尾部
}
@SuppressWarnings("unchecked")
public E next() {
checkForComodification();
int i = cursor;
if (i >= size)//判断是否越界
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length)//再次判断是否越界，在 我们这里的操作时，有异步线程修改了List
throw new ConcurrentModificationException();
cursor = i + 1;//游标+1
return (E) elementData[lastRet = i];//返回元素 ，并设置上一次返回的元素的下标
}
public void remove() {//remove 掉 上一次next的元素
if (lastRet < 0)//先判断是否next过
throw new IllegalStateException();
checkForComodification();//判断是否修改过
try {
ArrayList.this.remove(lastRet);//删除元素 remove方法内会修改 modCount 所以后面要更新Iterator里的这个标志值
cursor = lastRet; //要删除的游标
lastRet = -1; //不能重复删除 所以修改删除的标志位
expectedModCount = modCount;//更新 判断集合是否修改的标志，
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
//判断是否修改过了List的结构，如果有修改，抛出异常
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}HashMap
- HashMap底层是一个数组，数组的对象是一个node。
- node继承接口Entry，有四个成员变量，哈希值hash，键值key，值value还有next指针。
- 有两个核心的方法，一个是put，一个是get。
- put方法，先将key值通过哈希函数转换为哈希值，如果key是null的话，那么哈希值为0。然后根据哈希值确定在数组的位置。HashMap采用的解决hash冲突的方法是链地址法。
- 当插入时若数组未初始化，应该调用resize进行初始化。若已经初始化，找到数组对应位置，如果该位置没有值，直接放进去，若有，依次遍历且判断是否有key相同的结点，若有，更新值，若无，放在队尾。
- get方法。和put类似，若表为空，也会触发初始化。根据key生成哈希值找到对应的数组位置，进行遍历，如果找到对应的key，就返回，如果没有就返回null。
- jdk1.8之后如果由哈希冲突形成的链表长度大于8，在数组长度在64之前，用数组扩容进行解决，如果是大于64，那么将转化为红黑树。
- HashMap的扩容机制，当大于数组长度乘以扩容因子时，进行扩容，扩容长度是原来的两倍。如果一开始指定初始长度，也会扩充为2次幂对应的长度。
扩容机制
当向容器添加元素的时候，会判断当前容器的元素个数，如果大于等于阈值---即当前数组的长度乘以加载因子的值的时候，就要自动扩容啦。
扩容(resize)：重新计算容量，向HashMap对象里不停的添加元素，而HashMap对象内部的数组无法装载更多的元素时，对象就需要扩大数组的长度，以便能装入更多的元素。当然Java里的数组是无法自动扩容的，方法是使用一个新的数组代替已有的容量小的数组。
// jdk 1.7
void resize(int newCapacity) { //传入新的容量Entry[] oldTable = table; //引用扩容前的Entry数组 int oldCapacity = oldTable.length; if (oldCapacity == MAXIMUM_CAPACITY) { //扩容前的数组大小如果已经达到最大(2^30)了 threshold = Integer.MAX_VALUE; //修改阈值为int的最大值(2^31-1)，这样以后就不会扩容了 return; } Entry[] newTable = new Entry[newCapacity]; //初始化一个新的Entry数组 transfer(newTable); //！！将数据转移到新的Entry数组里 table = newTable; //HashMap的table属性引用新的Entry数组 threshold = (int) (newCapacity * loadFactor);//修改阈值}
// transfer()方法将原有Entry数组的元素拷贝到新的Entry数组里
void transfer(Entry[] newTable) {Entry[] src = table; //src引用了旧的Entry数组 int newCapacity = newTable.length; for (int j = 0; j < src.length; j++) { //遍历旧的Entry数组 Entry<K, V> e = src[j]; //取得旧Entry数组的每个元素 if (e != null) { src[j] = null;//释放旧Entry数组的对象引用（for循环后，旧的Entry数组不再引用任何对象） do { Entry<K, V> next = e.next; int i = indexFor(e.hash, newCapacity); //！！重新计算每个元素在数组中的位置 // 单链表的头插入方式 e.next = newTable[i]; //标记[1] newTable[i] = e; //将元素放在数组上 e = next; //访问下一个Entry链上的元素 } while (e != null); } }}
static int indexFor(int h, int length) {
return h & (length - 1);
}
// jdk 1.8
// 均匀的把之前的冲突的节点分散到新的bucket了,JDK1.8不会倒置链表元素
1 final Node<K,V>[] resize() {
/* 1、如果初始化的时候带了参数（HashMap(int initialCapacity, float loadFactor)），
那么newCap就是你的initialCapacity参数,threshold就是 (int)(initialCapacity*loadFactor)
2、否则就按默认的算 initialCapacity = 16，threshold = 12
3、如果已经有元素了，那么直接扩容2倍，如果oldCap >= DEFAULT_INITIAL_CAPACITY了，那么
threshold也扩大两倍
*/
2 Node<K,V>[] oldTab = table;
3 int oldCap = (oldTab == null) ? 0 : oldTab.length;
4 int oldThr = threshold;
5 int newCap, newThr = 0;
6 if (oldCap > 0) {
7 // 超过最大值就不再扩充了，就只好随你碰撞去吧
8 if (oldCap >= MAXIMUM_CAPACITY) {
9 threshold = Integer.MAX_VALUE;
10 return oldTab;
11 }
12 // 没超过最大值，就扩充为原来的2倍
13 else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
14 oldCap >= DEFAULT_INITIAL_CAPACITY)
15 newThr = oldThr << 1; // double threshold
16 }
17 else if (oldThr > 0) // initial capacity was placed in threshold
18 newCap = oldThr;
19 else { // zero initial threshold signifies using defaults
20 newCap = DEFAULT_INITIAL_CAPACITY;
21 newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
22 }
23 // 计算新的resize上限
24 if (newThr == 0) {
25
26 float ft = (float)newCap * loadFactor;
27 newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
28 (int)ft : Integer.MAX_VALUE);
29 }
30 threshold = newThr;
31 @SuppressWarnings({"rawtypes"，"unchecked"})
32 Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
33 table = newTab;
34 if (oldTab != null) {
35 // 把每个bucket都移动到新的buckets中
36 for (int j = 0; j < oldCap; ++j) {
37 Node<K,V> e;
38 if ((e = oldTab[j]) != null) {
39 oldTab[j] = null;
// 如果原来数组对应的元素是单独一个的话
40 if (e.next == null)
41 newTab[e.hash & (newCap - 1)] = e;
// 如果已经转换为红黑树，那么将红黑树的结点rehash之后根据hash放到新位置
42 else if (e instanceof TreeNode)
43 ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
44 else { // 链表优化重hash的代码块
// 经过rehash之后，元素的位置要么是在原位置，要么是在原位置再移动2次幂的位置
45 Node<K,V> loHead = null, loTail = null;
46 Node<K,V> hiHead = null, hiTail = null;
47 Node<K,V> next;
48 do {
49 next = e.next;
50 /* 如果是true，表明(e.hash & (newCap - 1))还会和
e.hash & (oldCap - 1)一样。因为oldCap和newCap是2的次幂，
并且newCap是oldCap的两倍 */
51 if ((e.hash & oldCap) == 0) {
52 if (loTail == null)
53 loHead = e;
54 else
55 loTail.next = e;
56 loTail = e;
57 }
58 // 原索引+oldCap
59 else {
60 if (hiTail == null)
61 hiHead = e;
62 else
63 hiTail.next = e;
64 hiTail = e;
65 }
66 } while ((e = next) != null);
67 // 原索引放到bucket里
68 if (loTail != null) {
69 loTail.next = null;
70 newTab[j] = loHead;
71 }
72 // 原索引+oldCap放到bucket里
73 if (hiTail != null) {
74 hiTail.next = null;
75 newTab[j + oldCap] = hiHead;
76 }
77 }
78 }
79 }
80 }
81 return newTab;
82 }n为table的长度，图（a）表示扩容前的key1和key2两种key确定索引位置的示例，图（b）表示扩容后key1和key2两种key确定索引位置的示例，其中hash1是key1对应的哈希值(也就是根据key1算出来的hashcode值)与高位与运算的结果。
关键就在这个新增的bit这里，如果是0，那么就跟原来的位置一致，如果是1，那么就是原位置加旧容量的位置。
判断这个bit，就用(e.hash & oldCap) == 0，这个是最大的精髓点。
ConcurrentHashMap
JDK1.7
首先将数据分为一段一段的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据时，其他段的数据也能被其他线程访问。
ConcurrentHashMap 是由 Segment 数组结构和 HashEntry 数组结构组成。
Segment 实现了 ReentrantLock,所以 Segment 是一种可重入锁，扮演锁的角色。HashEntry 用于存储键值对数据。
static class Segment<K,V> extends ReentrantLock implements Serializable {
}Copy to clipboardErrorCopied一个 ConcurrentHashMap 里包含一个 Segment 数组。Segment 的结构和HashMap类似，是一种数组和链表结构，一个 Segment 包含一个 HashEntry 数组，每个 HashEntry 是一个链表结构的元素，每个 Segment 守护着一个HashEntry数组里的元素，当对 HashEntry 数组的数据进行修改时，必须首先获得对应的 Segment的锁。
JDK 1.8
ConcurrentHashMap取消了Segment分段锁，采用CAS和synchronized来保证并发安全。数据结构跟HashMap1.8的结构类似，数组+链表/红黑二叉树。Java 8在链表长度超过一定阈值（8）时将链表（寻址时间复杂度为O(N)）转换为红黑树（寻址时间复杂度为O(log(N))）
synchronized只锁定当前链表或红黑二叉树的首节点，这样只要hash不冲突，就不会产生并发，效率又提升N倍。
如何计算size
jdk 1.7
在1.7版本中，有一个重要的类Segment，利用它来实现分段锁
static final class Segment<K,V> extends ReentrantLock implements Serializable {
private static final long serialVersionUID = 2249069246763182397L;
// 最大尝试获取锁次数，tryLock可能会阻塞，准备锁住segment操作获取锁。
在多处理器中，用一个有界的尝试次数，保证在定位node的时候，可以从缓存直接获取。
static final int MAX_SCAN_RETRIES =
Runtime.getRuntime().availableProcessors() > 1 ? 64 : 1;
//segment内部的Hash table，访问HashEntry，通过具有volatile的entryAt/setEntryAt方法
transient volatile HashEntry<K,V>[] table;
//segment的table中HashEntry的数量，只有在lock或其他保证可见性的volatile reads中，才可以访问count
transient int count;
//在segment上所有的修改操作数。尽管可能会溢出，但它为isEmpty和size方法,提供了有效准确稳定的检查或校验。只有在lock或其他保证可见性的volatile reads中，才可以访问
transient int modCount;
transient int threshold;
final float loadFactor;
Segment(float lf, int threshold, HashEntry<K,V>[] tab) {
this.loadFactor = lf;
this.threshold = threshold;
this.table = tab;
}
}
static final class HashEntry<K,V> {
final int hash;
final K key;
volatile V value;
volatile HashEntry<K,V> next;
HashEntry(int hash, K key, V value, HashEntry<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
}刚一开始不加锁，前后计算两次所有segment里面的数量大小和，两次结果相等，表明没有新的元素加入，计算的结果是正确的。如果不相等，就对每个segment加锁，再进行计算，返回结果并释放锁。
public int size() {
final Segment<K,V>[] segments = this.segments;
int size;
boolean overflow; // true if size overflows 32 bits
long sum; // sum of modCounts
long last = 0L; // previous sum
int retries = -1; // first iteration isn't retry
try {
for (;;) {
// 用该变量控制第一次不加锁，第二次加锁
if (retries++ == RETRIES_BEFORE_LOCK) {
for (int j = 0; j < segments.length; ++j)
ensureSegment(j).lock(); // force creation
}
sum = 0L;
size = 0;
overflow = false;
// 获取所有segment，统计数量
for (int j = 0; j < segments.length; ++j) {
Segment<K,V> seg = segmentAt(segments, j);
if (seg != null) {
sum += seg.modCount;
int c = seg.count;
if (c < 0 || (size += c) < 0)
overflow = true;
}
}
if (sum == last)
break;
last = sum;
}
} finally {
if (retries > RETRIES_BEFORE_LOCK) {
for (int j = 0; j < segments.length; ++j)
segmentAt(segments, j).unlock();
}
}
return overflow ? Integer.MAX_VALUE : size;
}jdk 1.8
先利用sumCount()计算，然后如果值超过int的最大值，就返回int的最大值。但是有时size就会超过最大值，这时最好用mappingCount方法
public int size() {
long n = sumCount();
return ((n < 0L) ? 0 :
(n > (long)Integer.MAX_VALUE) ? Integer.MAX_VALUE :
(int)n);
}
public long mappingCount() {
long n = sumCount();
return (n < 0L) ? 0L : n; // ignore transient negative values
}sumCount有两个重要的属性baseCount和counterCells,如果counterCells不为空，那么总共的大小就是baseCount与遍历counterCells的value值累加获得的。
final long sumCount() {
CounterCell[] as = counterCells; CounterCell a;
long sum = baseCount;
if (as != null) {
for (int i = 0; i < as.length; ++i) {
if ((a = as[i]) != null)
sum += a.value;
}
}
return sum;
}baseCount是从哪里来的？
//当没有线程争用时，使用这个变量计数 private transient volatile long baseCount;
一个volatile变量，在addCount方***使用它，而addCount方法在put结束后会调用
addCount(1L, binCount);
在并发情况下，如果CAS修改baseCount失败后，就会使用到CounterCell类，会创建一个对象，通常对象的volatile的value属性是1。
// 一种用于分配计数的填充单元。改编自LongAdder和Striped64。请查看他们的内部文档进行解释。
@sun.misc.Contended
static final class CounterCell {
volatile long value;
CounterCell(long x) { value = x; }
}并发时，利用CAS修改baseCount失败后，会利用CAS操作修改CountCell的值，
if (as == null || (m = as.length - 1) < 0 ||
(a = as[ThreadLocalRandom.getProbe() & m]) == null ||
!(uncontended =
U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))) {
fullAddCount(x, uncontended);
return;
}如果上面CAS操作也失败了，在fullAddCount方法中，会继续死循环操作，知道成功。
for (;;) {
CounterCell[] as; CounterCell a; int n; long v;
if ((as = counterCells) != null && (n = as.length) > 0) {
if ((a = as[(n - 1) & h]) == null) {
if (cellsBusy == 0) { // Try to attach new Cell
CounterCell r = new CounterCell(x); // Optimistic create
if (cellsBusy == 0 &&
U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) {
boolean created = false;
try { // Recheck under lock
CounterCell[] rs; int m, j;
if ((rs = counterCells) != null &&
(m = rs.length) > 0 &&
rs[j = (m - 1) & h] == null) {
rs[j] = r;
created = true;
}
} finally {
cellsBusy = 0;
}
if (created)
break;
continue; // Slot is now non-empty
}
}ThreadLocal
- ThreadLocal提供了线程的局部变量，每个线程都可以通过set()和get()来对这个局部变量进行操作，但不会和其他线程的局部变量进行冲突，实现了线程的数据隔离。
- ThreadLocal的里面有一个静态内部类ThreadLocalMap，它才是在Thread线程内部保存数据容器。
- ThreadLocal中的set()方法，是获取当前线程，然后通过当前线程去获取线程的map。然后调用map的set()方法进行设置，如果map为空就先创建map。
- ThreadLocal中的get()方法，也同样是获取当前线程，然后通过当前线程去获取线程的map。然后调用map的get()方法，并把自己作为参数传入，返回一个对应的Entry对象。如果map为空调用 setInitialValue() 方法返回初始值，并保存到新创建的 ThreadLocalMap 中。默认值是null，可以通过重写initialValue()去设置。
- 作为真正容器的ThreadLocalMap，底层其实也是一个哈希数组，解决哈希冲突用的是开放定址法的线性探测。
- map的set()，就是通过key值，也就是ThreadLocal对象，计算出哈希值，然后找到数组对应的位置，如果那个位置已经有数据，就往上找，找到第一个key为null的位置放下，找的过程需要不断对比key值，如果有想等的，就覆盖。
- map的get()，也是通过将key值转换为哈希值然后找到数组的对应位置，然后向前匹配，知道匹配到或者遇到null值就返回。
- 内存泄露问题。map是弱引用着ThreadLocal。也就是说，如果没有其他对象引用着ThreadLocal，那么在下一次GC时，就会被回收，那么对应的键值就会被置为<null, value>。没有额外的操作，那么它就不会被回收，因为Thread一直存在，map也就会一直存在。由于这样，所以map的所有方法都有清楚无效Entry的操作。
Thread
基础结构
线程的名字是这样子的：主线程叫做main，其他线程是Thread-x
private static int threadInitNumber;
// 构造方法
public Thread() {
this((ThreadGroup)null, (Runnable)null, "Thread-" + nextThreadNum(), 0L);
}
// nextThreadNum()实现
private static synchronized int nextThreadNum() {
return threadInitNumber++;
}守护线程是为其他线程服务的
- 垃圾回收线程就是守护线程~
守护线程有一个特点：
当别的用户线程执行完了，虚拟机就会退出，守护线程也就会被停止掉了。
也就是说：守护线程作为一个服务线程，没有服务对象就没有必要继续运行了
public final void setDaemon(boolean on) { this.checkAccess(); // 只能在线程运行前设置，不然会报错 if (this.isAlive()) { throw new IllegalThreadStateException(); } else { this.daemon = on; } } // 查看是否有权限 public final void checkAccess() { SecurityManager security = System.getSecurityManager(); if (security != null) { security.checkAccess(this); } } public void checkAccess(Thread t) { if (t == null) { throw new NullPointerException("thread can't be null"); } else { if (t.getThreadGroup() == rootGroup) { this.checkPermission(SecurityConstants.MODIFY_THREAD_PERMISSION); } } }
线程优先级高仅仅表示线程获取的CPU时间片的几率高，但这不是一个确定的因素！
线程的优先级是高度依赖于操作系统的，Windows和Linux就有所区别(Linux下优先级可能就被忽略了)~
// 可以看到的是，Java提供的优先级默认是5，最低是1，最高是10：
public static final int MIN_PRIORITY = 1;
public static final int NORM_PRIORITY = 5;
public static final int MAX_PRIORITY = 10;
public final void setPriority(int newPriority) {
this.checkAccess();
if (newPriority <= 10 && newPriority >= 1) {
ThreadGroup g;
if ((g = this.getThreadGroup()) != null) {
if (newPriority > g.getMaxPriority()) {
newPriority = g.getMaxPriority();
}
// native方法
this.setPriority0(this.priority = newPriority);
}
} else {
throw new IllegalArgumentException();
}
}生命周期
sleep：调用sleep方***进入计时等待状态，等时间到了，进入的是就绪状态而并非是运行状态！
public static void sleep(long millis, int nanos) throws InterruptedException { if (millis < 0L) { throw new IllegalArgumentException("timeout value is negative"); } else if (nanos >= 0 && nanos <= 999999) { if (nanos >= 500000 || nanos != 0 && millis == 0L) { ++millis; } // native方法 sleep(millis); } else { throw new IllegalArgumentException("nanosecond timeout value out of range"); } }yield：调用yield方***先让别的线程执行，但是不确保真正让出
- 意思是：我有空，可以的话，让你们先执行
join：调用join方***等待该线程执行完毕后才执行别的线程~
public final synchronized void join(long millis) throws InterruptedException { long base = System.currentTimeMillis(); long now = 0L; if (millis < 0L) { throw new IllegalArgumentException("timeout value is negative"); } else { if (millis == 0L) { while(this.isAlive()) { this.wait(0L); } } else { while(this.isAlive()) { long delay = millis - now; if (delay <= 0L) { break; } this.wait(delay); now = System.currentTimeMillis() - base; } } } }interrupt：
线程中断在之前的版本有stop方法，但是被设置过时了。现在已经没有强制线程终止的方法了！
由于stop方法可以让一个线程A终止掉另一个线程B- 被终止的线程B会立即释放锁，这可能会让对象处于不一致的状态。
- 线程A也不知道线程B什么时候能够被终止掉，万一线程B还处理运行计算阶段，线程A调用stop方法将线程B终止，那就很无辜了~
总而言之，Stop方法太暴力了，不安全，所以被设置过时了。
我们一般使用的是interrupt来请求终止线程~ - 要注意的是：interrupt不会真正停止一个线程，它仅仅是给这个线程发了一个信号告诉它，它应该要结束了(明白这一点非常重要！)
- 也就是说：Java设计者实际上是想线程自己来终止，通过上面的信号，就可以判断处理什么业务了。
- 具体到底中断还是继续运行，应该由被通知的线程自己处理
