List接口 – 允许保存重复数据

<--more-->

  • java类集的引出,使用动态数组解决定长问题

ArrayList,Vector,LinkedList

1552897701468

  • 每种集合的通用逻辑,都被抽象到相应的抽象类中,AbstractList集中了各种List操作的通用部分。这些集合不是完全孤立的,LinkList本身既是List,也是Deque

ArrayList

ArrayList类通过extends关键字继承AbstractList抽象类,通过关键字implement实现List集合接口,RandomAccess标记接口,Cloneable克隆接口,Serializable序列化接口

1
2
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable

1552898663072

接口RandomAccessa.java(实现随机访问)
  • 此接口的主要目的是允许一般的算法更改其行为,从而在将其应用到随机或连续访问列表时能提供良好的性能。
  • 接口RandomAccess 是一个标记接口,实现该接口的集合List 支持快速随机访问。List 集合尽量要实RandomAccess 接口,如果集合类是RandomAccess 的实现,则尽量用for(int i = 0; i < size; i++) 来遍历效率高,而不要用Iterator迭代器来遍历(如果List是Sequence List,则最好用迭代器来进行迭代)
接口Cloneable
  • 实现接口的目的是重写java.lang.Object的clone()的方法,实现浅拷贝。深拷贝和浅拷贝针对像 Object, Array 这样的复杂对象的。浅拷贝只复制一层对象的属性,而深拷贝则递归复制了所有层级。

    关于深浅拷贝

    • 浅拷贝
    • 深拷贝
接口Serializable
  • 该接口无继承实现关系,实现给接口的类支持序列化。所以ArrayList支持序列化

    关于序列化

    • 序列化:将一个内存中保存的对象变成二进制数据流的形式进行传输,或者是将其保存在文本中。
    • 反序列化:可以将其他地方所存储的数据通过二进制数据流的方式读取出来

源码分析:

ArrayList的构造方法

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
//序列版本号
private static final long serialVersionUID = 8683452581122892189L;

//空数组
private static final Object[] EMPTY_ELEMENTDATA = {};

//默认构造函数的空数组
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

//数组缓冲区,存储元素的底层实现,真正存放元素的数组
//使用transient关键字修饰的elementData是不支持序列化的
transient Object[] elementData;// non-private to simplify nested class access


//指定初始化容量的构造方法
public ArrayList(int initialCapacity) {
//若初始容量大于0,则新建一个大小为指定容量的Object数组
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
//若容量为0,则直接将空数组赋给elementData
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
//若容量小于0,则抛出异常
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}

//默认构造方法
//将默认的构造函数的空数组赋给elementData
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

//利用别的集合类构建ArrayList的构造方法
public ArrayList(Collection<? extends E> c) {
//用Collection.toArray()方法取得一个对象数组,并赋给elementData
//浅拷贝
elementData = c.toArray();
//size为集合元素数量,通过别的集合来构造ArrayList时,就需要给size赋值
//如果size为0,直接空数组赋给elementData即可
//如果size不为0,则要将Collection对象中的内容拷贝到elementData中
if ((size = elementData.length) != 0) {
// c.toArray might (incorrectly) not return Object[] (see 6260652)
//深拷贝
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// replace with empty array.
this.elementData = EMPTY_ELEMENTDATA;
}
}
  • 无参构造方法中直接初始化Object[] elementData={};
  • 带参构造方法是new Object()或者通过Arrays的方法转化为数组对象
问题一:ArrayList是数组还是集合
  • ArrayList实现List接口,重写其中的add(),get(),remove()等方法,而方法的内部代码是基于数组来处理数据的。
  • ArrayList是实现List接口的集合,是基于数组的集合,数据的存储容器是数组,集合方法是通过数组实现的(例如:泛型参数构造方法是将传入的集合c先转化为数组在进行处理的)。

通关add方法查看初始容量

  • ArrayList中定义了一个默认存储容器大小DEFAULT_CAPACITY=10,我们发现在构造方法创建ArrayList是并没有使用到该常量。在add添加元素的时候,先将size+1传入到ensureCapacityInternal()判断当前数组elementData是否需要扩容,足够size自增1,直接添加元素即可。
    • 扩容:当数组还是默认的空数组时,这里的size+1=0 < DEFAULT_CAPACITY 会将容器大小扩容为10,此时的elementData扩容为Object[10]

问题二:ArrayList的初始容量是多少?

  • 当调用构造方法创建ArrayList时,默认无参构造对象的容器初始大小为0。而当调用add方法时才会将数组扩容为10.

ArrayList的扩容问题:

当elementData.length < size+1时才会进行扩容,调用grow方法。

  • 先取到当前容器大小oldCapacity,进行扩容,判断扩容容量是否合法,是否溢出,然后处理为合理的大小
    • 使用newCapacity = oldCapacity + (oldCapacity >> 1)计算出来预计扩容的大小,如果该大小仍然小于数组所扩容后的大小,newCapacity = minCapacity;重新改写新扩容后数组容量,如果新数组大小大于数组的最大容量限度,调用huneCapacity()方法,直接将容量大小定义为Integer的最大值,最后调用Arrays方法进行拷贝
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
88
89
--------------------------------------------------------------------
//默认初始化数组容量
private static final int DEFAULT_CAPACITY = 10;
// 集合最大容量
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
//当前数组的大小
private int size;
public int size() {
return size;
}
public boolean isEmpty() {
return size == 0;
}

//添加元素,添加成功返回true
//每次添加元素之前都会检查一下是否需要扩容
public boolean add(E e) {
//判断添加后的容量,选择是否需要扩容
ensureCapacityInternal(size + 1); // Increments modCount!!
//在数组末尾添加元素,更新size
elementData[size++] = e;
return true;
}

private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

//当第一次添加元素,需要获取数组初始容量,返回minCapacity和默认初始容量中的较大值
//当不是第一次添加元素,则直接返回minCapacity
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}

//moCount(修改次数)自增1,判断是否需要扩充数组长度
private void ensureExplicitCapacity(int minCapacity) {
modCount++;

// overflow-conscious code
if (minCapacity - elementData.length > 0)
//增加数组长度
grow(minCapacity);
}

//数组扩容,默认需要扩容1.5倍
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
//新数组大小为原数组的1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
//如果新数组大小仍然小于minCapacity,则更新newCapacity的值
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
//如果新数组大小大于数组的最大容量限度,调用huneCapacity()方法
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);
}

//新数组的大小
private static int hugeCapacity(int minCapacity) {
//若minCapacity小于0,抛异常
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
//超过最大值不合法,直接将容量大小定义为Integer的最大值
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}

//指定位置添加元素
public void add(int index, E element) {
//越界判断,如果越界抛异常
rangeCheckForAdd(index);

//判断是否需要扩容,步骤和上面一样
ensureCapacityInternal(size + 1); // Increments modCount!!
//将数组从index开始的数据往后移一位
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
//添加元素
elementData[index] = element;
size++;
}
ArrayList的序列化问题补充
  • 集合的存储容器elementData 使用transient 关键字修饰不支持序列化,但是我们知道ArrayList 是支持序列化的,那我们是怎么序列化集合中的数据呢,这里不直接序列化elementData,而是遍历每个数据分别进行IO 流处理来实现存储容器中对象的序列化的。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// ArrayList 列表结构被修改的次数。        
protected transient int modCount = 0;

private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException{
// Write out element count, and any hidden stuff
//ArrayList 列表结构被修改的次数
int expectedModCount = modCount;
s.defaultWriteObject();
// Write out size as capacity for behavioural compatibility with clone()
s.writeInt(size);
//对每一对象进行IO流的写处理
// Write out all elements in the proper order.
for (int i=0; i<size; i++) {
s.writeObject(elementData[i]);
}

if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
}
  • modCount是表示ArrayList对象被修改的次数,Iterator中有一个成员变量expectedModCount,在创建时会将modCount赋值给他,用来检验在迭代过程中List对象是否被修改,如果被修改就会抛出ConcurrentModificationException异常。在每次调用Iterator对象的next方法时都会调用checkForComodification()方法进行检验,将modCount与expectedModCount进行对比。

互斥锁:解决原子性问题


如何解决原子性问题?

  • 原子性问题的源头是线程切换,在操作系统做线程切换是依赖CPU中断的,所以禁止CPU发生中断就能够禁止线程切换。

:thinking:为什么插入排序比冒泡排序更受欢迎?

如何分析一好“排序算法”?

排序算法的执行效率

  • 最好情况,最坏情况,平均情况时间复杂度
  • 时间复杂度的系数,常数,低阶
  • 比较次数和交换(或移动)次数

排序算法的内存消耗

  • 这里引入一个原地排序(Sorted in place)。原地排序是指空间复杂度为O(1)的排序算法

排序算法的稳定性

  • 稳定性:指定的是数组中值相同的元素,在排序之后的相对位置没有发生变化

    例如:

    排序前

    • 2,4,1,8,9,4,5,3

    排序后

    • 1,2,3,44,5,8,9

    这里边有两4,在经过排序之后,如果两个4的前后顺序没有发生变化,就将该排序算法称为稳定的排序算法,反之称为不稳定排序算法

那么稳定排序有什么意义呢?

例如:电商交易系统中的“订单”排序。订单两个属性,一是下单的时间,二是订单的金额。如果在一批订单中,按照订单的金额从小到大对订单排序,对于金额相同的订单,而是按照下单时间从早到晚有序。那么该如何处理这个需求呢?

  • 如果采用不稳定排序算法去进行排序,就会相当的麻烦,首先按照金额排序,再在金额相同的订单中按照时间排序,这样需要将相同金额的订单,按照各自小区间排序,实现起来就很复杂。

  • 如果采用稳定的排序算法,先按照时间对订单排序(这里比一定要是用稳定排序算法),再使用稳定排序算法,按照订单的金额重新排序。这样,得到的数据就是按照金额从小到大排序,而在金额相同的订单中是按照下单时间从早到晚排序。

  • 稳定排序算法保证了金额相同的两个对象,在排序之后的前后顺序不变。

时间复杂度为O(n^2)的排序算法

冒泡排序(Bubble Sort)

  • 冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较,看是否满足大小关系要求。如果不满足就让它俩互换。一次冒泡会让至少一个元素移动到它应该在的位置,重复 n 次,就完成了 n 个数据的排序工作。

如下图所示:一次冒泡的执行流程

  • 冒泡排序的优化:当某个冒泡操作已经没有数据交换时,表明数组中的所有元素已经有序,就不再需要进行后续的冒泡操作,例如:

代码实现如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public  void bubbleSort(int[] a, int n) {
if (n <= 1) return;
for (int i = 0; i < n; i++) {
boolean flag = false;
for (int j = 0; j < n - i - 1; j++) {
if (a[j] > a[j + 1]) {
int tmp = a[j];
a[j] = a[j + 1];
a[j + 1] = tmp;
//冒泡优化,当再一次冒泡中没有进行数据交换时,证明已经是有序数组
flag = true;
}
}
if (!flag) break;
}
问题一:冒泡排序是原地排序算法吗?
  • 冒泡排序只需要涉及相邻数据的交换,只需要常量级的临时空间,空间复杂度为O(1),是原地排序算法。
问题二:冒泡排序是稳定的排序算法吗?
  • 冒泡排序是交换两个元素的顺序,为了保证稳定性,当相邻元素大小相等时,不做交换,所以是稳定的排序算法。
问题三:冒泡排序的时间复杂度是多少?
  • 最坏情况:需要进行n次冒泡操作,时间复杂度为O(n^2)
  • 最好情况:数组已经有序,只需要进行一次冒泡操作,时间复杂度为O(n)
  • 平均情况:时间复杂度为O(n^2)

插入排序(Insertion Sort)

  • 插入排序的实现过程:将数组划分为,已排序区间未排序空间。初始的已排序空间只有一个元素,就是数组第一个元素。插入算法的核心思想是取未排序区间中的元素,在已排序区间中找到合适的插入位置将其插入,并保证已排序区间数据一直有序。重复这个过程,直到未排序区间中元素为空,算法结束。

如下图所示:要排序的数据是 4,5,6,1,3,2,其中左侧为已排序区间,右侧是未排序区间。

  • 插入排序包含两种操作:元素的比较元素的移动

代码实现如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public void insertSort(int a[], int n) {
if (n <= 1) return;
//下标从1开始
for (int i = 1; i < n; i++) {
int value = a[i];
int j = i - 1;
for (; j >= 0; j--) {
if (a[j] > value)
a[j + 1] = a[j];
else
break;
}
a[j + 1] = value;
}
}
问题一:插入排序是原地排序算法吗?
  • 插入排序不需要额外的存储空间,空间复杂度O(1),属于原地排序算法
问题二:插入排序是稳定的排序算法吗?
  • 插入排序中,对于相同值的元素,可以选择将后面出现的元素,插入到前面出现元素的后边,这样就可以保证原有前后顺序不变,属于稳定的排序算法。
问题三:插入排序的时间复杂度是多少?
  • 最坏情况:数组是倒序的,每次都需要在数组的第一个位置插入新的数据,需要大量的搬移数据,时间复杂度为O(n^2)
  • 最好情况:数组是有序的,只需要从头到尾遍历已经有序的数据即可。
  • 平均情况:时间复杂度为O(n^2)

选择排序(Selection Sort)

  • 选择排序算法的实现思路有点类似插入排序,也分已排序区间和未排序区间。但是选择排序每次会从未排序区间中找到最小的元素,将其放到已排序区间的末尾。

代码实现如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public void selectionSort(int[] a, int n) {
if (n <= 1) return;
for (int i = 0; i < n - 1; i++) {
int min = i;
for (int j = i + 1; j < n; j++) {
//更新已排序中最小数的下标
if (a[j] < a[min])
min = j;
//如果下标发生改变,数据进行交换
if (min != i) {
int value = a[min];
a[min] = a[i];
a[i] = value;
}
}
}
}
问题一:插入排序是原地排序算法吗?
  • 空间复杂度为O(1),属于原地排序算法
问题二:插入排序是稳定的排序算法吗?
  • 选择排序每次都需要在剩余未排序的元素中找出最小值,和前面的元素进行交换,这样就破坏里稳定性,属于不稳定的排序算法。
问题三:插入排序的时间复杂度是多少?
  • 最坏,最好,平均时间复杂度均为O(n^2)

时间复杂度为O(n^2)的排序算法

:thinking:如何在O(n)的时间复杂度查找一个无序数组中的第K大元素?

归并排序(Merge Sort)

  • 归并排序的核心思想:如果要排序一个数组,我们先把数组从中间分成前后两部分,然后对前后两部分分别排序,再将排好序的两部分合并在一起,这样整个数组就都有序了。

  • 分治思想:分治,顾名思义,就是分而治之,将一个大问题分解成小的子问题来解决。小的子问题解决了,大问题也就解决了。

代码实现如下:

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
public void margeSort(int[] a, int n) {
marge_Sort(a, 0, n - 1);
}

public void marge_Sort(int[] a, int l, int r) {
if (l >= r) {
return;
}
int m = l + ((r - l) >> 1);
marge_Sort(a, l, m);
marge_Sort(a, m + 1, r);
marge(a, l, m, r);
}

public void marge(int[] a, int l, int m, int r) {
//申请一个与原数组大小相同的临时数组
int[] tmp = new int[a.length];
int i = l;
int j = m + 1;
int k = 0;
while (i <= m && j <= r) {
if (a[i] <= a[j]) {
tmp[k++] = a[i++];
} else {
tmp[k++] = a[j++];
}
}
//判断哪个数组有剩余的数据
int start = i;
int end = m;
if (j <= r) {
start = j;
end = r;
}
//将剩余数据拷贝到临时数组
while (start <= end) {
tmp[k++] = a[start++];
}
//将临时数组中的数据拷贝会原数组,注意边界条件
for (i = 0; i <= r - l; i++) {
a[l + i] = tmp[i];
}
}
问题一:归并排序是稳定排序算法吗?
  • 在合并数组的过程中,在两个有序数组合并一个有序数组,相同的元素可以规定哪个在前面将该元素放在新数组前面,属于稳定的排序算法。
问题二:归并排序的时间复杂度是多少?
  • 最好,最坏,平均时间复杂度均为O(nlogn)

快速排序(Quick Sort)

  • 快排思想:任取待排序元素序列中的某元素作为基准值,按照该排序码将待排序集合分割成两子序列,左子序列中所有元素均小于基准值,右子序列中所有元素均大于基准值,然后最左右子序列重复该过程,直到所有元素都排列在相应位置上为止。

谈谈对Java平台的理解?“Java是解释执行”,这句话正确吗?

  • “一次编译、到处运行”说的是Java语言跨平台的特性,Java的跨平台特性与Java虚拟机的存在密不可分,可在不同的环境中运行。比如说Windows平台和Linux平台都有相应的JDK,安装好JDK后也就有了Java语言的运行环境。其实Java语言本身与其他的编程语言没有特别大的差异,并不是说Java语言可以跨平台,而是在不同的平台都有可以让Java语言运行的环境而已,所以才有了Java一次编译,到处运行这样的效果。

    严格的讲,跨平台的语言不止Java一种,但Java是较为成熟的一种。“一次编译,到处运行”这种效果跟编译器有关。编程语言的处理需要编译器和解释器。Java虚拟机和DOS类似,相当于一个供程序运行的平台。

    程序从源代码到运行的三个阶段:编码——编译——运行——调试。Java在编译阶段则体现了跨平台的特点。编译过程大概是这样的:首先是将Java源代码转化成.CLASS文件字节码,这是第一次编译。.class文件就是可以到处运行的文件。然后Java字节码会被转化为目标机器代码,这是是由JVM来执行的,即Java的第二次编译。

    “到处运行”的关键和前提就是JVM。因为在第二次编译中JVM起着关键作用。在可以运行Java虚拟机的地方都内含着一个JVM操作系统。从而使JAVA提供了各种不同平台上的虚拟机制,因此实现了“到处运行”的效果。需要强调的一点是,java并不是编译机制,而是解释机制。Java字节码的设计充分考虑了JIT这一即时编译方式,可以将字节码直接转化成高性能的本地机器码,这同样是虚拟机的一个构成部分。

JavaSE知识考点

  1. JAVA中的几种基本数据类型是什么,各自占用多少字节?

    • 4种整形 ( byte 1 short 2 int 4 long 8 )
    • 2种浮点型(float 4 double 8)
    • char型(char 2)
    • boolean型(boolean 1)
  2. String 类能被继承吗,为什么?

    • String类是被fianl修饰的,而被final修饰的属性不可变,类不可被继承,方法不可以被复写
  3. String,StringBuffer,StringBuilder 的区别

    • String是字符串常量

    • StringBuffer是字符串变量,同步处理线程安全的,效率低

    • StringBuilder是字符串变量,异步处理线程不安全的,效率高
  4. .ArrayList (扩容策略1.5倍)和 LinkedList 有什么区别

    • 共同点:都是实现了List接口的容器类,都支持增删查改的操作,都是采用异步处理放式
    • 底层实现:基于动态数组的数据结构与基于链表结构
    • 随机访问的get与set方法,ArrayList效率高
    • 对于删除与插入,LinkedList效率高
  5. ArrayList与Vector的区别

    • 出现版本:1.2 1.0

    • 初始化策略:

      • ArrayList:采用懒加载方式,在构造方法时并不初始化对象数组,只有在添加元素时才数组对象初始化为10
      • Vector:在无参构造时就将对象数组初始化为10
    • 扩容策略

      • ArrayList:新数组扩容为原数组的1.5倍
      • Vector:新数组寇蓉为原数组的2倍
    • 遍历方式

      • ArrayList则则不支持

      • Vector支持较老的Enumeration

  1. 讲讲类的实例化顺序,比如父类静态数据,构造函数,字段,子类静态数据,构造函数,字段,当 new 的时候,他们的执行顺序

    • 父类静态变量>父类静态代码块>子类静态变量>子类静态代码块>父类构造块>父类构造方法>父类字段>子类构造块>子类构造方法>子类字段
    • 父类静态数据 ,子类静态数据,父类构造函数 ,父类字段,子类构造函数,子类字段
  2. 用过哪些 Map 类,都有什么区别,HashMap 是线程安全的吗,并发下使用Map 是什么,他们内部原理分别是什么,比如存储方式,hashcode,扩容,默认容量等。

  • HashMap
    • 线程不安全,并且采用懒加载策略
    • 存储方式:链表+数组(JDK8增添了红黑树)
      • 树化逻辑:当桶中链表个数>=8,并且所有元素个数加起来超过64,结构转化为红黑树(解决问题:链表太长导致查找太慢问题,O(n)->O(logn),减少哈希碰撞)
    • 默认容量(桶的数量):16
    • 扩容策略:当超过容量最大值,不在扩充,没超过最大值扩充为原来的2倍,扩容后对元素进行rehash,要么保留在原桶中,要么在新桶中,HashMap
  • ConcurrentHashMap

    • 线程安全:

      • JDK7中采用ReentrantLock保证Segment的线程安全

      • JDK8之后使用内建锁+CAS锁每个桶的头结点,使得锁进一步细粒度化

    • 存储方式:

      • JDK7中将16个桶设计改为16个Segment,每个Segment都有独立的一把锁,拆分后每个Segment相当于一个HashMap,
      • JDK8使用与HashMap相同的存储结构:链表+数组+红黑树,并且引入懒加载模式(锁的力度更细:原来取得锁Segment一片区域到锁桶的头结点,内存占用更小)
  1. JAVA8 的 ConcurrentHashMap 为什么放弃了分段锁,有什么问题吗?

    • 锁力度更细
    • 内存占有更小

    深入理解HsahMap与ConcurrentHashMap扩容策略

  2. 有没有有顺序的 Map 实现类,如果有,他们是怎么保证有序

    LinkedHashMap(记录插入的顺序):保留插入的顺序,输出顺序与输入顺序一致

    TreeHashMap:默认升序的,按照key的内容排序,处理排序是按照Comparable接口完成,依靠comparaTo()方法完成,当然也可以自己复写Comparable接口中的comparaTo()方法,去自己规定排序方式

  3. 抽象类和接口的区别,类可以继承多个类么,接口可以继承多个接口么,类可以实现多个接口么

  4. 反射的原理,反射创建类实例的三种方式是什么?

    三种实例化对象方式

    1. 任何类的实例化对象可以通过Object类中的getClass()方法取得Class类对象
    2. “类.class”:直接根据某个具体的类来取得Class类的实例化对象。
    3. 使用Class类提供的方法:public static Class<?> forName(String className) throws ClassNotFoundException
  5. 反射中,Class.forName 和 ClassLoader 区别

  1. final 的用途

    • final变量是只读的,final变量一般与static关键字使用,作为常量使用
    • final方法不可重写
    • final类不能被继承

    final好处:

    • final关键字可以提高性能。JVM和Java应用都会缓存final变量
    • final变量可以安全的在多线程环境下进行共享,而不需要额外的同步开销
    • 使用final关键字,JVM会对方法,变量及类进行优化,更好地实现封装。

    final详解

  2. juc包下提供的四大工具类,

JVM

  1. 什么情况下会发生栈内存溢出

    • 如果线程请求的栈深度大于虚拟机所允许的最大深度,会抛出StackOverFlow异常
    • 如果虚拟机在拓展栈时无法申请到足够的内存空间,则会抛出OOM异常
  2. JVM 的内存结构,Eden 和 Survivor 比例

    • Eden和Survivor(一个称为From,另外称为To区域)的比例是按照8 : 1分配的
  3. JVM 内存为什么要分成新生代,老年代,永久代。新生代中为什么要分为 Eden和 Survivor。

    都是属于堆

    “标记-清除”算法是最基础的收集算法,分为“标记”和”清除”两个阶段:在标记后在完成统一回收所有被标记的对象。(效率问题:标记与清除效率不高 空间问题会:产生大量不连续的内存碎片)

    • MinorGC 新生代(复制算法):当对象进入初次进入Survivor区时就会将对象的年龄+1,当对象每熬过一次GC年龄就会+1,当到达默认值15时,就会将其移到老年代中。

      • 为啥有两个Survivor区:通过两个Survivor区可以达到新生代无碎片的目的
    • MajorGC 老年代(标记-整理算法):存活时间比较久,或者需要占用大量连续内存空间的对象

      • 针对老年代的特点,提出了一种称之为”标记-整理算法”。标记过程仍与”标记-清除”过程一致,但后续步骤不是直接对可回收对象进行清理,而是让所有存活对象都向一端移动,然后直接清理掉端边界以外的内存。
    • FullGC 持久代

    • 当前JVM垃圾回收机制采用“分代收集算法”,就是将Java堆分为新生代和老年代。
  4. 关于深浅拷贝

    • 浅拷贝:拷贝出来的对象仍然保留原有对象的所有引用

      • 问题:牵一发而动全身,只要任意一个原对象(或拷贝对象)中的引用发生改变,所有对象均会收到影响
    • 深拷贝:拷贝出来的对象产生了所有引用新的对象

      • 特点:修改任意一个对象,不会对其他对象产生影响

        深浅拷贝

  5. 强引用,软引用,弱引用,虚引用

  6. JVM 中一次完整的 GC 流程是怎样的,对象如何晋升到老年代,说说你知道的几种主要的 JVM参数

    过程:

    1. 向Eden申请空间
      • 空间足够
      • 空间不足够
        • 触发第一次Minor GC将所有存活对象放入Survivor from区,将对象年龄置位1,然后一次清理Eden区
        • 再次发生Minor GC,扫描Eden和From区,将存活对象拷贝到To区,然后一次清理掉Eden区和From区
        • 再次发生Minor GC时,会对Eden区域To区进行回收,存活对象移动到From区。每次移动都会将存活对象年龄+1
        • 当存活对象年龄到达默认15时,存入老年代
    2. 当对象的大小过大时,直接进入老年代
    3. 当老年代空间不足时,会进行标记-整理算法 Full GC(老年代 GC或者Major GC)
    4. 当完全垃圾收集后,若Survivor和old区仍然无法存放Eden复制过来的部分对象时会导致JVM无法在Eden区为新对象创建内存区域,则出现”Out of memory错误”;

    GC

    JVM主要参数:

    • -Xms:最小堆大小

    • -Xmx:最大堆大小

    • -Xss:设置每个线程的堆栈大小

    • -XX:NewSize=n:设置年轻代最小空间大小 MaxNewSize最大空间大小

    • -XX:PermSize=n:设置持久代最小空间大小 MaxPermSize最大空间大小

    • -XX:PretenureSizeThreshold:大于设定值的对象直接在老年代分配

    • -XX:MaxTenurngThreshold:设置垃圾最大年龄

    • -XX:NewRatio=n:设置年轻代和年老代的比值。如:为3,表示年轻代与年老代比值为1:3,年轻代占整个年轻代年老代和的1/4

    • -XX:SurvivorRatio=n:年轻代中Eden区与两个Survivor区的比值。注意Survivor区有两个。如:3,表示Eden:Survivor=3:2,一个Survivor区占整个年轻代的1/5

  1. 你知道哪几种垃圾收集器,各自的优缺

    • 串行收集器:暂停所有应用的线程来工作;单线程
    • 并行收集器:默认的垃圾收集器。暂停所有应用;多线程
    • G1收集器:用于大堆区域。堆内存分隔,并发回收
    • CMS收集器:多线程扫描,标记需要回收的实例,清除
  2. 垃圾回收算法的实现原理

    • 标记-清除算法
    • 复制算法
    • 标记-整理算法

    如何判断对象已死?

    • 引用计数法
    • 可达性分析算法
  3. JVM 内存模型的相关知识了解多少,比如重排序,内存屏障,happens-before,主内存,工作内存等。

    • 工作内存与主内存

      :black_flag:

    • Happens-before原则(指令重排序)

      :black_flag:

    • JMM内存三大特性(AVO)

      • 原子性:基本数据类型的访问读写是具备原子性的,如若需要更大范围

        的原子性,需要内建锁或lock体系的支持(i++,i– 等操作)

      • 可见性:当一个线程修改了共享线程的值,其他线程立即得知值的修改。volatile,final,synchronized可以实现可见性。

      • 有序性:若在本线程内观察,所有操作都是有序的;若在线程之外观察另外一个线程,所有操作都是无序的。

    • Volatile关键字(可见性,禁止指令重排(懒汉式单例的double-check))

      • 保证此变量对所有线程的可见性(一个线程将修改变量值,其余线程可得知值的修改)

        1. 线程对变量进行修改之后,要立刻回写到主内存。
        2. 线程对变量读取的时候,要从主内存中读,而不是缓存。
      • 禁止指令重排:为了尽可能减少内存操作速度远慢于CPU运行速度所带来的CPU空置的影响,虚拟机会按照自己的一些规则将程序编写顺序打乱。如果变量没有volatile修饰,程序执行的顺序可能会进行重排序。

      • 不能保证原子性(举例:i++操作)

        假如说线程A在做了i+1,但未赋值的时候,线程B就开始读取i,那么当

        线程A赋值i=1,并回写到主内存,而此时线程B已经不再需要i的值了,

        而是直接交给处理器去做+1的操作,于是当线程B执行完并回写到主

        内存,i的值仍然是1,而不是预期的2。也就是说,volatile缩短了普通

        变量在不同线程之间执行的时间差,但仍然存有漏洞,依然不能保证原

        子性。

        • 处理方法:加锁,使用原子类
关于double-check

:black_flag:

1
2
3
4
5
6
7
8
9
10
11
12
13
class Singleton{
private volatile static Singleton instance = null;
private Singleton(){}
public static Singleton getInstance(){
if(instance==null){
synchronized(Singleton.class){
if(instance==null)
instance=new Singleton();
}
}
retuen instance;
}
}
  1. 怎么打出线程堆栈信息

    • JDK:jps
    • Linux:ps -ef | grep | java
  2. 请解释如下 jvm 参数的含义

    • -Xms:最小堆大小
    • -Xmx:最大堆大小
    • -Xss:设置每个线程的堆栈大小
    • -XX:PermSize=n:设置持久代最小空间大小 MaxPermSize最大空间大小
    • -XX:MaxTenurngThreshold:设置垃圾最大年龄

数据库

  1. 数据库隔离级别有哪些,各自的含义是什么,MYSQL 默认的隔离级别是什么

    1. 未提交读
    2. 已提交读(不可重复读)
    3. 可重复读
    4. 可串行读

    Mysql默认是可重复读

  2. 什么是幻读与不可重读

    • 脏读:当一个事务正在访问数据,并且对数据进行了修改,而这种修改还没有提交到数据库中,这时,另外一个事务也访问这个数据,然后使用了这个数据。
    • 幻读:
    • 不可重复读:指在一个事务内,多次读同一数据。在这个事务还没有结束时,另外一个事务也访问该同一数据。那么,在第一个事务中的两次读数据之间,由于第二个事务的修改,那么第一个事务两次读到的的数据可能是不一样的。这样就发生了在一个事务内两次读到的数据是不一样的,因此称为是不可重复读。(即不能读到相同的数据内容)
  3. MSQL 的索引原理,索引的类型有哪些,如何创建合理的索引,索引如何优化

  4. 聚集索引和非聚集索引的区别

    聚簇索引:

    • 表排列顺序:表记录的排列顺序与索引的排列顺序一致。

    非聚簇索引:

    • 表排列顺序:物理顺序和索引的顺序不一致

    • 索引文件和数据文件分开,索引文件的叶子页只保存了主键值,要定位记录还要去查找相应的数据块

    聚集索引与非聚集索引的区别

  5. 某个表有近千万数据,CRUD 比较慢,如何优化。

  6. 数据库中的ACID是什么?

    • A:atomic,原子性

    • C:consistent,一致性

      事务开始及结束后,处于一致状态,是通过原子性来保证的

    • I:Isolation,隔离性

      各个事物之间互不干扰

    • D:Durability,持久性

      一个事物一旦提交,对数据库所做的改变都要记录到永久存储中去(例如:磁盘)

  1. 如何写 sql 能够有效的使用到复合索引。
  1. mysql 中 in 和 exists 区别

算法与数据结构

  1. 常用的排序算法,快排,归并、冒泡。 快排的最优时间复杂度,最差复杂度。
    冒泡排序的优化方案。

    | 排序方式 | 最优情况 | 平均情况 | 最坏情况 | 空间复杂度 | 稳定性 |
    | ——– | ——– | ——– | ————— | ———- | —— |
    | 插入排序 | O(n) | O(n^2) | O(n^2) | O(1) | 稳定 |
    | 希尔排序 | O(n) | O(n^1.3) | O(n^2) | O(1) | 不稳定 |
    | 选择排序 | O(n^2) | O(m^2) | O(n^2) | O(1) | 不稳定 |
    | 堆排序 | O() | O() | O() | O(1) | 不稳定 |
    | 冒泡排序 | O(n) | O(n^2) | O(n^2) | O(1) | 稳定 |
    | 快速排序 | O(nlogn) | O(nlogn) | 极端情况下O(n2) | O(logn) | 不稳定 |
    | 归并排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(n) | 稳定 |

  1. 10 亿个数字里里面找最小的 10个

    topk问题:建立一个数量为10的大堆,然后遍历数字,当有数字小于对顶元素时,替换堆顶元素,然后调整大堆

    优化:可以把所有10亿个数据分组存放,比如分别放在1000个文件中。这样处理就可以分别在每个文件的10^6个数据中找出最大的10个数,合并到一起在再找出最终的结果

  2. 有 1 亿个数字,其中有 2 个是重复的,快速找到它,时间和空间要最优

  3. 2 亿个随机生成的无序整数,找出中间大小的值

多线程

  1. 多线程的几种实现方式,什么是线程安全

    • 继承Thread类实现多线程
    • Runnable接口实现多线程
    • Callable接口实现多线程

    线程安全(线程同步)就是多个线程在访问一个内存资源时,只有一个线程可以访问成功,

  2. volatile(保证不了原子操作) 的原理,作用,能代替锁吗

    • 保持线程之间的内存可见性
    • 禁止指令重排

    由于Java中的运算不是原子性操作,所以volatile在多线程模式下不能保证安全性,并不能替代锁

  3. 线程的生命周期状态图

    创建 就绪 运行 阻塞 结束

    • start()
    • 就绪到运行通过系统调度,运行到就绪调用yield()方法(不会释放锁对象)
    • 运行到阻塞 sleep()方法不会释放对象锁 join()方法会释放锁,
    • 当sleep()结束后会,阻塞解除,回到就绪太
  4. sleep 和 wait 的区别

    • sleep是线程休眠,不会释放掉锁,是thread的静态方法
    • wait是线程等待,会释放掉锁,是object中的方法
  5. sleep 和 sleep(0)的区别

    与线程的优先级有关

    线程创建后,会进入线程调度队列。 线程调度队列通常按线程的优先级分成多个队列。 每个优先级都会有一个队列。

    • :ballot_box_with_check: sleep会使线程进入等待状态

    • 调用sleep(0)的时候,如果调度器中不存在优先级>=该线程优先级时,该线程会继续运行。否则,线程会被放入到其优先级相应的队列尾部。就是相当调用sleep(0)时,通常会让该程序中优先级更高或者与其相等的线程获取更多的运行时间。

  6. Lock 与 Synchronized 的区别

    Synchronized

    • 遇到异常或者执行完毕会自动释放锁

    Lock(可重入锁,读写锁)

    • 需要人为的unLock()释放锁资源

    性能方面:在资源竞争不是很激烈的情况下,Synchronized的性能要优于ReetrantLock,但在资源竞争激烈的情况下ReetrantLock的性能更优

    Atomic只能同步一个值,而且一段代码中只能出现一个Atomic变量,多一个同步无效

  7. synchronized 的原理是什么,一般用在什么地方(比如加在静态方法和非静态方法的区别,静态方法和非静态方法同时执行的时候会有影响吗)

    • synchronized底层采用对象锁(mointor)机制(监视器):在执行同步代码块前需要先执行monitorenter指令,退出时执行monitorexit指令,而且有多条monitorexit指令,要保证所获得的锁在正常路径,以及异常执行路径上都能够被解锁
    • 静态方法中锁的是实例对象,非静态方法中锁的是类对象,同事执行不会有影响
      • 静态方法
      • 非静态方法中

    Synchronized用在静态方法和普通方法区别

  8. 用过哪些原子类,他们的原理是什么(CAS 如 AtomicInteger)

JDBC

  • JDBC驱动

接口:是一种能力,是一种标准,是

Everything 文件搜索

简介

背景

意义

  • 解决Windows命令行下文件搜索问题
  • 基于Java开发的工具可以在Windows和Linux平台无差异使用

实现流程

  1. 交互式
  2. 文件遍历,并存入到数据库
  3. 文件检索

技术

  • java(文件操作)

  • Database(插入式H2数据库或者MySQL数据库)

    关于H2优势:

    • 非常快,开源,JDBC API
    • 内存数据库,支持嵌入式和服务器模式
    • 基于浏览器的Console应用
    • 占地面积小:大小约1.5MB的jar文件大小
  • JDBC

  • Lombok(IDEA安装Lombok插件)

  • java多线程

  • 文件系统监控(Apache Commons IO)

目标:搭建项目

  1. 创建Maven项目

  2. 配置pom

  3. 创建包(按照功能分类)

    • cmd:Everything应用程序的命令行交互程序

    • config:Everything应用程序的配置相关类

    • core:Everything应用程序的具体业务实现

      • common

        将file对象转化为thing对象

      • dao

        数据源的获取与连接,以及业务的CRUD(增删改查)

      • index

        索引加拦截,文件路径遍历

      • interceptor

        拦截器的具体实现

      • model

        基本的模型类抽象

      • search

        检索的实现,实现统一调度器

  4. 创建入口程序

  5. 简单的公共代码开发

  6. git管理

    1. Github创建仓库
    2. 本地仓库中git init
    3. 本地项目中创建 .gitignore添加不加入版本管理的目录和文件
    4. git add . -> git commit -m message
    5. git remote add origin http://xxx
    6. git push origin master

    代码更新之后,只需要4,6

ctrl+shift+alt+l

README.md

基本的模型类抽象

  • 文件类型(png jpeg doc exe msi jar zip rar ppt txt sh)
  • 索引File的属性之后的信息 Thing
  • 检索的参数(条件) Condition

设计数据库的表

  • 创建数据库(my_everything)
  • 设计数据库的表(Thing类创建的对象的属性)

数据库编程:(DAO)数据访问对象

  • 创建数据源(DataSource)
  • 执行数据库脚本(初始化数据库)
    • Druid数据源,为监控而生的数据库连接池

检索

  • 数据库的初始化工作

  • 数据库的访问工作(使用DataSource)

  • 实现检索业务(查询)

    final的初始化:直接赋值,构造方初始化法,构造块三种方法

索引

  • 数据库的初始化工作

  • 数据库的访问工作(使用DataSource)

  • 实现检索业务(插入)

    预编译命令设置参数

  • ①如何遍历文件系统中所有文件,②需要对一些特点的文件或目录进行排除,③并且将文件对象转化为Thing对象,调用数据库访问的插入操作

    索引

    • 通过配置类来处理那些文件需要扫描,那些不需要扫描

      C:\(路径) ->[做排除工作]
      
      File(Collection) ->
      
      Thing(Collection) ->
      
      FileIndexDao
      

shift f6 修改文件名称

1.检索 2.索引的遍历 3.重构

统一调度器(创建线程,分发任务)

  1. 构建索引(依赖index功能,业务FileScan)
  2. 检索数据(依赖search功能,业务FileSearch)
  3. 扩展

命令行客户端

  1. 欢迎
  2. 帮助
  3. 退出
  4. 索引
  5. 检索

发现问题

  1. 代码问题(资源未关闭,异常处理,输出信息不完整)

  2. 用户不友好

  3. 索引之后的问题,如果被删除,但是仍然可以被检索(功能缺陷)

  1. 检索的结果数量限制,排序策略,给用户提供可配置的机会

  2. 索引的目录和文件以及排除的目录和文件,给用户提供可配置的机会

  3. 文件系统的监控,文件系统中文件的新增,删除

解决问题

  1. Review(检查代码)

  2. 大家根据情况完善

  3. 删除文件的清理工作

  4. 5 问题 java -jar my-everything-1.0.0jar

    • 目的:通过执行程序的时候,传入参数,让配置信息可以变换
    • 解析

    java -jar my-everything-1.0.0.jar

    –maxReturn=40

    –deptOrderByAsc=false

    –includePath=D:\;E:\workspace

    –excludePath=E:\workspace\java4code

6. 文件系统监控

  1. 文件(目录)新增,删除

  2. 监控操作系统的文件系统中文件的变化

    解决方案:

    • JDK提供的文件监控(WatchService)

    FileSystem WatchService(只能监听一级目录,无法监听更深层次目录)

    • Apache Commons IO 开源库

      • IO工具
      • Input Output
      • Filter
      • Comparator
      • File mointer
      1
      2
      3
      FileAlterationListener //接受文件系统通知,处理业务,是自己要						  实现的一个接口	
      FileAlterationMoniter //负责调度,启动,停止监听器,添加通知 者,依赖Observe
      FileAlterationObserve //如果文件发生变化,发送一个通知告诉 listener去执行处理,需要依赖需 listener对象

如何判断文件发生改变?

  • 重新执行index
  • 遍历文件系统(自己规定间隔时间)

StringBuilder与StringBuffer

  • 方法在栈区储存,独立
  • 放在属性上使用时牵扯到线程安全,StringBufffer

broncho