String

1.不可变性

  字符串的不可变体现在两个方面,

  1. 从源码可知String类被final修饰,即不可被继承
  2. 字符串底层是char数组,初始化时一旦申请了空间就无法动态扩容

注意:jdk9中底层变成了byte数组,因为String是堆空间中占用内存比较大的一块,研究发现其当中存放的大多为拉丁字符,不需要两个字节,为了节省空间就改为byte+charset

2.字符串存储

字符串常量池是一个固定大小的HashTable,StringTableSize的值可以通过虚拟机参数进行更改,tableSize的大小可以影响到intern的性能

3.字符串拼接

  1. 常量和常量的拼接
    该情况下代码在编译期就会优化,比如”hello “+”world”编译完我们可以通过idea反编译代码看到它变成了”hello world”;
  2. 常量和变量的拼接
    这种情况我们可以看下图

    图中代码后面的注释分别对应指令行数,由此我们可以看出来常量和变量之间的拼接在底层会new StringBuilder()然后调用其append和toString方法,append底层是对数组的动态扩容,toString底层会new String
    所以可以看出来常量和变量的拼接代价是比较大的,且拼接后的结果是放在堆中的,因为StringBuilder.toString方法不会在字符串常量池中创建常量对象,如果用”==”和”hello world”去比较,返回的肯定是false
  3. 变量和变量的拼接
    同2
  4. intern
    intern()方法会判断常量池中是否存在相应字符串,如果存在则返回地址,如果不存在,则在常量池中加载一份,并返回地址
    1
    2
    3
    4
    5
    6
    7
    8
    public static void main(String[] args){
    String s1 = "hello world";
    String s2 = "hello ";
    String s3 = "world";
    String s4 = s2 + s3;
    System.out.println(s1 == s4);//false
    System.out.println(s1 == s4.intern()) //true;
    }

List

  List主要从底层的数据结构分为两个大类数组和链表

1.数组

ArrayList

  数据实现的List我们最常用的就是ArrayList,底层数据结构是一个 Object[],初始化未指定大小时即使用默认 Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {},指定了大小就申请一个指定大小的Object[]默认初始化因子为10,数组扩容使用Arrays.copyOf,重新申请一个数组,扩容机制为首先扩容为原始容量的 1.5 倍,如果1.5倍太小的话,则将我们所需的容量大小赋值给 newCapacity,如果1.5倍太大或者我们需要的容量太大,那就直接拿 newCapacity = (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE 来扩容
在并发场景下ArrayList的操作是不安全的,至于哪里不安全可自行查看源码,有很多地方有”i++”操作;因此jdk也提供了一些线程安全的类,比如Collections.synchronizedList,CopyOnWriteArrayList

Collections.synchronizedList

  该对象底层使用的是互斥锁(synchronized),也就是将ArrayList中的方法包在synchronized代码块中包括get类方法,其他任何方法实现都不变,因此get方法性能会较其他两个差一些

CopyOnWriteArrayList

  该对象底层使用的是可重入锁(ReentrantLock),底层使用volatile修饰的Object[],更新类的方法像add,remove等使用重入锁+数组拷贝,所以更新类的操作性能会较其他两个差些

2.链表

LinkedList

  该对象底层数据结构是一个双向链表,头插和尾插方法可以方便的实现队列和stack等功能,也可以直接使用Deque和Queue等api

1
2
3
4
5
6
7
8
9
10
11
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;

Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}

3.区别

  1. ArrayList是实现了基于动态数组的数据结构(其实就是copy),LinkedList是基于链表结构。
  2. 随机访问的get和set方法,ArrayList要优于LinkedList,新增和删除操作add和remove,LinkedList比较占优势,因为ArrayList要移动数据。
  3. LinkedList集合不支持 高效的随机随机访问(RandomAccess),因为可能产生二次项的行为。
  4. ArrayList的空间浪费主要体现在在list列表的结尾预留一定的容量空间,而LinkedList的空间花费则体现在它的每一个元素都需要消耗相当的空间
  5. 在ArrayList集合中添加或者删除一个元素时,当前的列表移动元素后面所有的元素都会被移动。而LinkedList集合中添加或者删除一个元素的开销是固定的。

4.排序

  集合的排序要么使用Collections.sort()或者Arrays.sort(),但是Collections.sort()底层实现还是Array.sort(),所以在这里只需研究Arrays.sort()

legacyMergeSort

  如果启动时java.util.Arrays.useLegacyMergeSort参数为true那么将会调用legacyMergeSort,其底层是mergeSort,该方法的实现是当数组长度小于7使用插入排序否则使用归并排序,但是后续会将其移除;因为归并排序对已经反向排好序数组排序时复杂度为O(n^2);

1
2
3
4
5
6
7
8
9
10
11
12
13
public static void sort(Object[] a) {
//useLegacyMergeSort
if (LegacyMergeSort.userRequested)
legacyMergeSort(a);
else
ComparableTimSort.sort(a, 0, a.length, null, 0, 0);
}

/** To be removed in a future release. */
private static void legacyMergeSort(Object[] a) {
Object[] aux = a.clone();
mergeSort(aux, a, 0, a.length, 0);
}

TimeSort

  针对mergeSort出现的倒序数组会出现O(n^2)的复杂度,TimeSort作出了相应的调整;并且保证了数组对象的稳定性(这是个至关重要的因素);该方法的主要思想是分区合并在数组大小<32情况下,采用“mini-TimeSort”,实质是二分排序,当数组较大的时候就开始分区,将每个分区排好序之后然后进行合并

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
/**
* 1.数组初始化
* [3,4,5,9,8,7,6,1,2,0] 数组(可扩展为无限大)
* 2.校验长度(小于32退化为二分排序)忽略
* 3.分区
* [3,4,5][9,8,7][6,1,2,0]
* 3.1分区排序
* [3,4,5][7,8,9][0,1,2,6]
* 4.归并(先归并小分段,后归并大分段)
* [3,4,5,7,8,9]
* 5.归并剩下的
* [0,1,2,3,4,5,6,7,8,9]
*
*/
void sort(Object[] a, int lo, int hi, Object[] work, int workBase, int workLen) {
assert a != null && lo >= 0 && lo <= hi && hi <= a.length;
int nRemaining = hi - lo;
if (nRemaining < 2)
return; // Arrays of size 0 and 1 are always sorted
// 当元素个数小于32时使用 "mini-TimSort",这里使用的二分排序,并不会有合并动作
if (nRemaining < MIN_MERGE) {
//寻找从lo开始连续升序或者降序的的元素个数,如果是降序则会被反转成升序
int initRunLen = countRunAndMakeAscending(a, lo, hi);
//比较排序
binarySort(a, lo, hi, lo + initRunLen);
return;
}

/**
*当元素大于32个时
*/
ComparableTimSort ts = new ComparableTimSort(a, work, workBase, workLen);
//返回一个数组最小可接受的运行长度值在[16,32]之间
int minRun = minRunLength(nRemaining);
do {
// 找出下个分区的起始位置
int runLen = countRunAndMakeAscending(a, lo, hi);
// 如果可运行长度太小则退化为min-TimeSort
if (runLen < minRun) {
int force = nRemaining <= minRun ? nRemaining : minRun;
binarySort(a, lo, lo + force, lo + runLen);
runLen = force;
}
// 将其放到归并栈中
ts.pushRun(lo, runLen);
//归并小段
ts.mergeCollapse();
// Advance to find next run
lo += runLen;
nRemaining -= runLen;
} while (nRemaining != 0);
// 归并剩下的分段
assert lo == hi;
ts.mergeForceCollapse();
assert ts.stackSize == 1;
}

Map

  map是我们常用到的api,其底层是每一个的key-value,像我们经常使用的redis其实也是key-value键值对,在jdk中我们最常使用的就是HashMap,HashTable,ConcurrentHashMap等

HashMap

1.构造函数

  如果是无参构造函数只会初始化负载因子0.75,有参构造函数还会初始化所能容纳最大数据量的Node个数threshold,通过tableSizeFor()方法找到大于输入参数且最近的2的整数次幂的数,redis中的rehash扩容时
ht[1]的大小跟HashMap中tableSizeFor同理;至于负载因子,跟每个桶所能承载的键值对有关,越大承载键值对越多,空间利用率高,但同时增加了链表长度查询效率变低,所以负载因子一般情况下不要手动去设置

1
2
3
4
5
6
7
8
9
10
11
12
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}

2.hash

1
2
3
4
5
6
7
8
static final int hash(Object key) {
int h;
/**
* jdk8中对其做了些变动,拿到hashcode之后通过高16位和低16位进行异或,让所有位都参与到hash运算
* (n - 1) & hash === hash % length 然后对其进行求模运算,找到key所在的数组位
*/
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

3.put

put方法主要分为以下几个步骤

  1. 判断表是否为空,如果是则初始化表
  2. 寻址后的位置是否有坑,如果有则插入当前元素
  3. 判断坑中的元素是否跟自己相等,如果是则覆盖
  4. 判断坑中元素类型是否是红黑树,如果是则调用红黑树的插入方法
  5. 如果坑中元素时链表则循环插入,插入过程中,如果链表元素大于7个,要么就扩容要么就树化
  6. 如果所有元素个数大于阈值开始扩容
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
    /** tab:表,也就是我们所说的hash桶;
    * p : 有三种情况
    * 1. 表元素,当一个桶中无其他元素时p就是tab[i]占位
    * 2. 链表元素,当有hash冲突时且元素小于8时p就是链表
    * 3. 红黑树,链表元素大于等于7,且tab元素大于64时链表树化为红黑树
    */
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    //1.判断表是否为空,如果是则初始化表
    if ((tab = table) == null || (n = tab.length) == 0)
    n = (tab = resize()).length;
    //2. 寻址后的位置是否有坑,如果有则插入当前元素
    if ((p = tab[i = (n - 1) & hash]) == null)
    tab[i] = newNode(hash, key, value, null);
    else {
    Node<K,V> e; K k;
    //3. 判断坑中的元素是否跟自己相等,如果是则覆盖
    if (p.hash == hash &&
    ((k = p.key) == key || (key != null && key.equals(k))))
    e = p;
    //4. 判断坑中元素类型是否是红黑树,如果是则调用红黑树的插入方法
    else if (p instanceof TreeNode)
    e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
    else {
    //5.如果坑中元素时链表则循环插入,插入过程中,如果链表元素大于7个,要么就扩容要么就树化
    for (int binCount = 0; ; ++binCount) {
    if ((e = p.next) == null) {
    //5.1 这个方法中next指针指向了null,也就是将元素放到了链表的尾部,典型的尾插实现
    p.next = newNode(hash, key, value, null);
    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
    treeifyBin(tab, hash);
    break;
    }
    if (e.hash == hash &&
    ((k = e.key) == key || (key != null && key.equals(k))))
    break;
    p = e;
    }
    }
    if (e != null) { // existing mapping for key
    V oldValue = e.value;
    if (!onlyIfAbsent || oldValue == null)
    e.value = value;
    afterNodeAccess(e);
    return oldValue;
    }
    }
    ++modCount;
    //6.如果所有元素个数大于阈值开始扩容
    if (++size > threshold)
    resize();
    afterNodeInsertion(evict);
    return null;
    }

4.扩容

  1. 当原先table中的元素大于阈值时,HashMap就会开始执行扩容机制
  2. 计算新table的大小newCap和新的阈值newThr
  3. 创建一个大小为newCap的新数组,然后根据情况将老数组的数据放到新数组(具体步骤可以看下面代码)
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    //1.设置新的大小和阈值
    if (oldCap > 0) {
    //1.1 当就的大小超过2^30则不再扩容
    if (oldCap >= MAXIMUM_CAPACITY) {
    threshold = Integer.MAX_VALUE;
    return oldTab;
    }
    //1.2否则扩容为2倍(并校验其是否超过边界)
    else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
    oldCap >= DEFAULT_INITIAL_CAPACITY)
    newThr = oldThr << 1; // double threshold
    }
    //1.3 未指定大小初始化时,取默认值
    else if (oldThr > 0) // initial capacity was placed in threshold
    newCap = oldThr;
    else { // zero initial threshold signifies using defaults
    newCap = DEFAULT_INITIAL_CAPACITY;
    newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    //1.4 主要是初始化和1.2失败之后做个保底
    if (newThr == 0) {
    float ft = (float)newCap * loadFactor;
    newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
    (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr;
    @SuppressWarnings({"rawtypes","unchecked"})
    //2.创建一个大小为newCap的新数组 这里有可能是第一次初始化也有可能是用于扩容
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    if (oldTab != null) {
    //2.1 这里就到扩容了,遍历老数组的每个项
    for (int j = 0; j < oldCap; ++j) {
    Node<K,V> e;
    if ((e = oldTab[j]) != null) {
    oldTab[j] = null;
    //2.2 如果不是链表也不是树则直接寻址放元素,这里选址不会再次hash而是直接取模寻址放入新数组
    if (e.next == null)
    newTab[e.hash & (newCap - 1)] = e;
    //2.3 如果数组元素存储的是树,那么就要拆树
    else if (e instanceof TreeNode)
    //2.3.1 这里的split函数可以单独拎出来分析
    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
    else { // preserve order
    //2.4 如果是链表则将链表遍历分组然后放到新数组中
    Node<K,V> loHead = null, loTail = null;
    Node<K,V> hiHead = null, hiTail = null;
    Node<K,V> next;
    do {
    //分为lo 和 hi两个链表
    next = e.next;
    if ((e.hash & oldCap) == 0) {
    if (loTail == null)
    loHead = e;
    else
    loTail.next = e;
    loTail = e;
    }
    else {
    if (hiTail == null)
    hiHead = e;
    else
    hiTail.next = e;
    hiTail = e;
    }
    } while ((e = next) != null);
    //lo链表放在原先位置
    if (loTail != null) {
    loTail.next = null;
    newTab[j] = loHead;
    }
    //hi链表放在 从原先位置前移原先长度的地方
    if (hiTail != null) {
    hiTail.next = null;
    newTab[j + oldCap] = hiHead;
    }
    }
    }
    }
    }
    return newTab;
    }
    在上述扩容过程中的2.3项,拆分树调用了split方法
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
    TreeNode<K,V> b = this;
    // Relink into lo and hi lists, preserving order
    TreeNode<K,V> loHead = null, loTail = null;
    TreeNode<K,V> hiHead = null, hiTail = null;
    int lc = 0, hc = 0;
    //1.因为在插入过程,链表树化时还保留了next指针,所以可以跟链表一样往下找,并拆分为lo和hi两个链表
    for (TreeNode<K,V> e = b, next; e != null; e = next) {
    next = (TreeNode<K,V>)e.next;
    e.next = null;
    if ((e.hash & bit) == 0) {
    if ((e.prev = loTail) == null)
    loHead = e;
    else
    loTail.next = e;
    loTail = e;
    ++lc;
    }
    else {
    if ((e.prev = hiTail) == null)
    hiHead = e;
    else
    hiTail.next = e;
    hiTail = e;
    ++hc;
    }
    }

    //2.将lo链表树放到 原来位置
    if (loHead != null) {
    //如果长度小于等于6则拆树,转换为链表
    if (lc <= UNTREEIFY_THRESHOLD)
    //这里拆树时底层调用replacementNode,其中next参数为空,即尾插
    tab[index] = loHead.untreeify(map);
    else {
    //否则放到原先的位置
    tab[index] = loHead;
    //hiHead == null 时,表明扩容后,所有节点仍在原位置,树结构不变,无需重新树化
    if (hiHead != null) // (else is already treeified)
    //重建树
    loHead.treeify(tab);
    }
    }
    //3.将hi链表树放到 原来位置往前移老table数组大小个长度
    if (hiHead != null) {
    if (hc <= UNTREEIFY_THRESHOLD)
    tab[index + bit] = hiHead.untreeify(map);
    else {
    tab[index + bit] = hiHead;
    if (loHead != null)
    hiHead.treeify(tab);
    }
    }
    }

  通过上述代码解析,已将HashMap最关键的插入和扩容机制详尽描述,上述代码都是jdk8版本中的,较之jdk7变化其实蛮大的主要有以下几种区别

  1. 底层数组结构发生变化,jdk7底层是数组+链表,jdk8中是数组+链表+红黑树;有效的提升了查询效率,避免了在数据量大的情况下一直遍历链表的操作
  2. 插入元素使用尾插法,解决了jdk7中扩容时出现的死循环(自行查看jdk7源码分析)
  3. 细节优化,比如hash算法在jdk8中使用高低位异或增加了散列程度

在美团技术博客找到一张图,对插入过程有很好的的描述