数据结构 - 堆(Heap)原理介绍和 Java 代码的完整实现
「这是我参与2022首次更文挑战的第11天,活动详情查看:2022首次更文挑战」。
详细介绍了堆(Heap)这种数据结构的特点和原理,并且提供了Java代码的完全实现,包括大顶堆、小顶堆的构建,堆节点的添加、删除,大顶堆、小顶堆的排序等方法!
1 堆的概述
1.1 堆的概述
要想了解堆,就必须了解二叉树的一些基本性质,如果不是很了解二叉树的,可以看看这篇文章:二叉树的入门以及Java实现案例详解。
这里所说的堆(Heap)是数据结构中的堆,而不是内存模型中的堆。堆是一种树形结构,它满足如下性质:
- 堆是一棵完全二叉树,也被称为二叉堆(binary heap),一般说的堆就是指二叉堆,实际上还有左倾堆、右倾堆等,它们不要求是完全二叉树。
- 堆中任意节点的值总是不大于/不小于其子节点的值。
如果每个节点的值都大于或等于其左右孩子节点的值,称为大顶堆/最大堆/大根堆,如下图左;或者每个节点的值都小于或等于其左右孩子节点的值,称为小顶堆/最小堆/小根堆,如下图右。
1.2 堆的常见应用和实现
堆的应用:
- 堆常被用于实现“优先队列”(PriorityQueue)。优先队列可以*添加数据,但取出数据时要从最小值开始按顺序取出;
- 堆还用于实现堆排序。
堆的实现:由于堆作为一颗完全二叉树,因此根据二叉树的性质,完全二叉树能够完美的映射到数组结构中去:如果节点从0开始编号,并把节点映射到数组中之后,则节点之间满足如下关系:
大顶堆:arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2](0<=i<=n/2 -1) 小顶堆:arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2](0<=i<=n/2 -1)
n为数组长度,n/2 -1实际上表示数组从头到尾最后一个非叶子结点的索引位置。
因此,常常使用数组来实现堆结构,比如Java中的PriorityQueue,就是采用数组实现的二叉堆。由于堆算作一个偏序(只有父节点和子节点的大小关系,没有两个子节点之间的大小关系),因此同一批元素采用不同算法构建成的堆在数组中的实际存储顺序是不一定相同的,并且堆排序也是一种不稳定的排序算法。
二叉堆和二叉排序树的区别:
- 在二叉排序树中,左子节点必须比父节点小,右子节点必须必比父节点大。但是在堆中并非如此。在最大堆中两个子节点都必须比父节点小,而在最小堆中,它们都必须比父节点大。关于二叉排序树:二叉排序树的详解以及Java代码的完全实现。
- 二叉排序树一般使用链表实现,占用的内存空间比它们存储的数据要多。必须为节点对象以及左/右子节点指针分配额外的内存。堆可以使用数组来存放数据,节点对象以及左/右子节点存在天然的关系,使用索引即可到达,节省内存。
- 由于二叉排序树中节点大小的性质,在二叉排序树中查找会很快,查找过程类似与有序数组的二分查找,并且查找次数不会超过树的深度,但是在堆中查找会比较慢。使用二叉排序树的目的是为了方便查找节点,使用堆的目的是将最大(或者最小)的节点放在最前面,从而快速的进行相关排序、插入、删除操作。
2 实现原理
这里以大顶堆的构建为例子,该案例对应着下面实现代码中的案例。
2.1 根据数组构建大顶堆
这里的构建堆是从“父节点”入手进行构建。实际上是用到了堆排序的过程中的第一次构建大顶堆的过程,这里不多叙述,具体原理直接看这篇文章:10种常见排序算法原理详解以及Java代码的完全实现,可以直接看其中的堆排序的原理部分,讲的很详细。
最终结果数组中元素位置和映射到堆中的结构如下:
2.2 添加元素构建大顶堆
这里的构建堆是从“新节点”入手进行构建,不同于堆排序的构建方式,这里详细解释一下。
大概原理是: 每添加一个元素,则将其与父节点进行比较,如果新添加节点小于等于父节点,则添加元素到该位置;否则,继续向上寻找父节点,直到找到某个位置,使得位于该位置的新元素的值小于等于对应父节点的元素的值,并且将原位置上的元素一一向后挪动。这里比较抽象,我们看具体的过程。
当添加第1个元素49时,strat=0,此时直接heap[0] = 49,即添加到堆的顶点。此时数组中元素位置和映射到堆中的结构如下:
当添加第2个元素38时,strat=1,parent=0,此时strat>0进入内层循环,判断父节点和子节点的大小,由于49>38,因此break跳出循环,此时直接heap[1] = 49此时数组中元素位置和映射到堆中的结构如下:
当添加第3个元素65时,strat=2,parent=0,此时strat>0进入内层循环,判断父节点和子节点的大小,由于49<65,此时将父节点的值移动到子节点位置处,heap[2] = heap[0],此时数组结构为{49, 38, 49},然后将start的索引值变成父节点的索引值,即start=0,重新计算parent=0。
由于此时start=0,因此结束循环,此时直接heap[start] = 65,即heap[0]= 65。此时数组中元素位置和映射到堆中的结构如下:
当添加第4个元素97时,strat=3,parent=1,此时strat>0进入内层循环,判断父节点和子节点的大小,由于38<97,此时将父节点的值移动到子节点位置处,heap[3] = heap[1],此时数组结构为{65, 38, 49, 38},然后将start的索引值变成父节点的索引值,即start=1,重新计算parent=0。
由于此时start>0开始第二次内层循环,判断父节点和子节点的大小,由于65<97,此时将父节点的值移动到子节点位置处,heap[1] = heap[0],此时数组结构为{65, 65, 49, 38},然后将start的索引值变成父节点的索引值,即start=0,重新计算parent=0。
由于此时start=0,因此结束循环,此时直接heap[start] = 97,即heap[0]= 97。此时数组中元素位置和映射到堆中的结构如下:
当添加第5个元素76时,strat=4,parent=1,此时strat>0进入内层循环,判断父节点和子节点的大小,由于65<76,此时将父节点的值移动到子节点位置处,heap[4] = heap[1],此时数组结构为{97, 65, 49, 38, 65},然后将start的索引值变成父节点的索引值,即start=1,重新计算parent=0。
由于此时start>0开始第二次内层循环,判断父节点和子节点的大小,由于76<97,因此break跳出循环,此时直接heap[1] = 76,此时数组中元素位置和映射到堆中的结构如下:
当添加第6个元素13时,strat=5,parent=2,此时strat>0进入内层循环,判断父节点和子节点的大小,由于13<49,因此break跳出循环,此时直接heap[5] = 13,此时数组中元素位置和映射到堆中的结构如下:
当添加第7个元素27时,strat=6,parent=2,此时strat>0进入内层循环,判断父节点和子节点的大小,由于27<49,因此break跳出循环,此时直接heap[6] = 27,此时数组中元素位置和映射到堆中的结构如下:
当添加第8个元素49时,strat=7,parent=3,此时strat>0进入内层循环,判断父节点和子节点的大小,由于49>38,此时将父节点的值移动到子节点位置处,heap[7] = heap[3],此时数组结构为{97, 76, 49, 38, 65, 13, 27, 38},然后将start的索引值变成父节点的索引值,即start=3,重新计算parent=1。
由于此时start>0开始第二次内层循环,判断父节点和子节点的大小,由于49<76,因此break跳出循环,此时直接heap[3] = 49,此时数组中元素位置和映射到堆中的结构如下:
当添加第9个元素78时,strat=8,parent=3,此时strat>0进入内层循环,判断父节点和子节点的大小,由于78>49,此时将父节点的值移动到子节点位置处,heap[8] = heap[3],此时数组结构为{97, 76, 49, 49, 65, 13, 27, 38, 49},然后将start的索引值变成父节点的索引值,即start=3,重新计算parent=1。
由于此时start>0开始第二次内层循环,判断父节点和子节点的大小,由于78>76,此时将父节点的值移动到子节点位置处,heap[3] = heap[1],此时数组结构为{97, 76, 49, 76, 65, 13, 27, 38, 49},然后将start的索引值变成父节点的索引值,即start=1,重新计算parent=0。
由于此时start>0开始第三次内层循环,判断父节点和子节点的大小,由于78<97,因此break跳出循环,此时直接heap[1] = 78,此时数组中元素位置和映射到堆中的结构如下:
这就是最终的构建结果,可以看到它和直接使用数组构建的最终结果序列是不一样的,但是他们都符合大顶堆的要求,这也证明了大顶堆的序列不唯一的性质。
2.3 删除元素
- 首先在数组中查找是否存在对应的元素,如果不存在则返回false;
- 如果存在则获取第一个找到的元素的索引(因为有可能有相同的元素,这里的删除是删除第一个找到的元素);
- 之后一步就和堆排序的过程中的重构大顶堆是一致的,实际上就是将需要删除的元素与堆尾元素互换,然后移除堆尾元素,之后从被删除元素的索引处开始向下重构大顶堆的过程。
- 向下重构大顶堆的操作只能保证从该索引位置开始下面的结构满足堆的要求。但是这里的向下重构和堆排序那里不同的是,堆排序是从堆顶部开始重构的,因此能够保证整个堆的满足要求,而这里却可能从堆的中间的某个结点开始的,在向下重构完毕之后,还需要校验起始索引位置的结点有没有调整位置,因为最开始就是一个大顶堆结构,即父结点大于等于子结点,如果调整了位置,那么说明起始索引之前的结构也满足要求;如果没有调整位置,那么可能出现起始位置的元素不仅大于等于其子结点,还可能大于其父结点的情况,此时还需要一次从该位置开始的向上的重构大顶堆来保证从该索引位置开始上面的结构也满足堆的要求!
2.4 堆排序
这里不多叙述,具体原理直接看这篇文章:10种常见排序算法原理详解以及Java代码的完全实现,可以直接看其中的堆排序的原理部分,讲的很详细。
3 大顶堆的实现
提供基于数组实现的大顶堆的类,提供根据集合构建大顶堆的方法,提供添加、删除节点的方法,提供了大顶堆的堆排序(顺序)的方法。
/**
* 大顶堆的实现
* {@link MaxBinaryHeap#MaxBinaryHeap()} 初始化空的大顶堆,使用默认容量
* {@link MaxBinaryHeap#MaxBinaryHeap(int)} 初始化空的大顶堆,使用指定容量
* {@link MaxBinaryHeap#MaxBinaryHeap(Comparator)} 初始化空的大顶堆,使用指定比较器
* {@link MaxBinaryHeap#MaxBinaryHeap(int, Comparator)} 初始化空的大顶堆,使用指定容量和比较器
* {@link MaxBinaryHeap#MaxBinaryHeap(Collection)} 根据指定集合元素构建大顶堆
* {@link MaxBinaryHeap#MaxBinaryHeap(Collection, Comparator)} 根据指定集合元素构建大顶堆,使用自定义比较器
* {@link MaxBinaryHeap#add(Object)} 添加元素,并重构大顶堆
* {@link MaxBinaryHeap#remove(Object)} 删除元素,并重构大顶堆
* {@link MaxBinaryHeap#heapSort()} 大顶堆排序(顺序)
* {@link MaxBinaryHeap#toString()} 输出大顶堆
*
* @author lx
*/
public class MaxBinaryHeap<E> {
/**
* 堆的物理存储结构,即使用数组来实现
*/
private Object[] heap;
/**
* 节点数量
*/
private int size;
/**
* 容量
*/
private static int capacity = 16;
/**
* 如果元素使用自然排序,那么比较器为null;否则使用比较器比较
*/
private final Comparator<? super E> cmp;
/**
* 对元素进行比较大小的方法,如果传递了自定义比较器,则使用自定义比较器,否则则需要数据类型实现Comparable接口
*
* @param e1 被比较的第一个对象
* @param e2 被比较的第二个对象
* @return 0 相等 ;小于0 e1 < e2 ;大于0 e1 > e2
*/
private int compare(E e1, E e2) {
if (cmp != null) {
return cmp.compare(e1, e2);
} else {
return ((Comparable<E>) e1).compareTo(e2);
}
}
/**
* 初始化空的大顶堆,使用默认容量
*/
public MaxBinaryHeap() {
this(capacity, null);
}
/**
* 初始化空的大顶堆,指定容量
*
* @param initCapacity 指定容量数组
*/
public MaxBinaryHeap(int initCapacity) {
this(initCapacity, null);
}
/**
* 初始化空的大顶堆,指定比较器
*
* @param comparator 指定比较器
*/
public MaxBinaryHeap(Comparator<? super E> comparator) {
this(capacity, comparator);
}
/**
* 初始化空的大顶堆,指定容量和比较器
*
* @param initCapacity 指定数组容量
* @param comparator 指定比较器
*/
public MaxBinaryHeap(int initCapacity, Comparator<? super E> comparator) {
if (initCapacity < 1) {
throw new IllegalArgumentException();
}
capacity = initCapacity;
this.heap = new Object[initCapacity];
cmp = comparator;
}
/**
* 同通过一批数据初始化大顶堆
*
* @param heap 数组
*/
public MaxBinaryHeap(Collection<? extends E> heap) {
this(heap, null);
}
/**
* 同通过一批数据和指定比较器初始化大顶堆
*
* @param heap 数组
* @param comparator 自定义的比较器
*/
public MaxBinaryHeap(Collection<? extends E> heap, Comparator<? super E> comparator) {
Object[] array = heap.toArray();
this.cmp = comparator;
if (array.getClass() != Object[].class) {
array = Arrays.copyOf(array, array.length, Object[].class);
}
for (Object o : array) {
if (o == null) {
throw new NullPointerException();
}
}
this.heap = array;
this.size = array.length;
buildHeap(this.heap);
}
/**
* 同通过一批数据初始化大顶堆
*
* @param heap 数据数组
*/
private void buildHeap(Object[] heap) {
/*i从最后一个非叶子节点的索引开始,递减构建,直到i=-1结束循环
这里元素的索引是从0开始的,所以最后一个非叶子节点array.length/2 - 1,这是利用了完全二叉树的性质*/
for (int i = heap.length / 2 - 1; i >= 0; i--) {
buildHeap(heap, i, heap.length);
}
}
/**
* 同通过一批数初始化大顶堆
*
* @param arr 数据数组
* @param i 非叶子节点的索引
* @param length 堆长度
*/
private void buildHeap(Object[] arr, int i, int length) {
//先把当前非叶子节点元素取出来,因为当前元素可能要一直移动
Object temp;
//节点的子节点的索引
int childIndex;
/*循环判断父节点是否大于两个子节点,如果左子节点索引大于等于堆长度 或者父节点大于两个子节点 则结束循环*/
for (temp = arr[i]; (childIndex = 2 * i + 1) < length; i = childIndex) {
//childIndex + 1 < length 说明该节点具有右子节点,并且如果如果右子节点的值大于左子节点,那么childIndex自增1,即childIndex指向右子节点索引
if (childIndex + 1 < length && compare((E) arr[childIndex], (E) arr[childIndex + 1]) < 0) {
childIndex++;
}
//如果发现最大子节点(左、右子节点)大于根节点,为了满足大顶堆根节点的值大于子节点,需要进行值的交换
//如果子节点更换了,那么,以子节点为根的子树会受到影响,所以,交换之后继续循环对子节点所在的树进行判断
if (compare((E) arr[childIndex], (E) temp) > 0) {
swap(arr, i, childIndex);
} else {
//走到这里,说明父节点大于最大的子节点,满足大顶堆的条件,直接终止循环
break;
}
}
}
/**
* 大顶堆排序(顺序)
* 实际上就是不断循环将堆顶元素与堆尾元素互换,然后移除堆尾元素,之后重构大顶堆的过程
*/
public Object[] heapSort() {
//使用大顶堆的副本进行排序输出
Object[] arr = Arrays.copyOf(heap, size);
/*开始堆排序,i = arr.length - 1,即从大顶堆尾部的数开始,直到i=0结束循环*/
for (int i = size - 1; i > 0; i--) {
//交换堆顶与堆尾元素顺序
swap(arr, 0, i);
//重新构建大顶堆
buildHeap(arr, 0, i);
}
return arr;
}
/**
* 添加节点,构建大顶堆
*
* @param e 需要添加的节点
*/
public void add(E e) {
/*判空*/
if (e == null) {
throw new NullPointerException();
}
/*检查容量*/
if (heap.length == size) {
resize();
}
/*添加节点*/
addNode(e, size++);
}
/**
* 添加节点,并向上重构大顶堆,最终找到一个位置加入新结点e,该位置的结点小于等于其父结点
*
* @param e 要添加的节点
*/
private void addNode(E e, int start) {
//获取size处节点的父节点索引
int parent = (start - 1) / 2;
/*如果size>0 寻找合适的位置:在某个插入的位置的新节点小于等于对应的父节点的值*/
while (start > 0) {
//判断父节点和新子节点的大小,如果父节点小于等于新子节点,那么符合小顶堆的要求,重构结束,该start就是子节点插入的位置
if (compare((E) heap[parent], e) >= 0) {
break;
} else {
//否则,将父节点的值移动到子节点的位置处
heap[start] = heap[parent];
//将start的索引值变成父节点的索引值
start = parent;
//重新计算父节点的索引,不断循环,直到找到父节点值小于等于新子节点值的索引
parent = (start - 1) / 2;
}
}
//在合适的位置插入新节点值
heap[start] = e;
}
/**
* 底层数组扩容
*/
private void resize() {
heap = Arrays.copyOf(heap, heap.length * 2, Object[].class);
}
/**
* 交换元素
*
* @param arr 数组
* @param a 元素的下标
* @param b 元素的下标
*/
private static void swap(Object[] arr, int a, int b) {
Object temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
/**
* 删除找到的第一个堆节点,并且重构大顶堆
*
* @param e 需要删除的节点
* @return false 删除失败 true 删除成功
*/
public boolean remove(E e) {
int eIndex = -1;
for (int i = 0; i < size; i++) {
//这里是通过compare来查找元素是否相同的
if (compare((E) heap[i], e) == 0) {
eIndex = i;
}
}
/*没找到需要删除的元素*/
if (eIndex == -1) {
return false;
}
/*找到了*/
//原尾部元素x
E x = (E) heap[size - 1];
//交换查找到的元素与堆尾元素的位置
swap(heap, eIndex, size - 1);
//移除堆尾元素
heap[size--] = null;
//从eIndex开始向下重新构建大顶堆
buildHeap(heap, eIndex, size);
//构建之后如果eIndex位置的元素就是x,说明没有调整堆结构,那么将该位置的元素看成新插入的元素,需要向上构建大顶堆
if (heap[eIndex] == x) {
//调用addNode从eIndex开始向上重构大顶堆
addNode(x, eIndex);
}
return true;
}
public int size(){
return size;
}
@Override
public String toString() {
StringBuilder stringBuilder = new StringBuilder();
stringBuilder.append("[");
for (int i = 0; i < size; i++) {
stringBuilder.append(heap[i]);
if (i != size - 1) {
stringBuilder.append(",");
}
}
stringBuilder.append("]");
return stringBuilder.toString();
}
}
4 小顶堆的实现
提供基于数组实现的小顶堆的类,提供根据集合构建小顶堆的方法,提供添加、删除节点的方法,提供了小顶堆的堆排序(逆序)的方法。实际上,大顶堆和小顶堆的实现的区别仅仅在于某些比较条件是相反,大部分代码都是相同的。
/**
* 小顶堆的实现
* {@link MinBinaryHeap#MinBinaryHeap()} 初始化空的小顶堆,使用默认容量
* {@link MinBinaryHeap#MinBinaryHeap(int)} 初始化空的小顶堆,使用指定容量
* {@link MinBinaryHeap#MinBinaryHeap(Comparator)} 初始化空的小顶堆,使用指定比较器
* {@link MinBinaryHeap#MinBinaryHeap(int, Comparator)} 初始化空的小顶堆,使用指定容量和比较器
* {@link MinBinaryHeap#MinBinaryHeap(Collection)} 根据指定集合元素构建小顶堆
* {@link MinBinaryHeap#MinBinaryHeap(Collection, Comparator)} 根据指定集合元素构建小顶堆,使用自定义比较器
* {@link MinBinaryHeap#add(Object)} 添加元素,并重构小顶堆
* {@link MinBinaryHeap#remove(Object)} 删除元素,并重构小顶堆
* {@link MinBinaryHeap#heapSort()} 小顶堆排序(顺序)
* {@link MinBinaryHeap#toString()} 输出小顶堆
*
* @author lx
*/
public class MinBinaryHeap<E> {
/**
* 堆的物理结构,即使用数组来实现
*/
private Object[] heap;
/**
* 节点数量
*/
private int size;
/**
* 容量
*/
private static int capacity = 16;
/**
* 如果元素使用自然排序,那么比较器为null
*/
private final Comparator<? super E> cmp;
/**
* 对元素进行比较大小的方法,如果传递了自定义比较器,则使用自定义比较器,否则则需要数据类型实现Comparable接口
*
* @param e1 被比较的第一个对象
* @param e2 被比较的第二个对象
* @return 0 相等 ;小于0 e1 < e2 ;大于0 e1 > e2
*/
private int compare(E e1, E e2) {
if (cmp != null) {
return cmp.compare(e1, e2);
} else {
return ((Comparable<E>) e1).compareTo(e2);
}
}
/**
* 初始化空的小顶堆,使用默认容量
*/
public MinBinaryHeap() {
this(capacity, null);
}
/**
* 初始化空的小顶堆,指定容量
*
* @param initCapacity 指定容量数组
*/
public MinBinaryHeap(int initCapacity) {
this(initCapacity, null);
}
/**
* 初始化空的小顶堆,指定比较器
*
* @param comparator 指定比较器
*/
public MinBinaryHeap(Comparator<? super E> comparator) {
this(capacity, comparator);
}
/**
* 初始化空的小顶堆,指定容量和比较器
*
* @param initCapacity 指定数组容量
* @param comparator 指定比较器
*/
public MinBinaryHeap(int initCapacity, Comparator<? super E> comparator) {
if (initCapacity < 1) {
throw new IllegalArgumentException();
}
capacity = initCapacity;
this.heap = new Object[initCapacity];
cmp = comparator;
}
/**
* 同通过一批数据初始化小顶堆
*
* @param heap 数组
*/
public MinBinaryHeap(Collection<? extends E> heap) {
this(heap, null);
}
/**
* 同通过一批数据和指定比较器初始化小顶堆
*
* @param heap 数组
* @param comparator 自定义的比较器
*/
public MinBinaryHeap(Collection<? extends E> heap, Comparator<? super E> comparator) {
Object[] array = heap.toArray();
this.cmp = comparator;
if (array.getClass() != Object[].class) {
array = Arrays.copyOf(array, array.length, Object[].class);
}
for (Object o : array) {
if (o == null) {
throw new NullPointerException();
}
}
this.heap = array;
this.size = array.length;
buildHeap(this.heap);
}
/**
* 构建小顶堆
*
* @param heap 一批数据
*/
private void buildHeap(Object[] heap) {
/*i从最后一个非叶子节点的索引开始,递减构建,直到i=-1结束循环
这里元素的索引是从0开始的,所以最后一个非叶子节点array.length/2 - 1,这是利用了完全二叉树的性质*/
for (int i = heap.length / 2 - 1; i >= 0; i--) {
buildHeap(heap, i, heap.length);
}
}
/**
* 从指定索引向下构建小顶堆,最终该位置的结点小于等于其子结点
*
* @param arr 数组
* @param i 非叶子节点的索引
* @param length 堆长度
*/
private void buildHeap(Object[] arr, int i, int length) {
//先把当前非叶子节点元素取出来,因为当前元素可能要一直移动
Object temp;
//节点的子节点的索引
int childIndex;
/*循环判断父节点是否大于两个子节点,如果左子节点索引大于等于堆长度 或者父节点大于两个子节点 则结束循环*/
for (temp = arr[i]; (childIndex = 2 * i + 1) < length; i = childIndex) {
//childIndex + 1 < length 说明该节点具有右子节点,并且如果如果右子节点的值小于左子节点,那么childIndex自增1,即childIndex指向右子节点索引
if (childIndex + 1 < length && compare((E) arr[childIndex], (E) arr[childIndex + 1]) > 0) {
childIndex++;
}
//如果发现最小子节点(左、右子节点)小于根节点,为了满足小顶堆根节点的值小于子节点,需要进行值的交换
//如果子节点更换了,那么,以子节点为根的子树会受到影响,所以,交换之后继续循环对子节点所在的树进行判断
if (compare((E) arr[childIndex], (E) temp) < 0) {
swap(arr, i, childIndex);
} else {
//走到这里,说明父节点小于等于最小的子节点,满足小顶堆的条件,直接终止循环
break;
}
}
}
/**
* 小顶堆排序(顺序)
*
* @param arr 需要被排序的数据集合
*/
public void bigHeapSort(Object[] arr) {
/*1、构建小顶堆*/
/*i从最后一个非叶子节点的索引开始,递减构建,直到i=-1结束循环
这里元素的索引是从0开始的,所以最后一个非叶子节点array.length/2 - 1,这是利用了完全二叉树的性质*/
for (int i = arr.length / 2 - 1; i >= 0; i--) {
buildHeap(arr, i, arr.length);
}
/*2、开始堆排序,i = arr.length - 1,即从小顶堆尾部的数开始,直到i=0结束循环*/
for (int i = arr.length - 1; i > 0; i--) {
//交换堆顶与堆尾元素顺序
swap(arr, 0, i);
//重新构建小顶堆
buildHeap(arr, 0, i);
}
}
/**
* 小顶堆排序(逆序)
* 实际上就是不断循环将堆顶元素与堆尾元素互换,然后移除堆尾元素,之后重构小顶堆的过程
*/
public Object[] heapSort() {
//使用小顶堆的副本进行排序输出
Object[] arr = Arrays.copyOf(heap, size);
/*2、开始堆排序,i = arr.length - 1,即从小顶堆尾部的数开始,直到i=0结束循环*/
for (int i = arr.length - 1; i > 0; i--) {
//交换堆顶与堆尾元素顺序
swap(arr, 0, i);
//重新构建小顶堆,此时堆的大小为交换前堆大小-1
buildHeap(arr, 0, i);
}
return arr;
}
/**
* 添加节点
*
* @param e 被添加的节点元素
*/
public void add(E e) {
/*判空*/
if (e == null) {
throw new NullPointerException();
}
/*检查容量*/
if (heap.length == size) {
resize();
}
/*添加节点*/
addNode(e, size++);
}
/**
* 添加节点,并向上重构小顶堆,最终找到一个位置加入新结点e,该位置的结点大于等于其父结点
*
* @param e 要添加的节点
* @param start 即新添加元素所在的索引
*/
private void addNode(E e, int start) {
//获取size处结点的父节点索引
int parent = (start - 1) / 2;
/*如果size>0 寻找合适的位置:在某个插入的位置的新节点大于等于对应的父节点的值*/
while (start > 0) {
//判断父节点和新子节点的大小,如果父节点小于等于新子节点,那么符合小顶堆的要求,重构结束
if (compare((E) heap[parent], e) <= 0) {
break;
} else {
//否则,将父节点的值移动到子节点的位置处
heap[start] = heap[parent];
//将start的索引值变成父节点的索引值
start = parent;
//重新计算父节点的索引,不断循环,直到找到父节点值小于等于新子节点值的索引
parent = (start - 1) / 2;
}
}
//在合适的位置插入新节点值
heap[start] = e;
}
/**
* 扩容
*/
private void resize() {
heap = Arrays.copyOf(heap, heap.length * 2, Object[].class);
}
/**
* 交换元素
*
* @param arr 数组
* @param a 元素的下标
* @param b 元素的下标
*/
private static void swap(Object[] arr, int a, int b) {
Object temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
/**
* 删除找到的第一个堆节点,并且重构小顶堆
*
* @param e 需要删除的节点
* @return false 删除失败 true 删除成功
*/
public boolean remove(E e) {
int eIndex = -1;
for (int i = 0; i < size; i++) {
if (compare((E) heap[i], e) == 0) {
eIndex = i;
}
}
if (eIndex == -1) {
return false;
}
//原尾部元素x
E x = (E) heap[size - 1];
//交换查找到的元素与堆尾元素的位置
swap(heap, eIndex, size - 1);
//移除堆尾元素
heap[size--] = null;
//从eIndex开始向下重新构建小顶堆
buildHeap(heap, eIndex, size);
//构建之后如果eIndex位置的元素就是x,说明没有调整堆结构,那么将该位置的元素看成新插入的元素,需要向上构建小顶堆
if (heap[eIndex] == x) {
//调用addNode从eIndex开始向上重构小顶堆
addNode(x, eIndex);
}
return true;
}
@Override
public String toString() {
StringBuilder stringBuilder = new StringBuilder();
stringBuilder.append("[");
for (int i = 0; i < size; i++) {
stringBuilder.append(heap[i]);
if (i != size - 1) {
stringBuilder.append(",");
}
}
stringBuilder.append("]");
return stringBuilder.toString();
}
}
5 测试案例
/**
* 堆测试
*
* @author lx
*/
public class BinaryTest {
/**
* 通过数组在构造器中构建大顶堆
*/
@Test
public void testMaxBinaryHeap1() {
Integer[] arr = new Integer[]{49, 38, 65, 97, 76, 13, 27, 49, 78};
//构建大顶堆
MaxBinaryHeap<Integer> maxBinaryHeap = new MaxBinaryHeap<>(Arrays.asList(arr));
//输出大顶堆
System.out.println(maxBinaryHeap);
//添加节点,并且重构大顶堆
maxBinaryHeap.add(11);
maxBinaryHeap.add(77);
//输出大顶堆
System.out.println(maxBinaryHeap);
//删除节点,并且重构大顶堆
//删除失败
System.out.println(maxBinaryHeap.remove(79));
//删除成功
System.out.println(maxBinaryHeap.remove(78));
//输出大顶堆
System.out.println(maxBinaryHeap);
//大顶堆排序(顺序排序)
System.out.println(Arrays.toString(maxBinaryHeap.heapSort()));
//输出大顶堆
System.out.println(maxBinaryHeap);
}
/**
* 通过add方法构建大顶堆
*/
@Test
public void testMaxBinaryHeap2() {
MaxBinaryHeap<Integer> maxBinaryHeap = new MaxBinaryHeap<>();
maxBinaryHeap.add(49);
maxBinaryHeap.add(38);
maxBinaryHeap.add(65);
maxBinaryHeap.add(97);
maxBinaryHeap.add(76);
maxBinaryHeap.add(13);
maxBinaryHeap.add(27);
maxBinaryHeap.add(49);
maxBinaryHeap.add(78);
//输出大顶堆 [97,78,49,76,65,13,27,38,49]
System.out.println(maxBinaryHeap);
//添加节点,并且重构大顶堆
maxBinaryHeap.add(11);
maxBinaryHeap.add(77);
//输出大顶堆
System.out.println(maxBinaryHeap);
//删除节点,你
//删除失败
System.out.println(maxBinaryHeap.remove(79));
//删除成功
System.out.println(maxBinaryHeap.remove(78));
//输出大顶堆
System.out.println(maxBinaryHeap);
//大顶堆排序(顺序排序)
System.out.println(Arrays.toString(maxBinaryHeap.heapSort()));
//输出大顶堆
System.out.println(maxBinaryHeap);
}
/**
* 通过数组在构造器中构建小顶堆
*/
@Test
public void testMinBinaryHeap1() {
Integer[] arr = new Integer[]{49, 38, 65, 97, 76, 13, 27, 49, 78};
//构建小顶堆
MinBinaryHeap<Integer> minBinaryHeap = new MinBinaryHeap<>(Arrays.asList(arr));
//输出小顶堆
System.out.println(minBinaryHeap);
//添加节点,并且重构小顶堆
minBinaryHeap.add(11);
minBinaryHeap.add(77);
//输出小顶堆
System.out.println(minBinaryHeap);
//删除节点,并且重构小顶堆
//删除失败
System.out.println(minBinaryHeap.remove(79));
//删除成功
System.out.println(minBinaryHeap.remove(78));
//输出小顶堆
System.out.println(minBinaryHeap);
//小顶堆排序(逆序排序)
System.out.println(Arrays.toString(minBinaryHeap.heapSort()));
//输出小顶堆
System.out.println(minBinaryHeap);
}
/**
* 通过add方法构建小顶堆
*/
@Test
public void testMinBinaryHeap2() {
MinBinaryHeap<Integer> minBinaryHeap = new MinBinaryHeap<>();
minBinaryHeap.add(49);
minBinaryHeap.add(38);
minBinaryHeap.add(
上一篇:
java 输出语句_什么是 java 输入/输出语句
下一篇:
JAVA 核心异常处理和调试技能
推荐阅读
-
【2022新手指南】Java编程进阶之路 - 六、技术架构篇 ### MySQL索引底层解析与优化实战 - 你会讲解MySQL索引的数据结构吗?性能调优技巧知多少? - Redis深度揭秘:你知道多少?从基础到哨兵、主从复制全梳理 - Redis持久化及哨兵模式详解,还有集群搭建和Leader选举黑箱打开 - Zookeeper是个啥?特性和应用场景大公开 - ZooKeeper集群搭建攻略及 Leader选举、读写一致性、共享锁实现细节 - 探究ZooKeeper中的Leader选举机制及其在分布式环境中的作用 - Zab协议深入剖析:原理、功能与在Zookeeper中的核心地位 - RabbitMQ全方位解读:工作模式、消费限流、可靠投递与配置策略 - 设计者视角:RabbitMQ过期时间、死信队列与延时队列实践指南 - RocketMQ特性和应用场景揭示:理解其精髓与差异化优势 - Kafka详细介绍:特性及广泛应用于实时数据处理的场景解析 - ElasticSearch实力揭秘:特性概述与作为搜索引擎的广泛应用 - MongoDB认知升级:非关系型数据库的优势阐述,安装与使用实战教学 - BIO/NIO/AIO网络模型对比:掌握它们的区别与在网络编程中的实际应用 - Netty带你飞:理解其超快速度背后的秘密,包括线程模型分析 - 网络通信黑科技:Netty编解码原理与常用编解码器的应用,Protostuff实战演示 - 解密Netty粘包与拆包现象,怎样有效应对这一常见问题 - 自定义Netty心跳检测机制,轻松调整检测间隔时间的艺术 - Dubbo轻骑兵介绍:核心特性概览,服务降级实战与其实现益处 - Dubbo三大神器解读:本地存根与本地伪装的实战运用与优势呈现 ----------------------- 七、结语与回顾
-
SSM三大框架基础面试题-一、Spring篇 什么是Spring框架? Spring是一种轻量级框架,提高开发人员的开发效率以及系统的可维护性。 我们一般说的Spring框架就是Spring Framework,它是很多模块的集合,使用这些模块可以很方便地协助我们进行开发。这些模块是核心容器、数据访问/集成、Web、AOP(面向切面编程)、工具、消息和测试模块。比如Core Container中的Core组件是Spring所有组件的核心,Beans组件和Context组件是实现IOC和DI的基础,AOP组件用来实现面向切面编程。 Spring的6个特征: 核心技术:依赖注入(DI),AOP,事件(Events),资源,i18n,验证,数据绑定,类型转换,SpEL。 测试:模拟对象,TestContext框架,Spring MVC测试,WebTestClient。 数据访问:事务,DAO支持,JDBC,ORM,编组XML。 Web支持:Spring MVC和Spring WebFlux Web框架。 集成:远程处理,JMS,JCA,JMX,电子邮件,任务,调度,缓存。 语言:Kotlin,Groovy,动态语言。 列举一些重要的Spring模块? Spring Core:核心,可以说Spring其他所有的功能都依赖于该类库。主要提供IOC和DI功能。 Spring Aspects:该模块为与AspectJ的集成提供支持。 Spring AOP:提供面向切面的编程实现。 Spring JDBC:Java数据库连接。 Spring JMS:Java消息服务。 Spring ORM:用于支持Hibernate等ORM工具。 Spring Web:为创建Web应用程序提供支持。 Spring Test:提供了对JUnit和TestNG测试的支持。 谈谈自己对于Spring IOC和AOP的理解 IOC(Inversion Of Controll,控制反转)是一种设计思想: 在程序中手动创建对象的控制权,交由给Spring框架来管理。IOC在其他语言中也有应用,并非Spring特有。IOC容器实际上就是一个Map(key, value),Map中存放的是各种对象。 将对象之间的相互依赖关系交给IOC容器来管理,并由IOC容器完成对象的注入。这样可以很大程度上简化应用的开发,把应用从复杂的依赖关系中解放出来。IOC容器就像是一个工厂一样,当我们需要创建一个对象的时候,只需要配置好配置文件/注解即可,完全不用考虑对象是如何被创建出来的。在实际项目中一个Service类可能由几百甚至上千个类作为它的底层,假如我们需要实例化这个Service,可能要每次都搞清楚这个Service所有底层类的构造函数,这可能会把人逼疯。如果利用IOC的话,你只需要配置好,然后在需要的地方引用就行了,大大增加了项目的可维护性且降低了开发难度。 Spring中的bean的作用域有哪些? 1.singleton:该bean实例为单例 2.prototype:每次请求都会创建一个新的bean实例(多例)。 3.request:每一次HTTP请求都会产生一个新的bean,该bean仅在当前HTTP request内有效。 4.session:每一次HTTP请求都会产生一个新的bean,该bean仅在当前HTTP session内有效。 5.global-session:全局session作用域,仅仅在基于Portlet的Web应用中才有意义,Spring5中已经没有了。Portlet是能够生成语义代码(例如HTML)片段的小型Java Web插件。它们基于Portlet容器,可以像Servlet一样处理HTTP请求。但是与Servlet不同,每个Portlet都有不同的会话。 Spring中的单例bean的线程安全问题了解吗? 概念用于理解:大部分时候我们并没有在系统中使用多线程,所以很少有人会关注这个问题。单例bean存在线程问题,主要是因为当多个线程操作同一个对象的时候,对这个对象的非静态成员变量的写操作会存在线程安全问题。 有两种常见的解决方案(用于回答的点): 1.在bean对象中尽量避免定义可变的成员变量(不太现实)。 2.在类中定义一个ThreadLocal成员变量,将需要的可变成员变量保存在ThreadLocal(线程本地化对象)中(推荐的一种方式)。 ThreadLocal解决多线程变量共享问题(参考博客):https://segmentfault.com/a/1190000009236777 Spring中Bean的生命周期: 1.Bean容器找到配置文件中Spring Bean的定义。 2.Bean容器利用Java Reflection API创建一个Bean的实例。 3.如果涉及到一些属性值,利用set方法设置一些属性值。 4.如果Bean实现了BeanNameAware接口,调用setBeanName方法,传入Bean的名字。 5.如果Bean实现了BeanClassLoaderAware接口,调用setBeanClassLoader方法,传入ClassLoader对象的实例。 6.如果Bean实现了BeanFactoryAware接口,调用setBeanClassFacotory方法,传入ClassLoader对象的实例。 7.与上面的类似,如果实现了其他*Aware接口,就调用相应的方法。 8.如果有和加载这个Bean的Spring容器相关的BeanPostProcessor对象,执postProcessBeforeInitialization方法。 9.如果Bean实现了InitializingBean接口,执行afeterPropertiesSet方法。 10.如果Bean在配置文件中的定义包含init-method属性,执行指定的方法。 11.如果有和加载这个Bean的Spring容器相关的BeanPostProcess对象,执行postProcessAfterInitialization方法。 12.当要销毁Bean的时候,如果Bean实现了DisposableBean接口,执行destroy方法。 13.当要销毁Bean的时候,如果Bean在配置文件中的定义包含destroy-method属性,执行指定的方法。 Spring框架中用到了哪些设计模式? 1.工厂设计模式:Spring使用工厂模式通过BeanFactory和ApplicationContext创建bean对象。 2.代理设计模式:Spring AOP功能的实现。 3.单例设计模式:Spring中的bean默认都是单例的。 4.模板方法模式:Spring中的jdbcTemplate、hibernateTemplate等以Template结尾的对数据库操作的类,它们就使用到了模板模式。 5.包装器设计模式:我们的项目需要连接多个数据库,而且不同的客户在每次访问中根据需要会去访问不同的数据库。这种模式让我们可以根据客户的需求能够动态切换不同的数据源。 6.观察者模式:Spring事件驱动模型就是观察者模式很经典的一个应用。 7.适配器模式:Spring AOP的增强或通知(Advice)使用到了适配器模式、Spring MVC中也是用到了适配器模式适配Controller。 还有很多。。。。。。。 @Component和@Bean的区别是什么 1.作用对象不同。@Component注解作用于类,而@Bean注解作用于方法。 2.@Component注解通常是通过类路径扫描来自动侦测以及自动装配到Spring容器中(我们可以使用@ComponentScan注解定义要扫描的路径)。@Bean注解通常是在标有该注解的方法中定义产生这个bean,告诉Spring这是某个类的实例,当我需要用它的时候还给我。 3.@Bean注解比@Component注解的自定义性更强,而且很多地方只能通过@Bean注解来注册bean。比如当引用第三方库的类需要装配到Spring容器的时候,就只能通过@Bean注解来实现。 @Configuration public class AppConfig { @Bean public TransferService transferService { return new TransferServiceImpl; } } <beans> <bean id="transferService" class="com.kk.TransferServiceImpl"/> </beans> @Bean public OneService getService(status) { case (status) { when 1: return new serviceImpl1; when 2: return new serviceImpl2; when 3: return new serviceImpl3; } } 将一个类声明为Spring的bean的注解有哪些? 声明bean的注解: @Component 组件,没有明确的角色 @Service 在业务逻辑层使用(service层) @Repository 在数据访问层使用(dao层) @Controller 在展现层使用,控制器的声明 注入bean的注解: @Autowired:由Spring提供 @Inject:由JSR-330提供 @Resource:由JSR-250提供 *扩:JSR 是 java 规范标准 Spring事务管理的方式有几种? 1.编程式事务:在代码中硬编码(不推荐使用)。 2.声明式事务:在配置文件中配置(推荐使用),分为基于XML的声明式事务和基于注解的声明式事务。 Spring事务中的隔离级别有哪几种? 在TransactionDefinition接口中定义了五个表示隔离级别的常量:ISOLATION_DEFAULT:使用后端数据库默认的隔离级别,Mysql默认采用的REPEATABLE_READ隔离级别;Oracle默认采用的READ_COMMITTED隔离级别。ISOLATION_READ_UNCOMMITTED:最低的隔离级别,允许读取尚未提交的数据变更,可能会导致脏读、幻读或不可重复读。ISOLATION_READ_COMMITTED:允许读取并发事务已经提交的数据,可以阻止脏读,但是幻读或不可重复读仍有可能发生ISOLATION_REPEATABLE_READ:对同一字段的多次读取结果都是一致的,除非数据是被本身事务自己所修改,可以阻止脏读和不可重复读,但幻读仍有可能发生。ISOLATION_SERIALIZABLE:最高的隔离级别,完全服从ACID的隔离级别。所有的事务依次逐个执行,这样事务之间就完全不可能产生干扰,也就是说,该级别可以防止脏读、不可重复读以及幻读。但是这将严重影响程序的性能。通常情况下也不会用到该级别。 Spring事务中有哪几种事务传播行为? 在TransactionDefinition接口中定义了八个表示事务传播行为的常量。 支持当前事务的情况:PROPAGATION_REQUIRED:如果当前存在事务,则加入该事务;如果当前没有事务,则创建一个新的事务。PROPAGATION_SUPPORTS: 如果当前存在事务,则加入该事务;如果当前没有事务,则以非事务的方式继续运行。PROPAGATION_MANDATORY: 如果当前存在事务,则加入该事务;如果当前没有事务,则抛出异常。(mandatory:强制性)。 不支持当前事务的情况:PROPAGATION_REQUIRES_NEW: 创建一个新的事务,如果当前存在事务,则把当前事务挂起。PROPAGATION_NOT_SUPPORTED: 以非事务方式运行,如果当前存在事务,则把当前事务挂起。PROPAGATION_NEVER: 以非事务方式运行,如果当前存在事务,则抛出异常。 其他情况:PROPAGATION_NESTED: 如果当前存在事务,则创建一个事务作为当前事务的嵌套事务来运行;如果当前没有事务,则该取值等价于PROPAGATION_REQUIRED。 二、SpringMVC篇 什么是Spring MVC ?简单介绍下你对springMVC的理解? Spring MVC是一个基于Java的实现了MVC设计模式的请求驱动类型的轻量级Web框架,通过把Model,View,Controller分离,将web层进行职责解耦,把复杂的web应用分成逻辑清晰的几部分,简化开发,减少出错,方便组内开发人员之间的配合。 Spring MVC的工作原理了解嘛? image.png Springmvc的优点: (1)可以支持各种视图技术,而不仅仅局限于JSP; (2)与Spring框架集成(如IoC容器、AOP等); (3)清晰的角色分配:前端控制器(dispatcherServlet) , 请求到处理器映射(handlerMapping), 处理器适配器(HandlerAdapter), 视图解析器(ViewResolver)。 (4) 支持各种请求资源的映射策略。 Spring MVC的主要组件? (1)前端控制器 DispatcherServlet(不需要程序员开发) 作用:接收请求、响应结果,相当于转发器,有了DispatcherServlet 就减少了其它组件之间的耦合度。 (2)处理器映射器HandlerMapping(不需要程序员开发) 作用:根据请求的URL来查找Handler (3)处理器适配器HandlerAdapter 注意:在编写Handler的时候要按照HandlerAdapter要求的规则去编写,这样适配器HandlerAdapter才可以正确的去执行Handler。 (4)处理器Handler(需要程序员开发) (5)视图解析器 ViewResolver(不需要程序员开发) 作用:进行视图的解析,根据视图逻辑名解析成真正的视图(view) (6)视图View(需要程序员开发jsp) View是一个接口, 它的实现类支持不同的视图类型(jsp,freemarker,pdf等等) springMVC和struts2的区别有哪些? (1)springmvc的入口是一个servlet即前端控制器(DispatchServlet),而struts2入口是一个filter过虑器(StrutsPrepareAndExecuteFilter)。 (2)springmvc是基于方法开发(一个url对应一个方法),请求参数传递到方法的形参,可以设计为单例或多例(建议单例),struts2是基于类开发,传递参数是通过类的属性,只能设计为多例。 (3)Struts采用值栈存储请求和响应的数据,通过OGNL存取数据,springmvc通过参数解析器是将request请求内容解析,并给方法形参赋值,将数据和视图封装成ModelAndView对象,最后又将ModelAndView中的模型数据通过reques域传输到页面。Jsp视图解析器默认使用jstl。 SpringMVC怎么样设定重定向和转发的? (1)转发:在返回值前面加"forward:",譬如"forward:user.do?name=method4" (2)重定向:在返回值前面加"redirect:",譬如"redirect:http://www.baidu.com" SpringMvc怎么和AJAX相互调用的? 通过Jackson框架就可以把Java里面的对象直接转化成Js可以识别的Json对象。具体步骤如下 : (1)加入Jackson.jar (2)在配置文件中配置json的映射 (3)在接受Ajax方法里面可以直接返回Object,List等,但方法前面要加上@ResponseBody注解。 如何解决POST请求中文乱码问题,GET的又如何处理呢? (1)解决post请求乱码问题: 在web.xml中配置一个CharacterEncodingFilter过滤器,设置成utf-8; <filter> <filter-name>CharacterEncodingFilter</filter-name> <filter-class>org.springframework.web.filter.CharacterEncodingFilter</filter-class> <init-param> <param-name>encoding</param-name> <param-value>utf-8</param-value> </init-param> </filter> <filter-mapping> <filter-name>CharacterEncodingFilter</filter-name> <url-pattern>/*</url-pattern> </filter-mapping> (2)get请求中文参数出现乱码解决方法有两个: ①修改tomcat配置文件添加编码与工程编码一致,如下: <ConnectorURIEncoding="utf-8" connectionTimeout="20000" port="8080" protocol="HTTP/1.1" redirectPort="8443"/> ②另外一种方法对参数进行重新编码: String userName = new String(request.getParamter("userName").getBytes("ISO8859-1"),"utf-8") ISO8859-1是tomcat默认编码,需要将tomcat编码后的内容按utf-8编码。 Spring MVC的异常处理 ? 统一异常处理: Spring MVC处理异常有3种方式: (1)使用Spring MVC提供的简单异常处理器SimpleMappingExceptionResolver; (2)实现Spring的异常处理接口HandlerExceptionResolver 自定义自己的异常处理器; (3)使用@ExceptionHandler注解实现异常处理; 统一异常处理的博客:https://blog.csdn.net/ctwy291314/article/details/81983103 SpringMVC的控制器是不是单例模式,如果是,有什么问题,怎么解决? 是单例模式,所以在多线程访问的时候有线程安全问题,不要用同步,会影响性能的,解决方案是在控制器里面不能写成员变量。(此题目类似于上面Spring 中 第5题 有两种解决方案) SpringMVC常用的注解有哪些? @RequestMapping:用于处理请求 url 映射的注解,可用于类或方法上。用于类上,则表示类中的所有响应请求的方法都是以该地址作为父路径。 @RequestBody:注解实现接收http请求的json数据,将json转换为java对象。 @ResponseBody:注解实现将conreoller方法返回对象转化为json对象响应给客户。 SpingMvc中的控制器的注解一般用那个,有没有别的注解可以替代? 一般用@Controller注解,也可以使用@RestController,@RestController注解相当于@ResponseBody + @Controller,表示是表现层,除此之外,一般不用别的注解代替。 如果在拦截请求中,我想拦截get方式提交的方法,怎么配置? 可以在@RequestMapping注解里面加上method=RequestMethod.GET。 怎样在方法里面得到Request,或者Session? 直接在方法的形参中声明request,SpringMVC就自动把request对象传入。 如果想在拦截的方法里面得到从前台传入的参数,怎么得到? 直接在形参里面声明这个参数就可以,但必须名字和传过来的参数一样。 如果前台有很多个参数传入,并且这些参数都是一个对象的,那么怎么样快速得到这个对象? 直接在方法中声明这个对象,SpringMVC就自动会把属性赋值到这个对象里面。 SpringMVC中函数的返回值是什么? 返回值可以有很多类型,有String, ModelAndView。ModelAndView类把视图和数据都合并的一起的。 SpringMVC用什么对象从后台向前台传递数据的? 通过ModelMap对象,可以在这个对象里面调用put方法,把对象加到里面,前台就可以拿到数据。 怎么样把ModelMap里面的数据放入Session里面? 可以在类上面加上@SessionAttributes注解,里面包含的字符串就是要放入session里面的key。 SpringMvc里面拦截器是怎么写的: 有两种写法,一种是实现HandlerInterceptor接口,另外一种是继承适配器类,接着在接口方法当中,实现处理逻辑;然后在SpringMvc的配置文件中配置拦截器即可: <!-- 配置SpringMvc的拦截器 --> <mvc:interceptors> <!-- 配置一个拦截器的Bean就可以了 默认是对所有请求都拦截 --> <bean id="myInterceptor" class="com.zwp.action.MyHandlerInterceptor"></bean> <!-- 只针对部分请求拦截 --> <mvc:interceptor> <mvc:mapping path="/modelMap.do" /> <bean class="com.zwp.action.MyHandlerInterceptorAdapter" /> </mvc:interceptor> </mvc:interceptors> 注解原理: 注解本质是一个继承了Annotation的特殊接口,其具体实现类是Java运行时生成的动态代理类。我们通过反射获取注解时,返回的是Java运行时生成的动态代理对象。通过代理对象调用自定义注解的方法,会最终调用AnnotationInvocationHandler的invoke方法。该方法会从memberValues这个Map中索引出对应的值。而memberValues的来源是Java常量池 三、Mybatis篇 什么是MyBatis? MyBatis是一个可以自定义SQL、存储过程和高级映射的持久层框架。 讲下MyBatis的缓存 MyBatis的缓存分为一级缓存和二级缓存,一级缓存放在session里面,默认就有, 二级缓存放在它的命名空间里,默认是不打开的,使用二级缓存属性类需要实现Serializable序列化接口, 可在它的映射文件中配置<cache/> Mybatis是如何进行分页的?分页插件的原理是什么? 1)Mybatis使用RowBounds对象进行分页,也可以直接编写sql实现分页,也可以使用Mybatis的分页插件。 2)分页插件的原理:实现Mybatis提供的接口,实现自定义插件,在插件的拦截方法内拦截待执行的sql,然后重写sql。 举例:select * from student,拦截sql后重写为:select t.* from (select * from student)t limit 0,10 简述Mybatis的插件运行原理,以及如何编写一个插件? 1)Mybatis仅可以编写针对ParameterHandler、ResultSetHandler、StatementHandler、 Executor这4种接口的插件,Mybatis通过动态代理, 为需要拦截的接口生成代理对象以实现接口方法拦截功能, 每当执行这4种接口对象的方法时,就会进入拦截方法, 具体就是InvocationHandler的invoke方法,当然, 只会拦截那些你指定需要拦截的方法。 2)实现Mybatis的Interceptor接口并复写intercept方法, 然后在给插件编写注解,指定要拦截哪一个接口的哪些方法即可, 记住,别忘了在配置文件中配置你编写的插件。 Mybatis动态sql是做什么的?都有哪些动态sql?能简述一下动态sql的执行原理不? 1)Mybatis动态sql可以让我们在Xml映射文件内, 以标签的形式编写动态sql,完成逻辑判断和动态拼接sql的功能。 2)Mybatis提供了9种动态sql标签:trim|where|set|foreach|if|choose|when|otherwise|bind。 3)其执行原理为,使用OGNL从sql参数对象中计算表达式的值, 根据表达式的值动态拼接sql,以此来完成动态sql的功能。 #{}和${}的区别是什么? 1)#{}是预编译处理,${}是字符串替换。 2)Mybatis在处理#{}时,会将sql中的#{}替换为?号,调用PreparedStatement的set方法来赋值(有效的防止SQL注入); 3)Mybatis在处理${}时,就是把${}替换成变量的值。 为什么说Mybatis是半自动ORM映射工具?它与全自动的区别在哪里? Hibernate属于全自动ORM映射工具, 使用Hibernate查询关联对象或者关联集合对象时, 可以根据对象关系模型直接获取,所以它是全自动的。 而Mybatis在查询关联对象或关联集合对象时, 需要手动编写sql来完成,所以,称之为半自动ORM映射工具。 Mybatis是否支持延迟加载?如果支持,它的实现原理是什么? 1)Mybatis仅支持association关联对象和collection关联集合对象的延迟加载, association指的就是一对一,collection指的就是一对多查询。 在Mybatis配置文件中, 可以配置是否启用延迟加载lazyLoadingEnabled=true|false。 2)它的原理是,使用CGLIB创建目标对象的代理对象, 当调用目标方法时,进入拦截器方法, 比如调用a.getB.getName, 拦截器invoke方法发现a.getB是null值, 那么就会单独发送事先保存好的查询关联B对象的sql, 把B查询上来,然后调用a.setB(b), 于是a的对象b属性就有值了, 接着完成a.getB.getName方法的调用。 这就是延迟加载的基本原理。 MyBatis与Hibernate有哪些不同? 1)Mybatis和hibernate不同,它不完全是一个ORM框架, 因为MyBatis需要程序员自己编写Sql语句, 不过mybatis可以通过XML或注解方式灵活配置要运行的sql语句, 并将java对象和sql语句映射生成最终执行的sql, 最后将sql执行的结果再映射生成java对象。 2)Mybatis学习门槛低,简单易学,程序员直接编写原生态sql, 可严格控制sql执行性能,灵活度高,非常适合对关系数据模型要求不高的软件开发, 例如互联网软件、企业运营类软件等,因为这类软件需求变化频繁, 一但需求变化要求成果输出迅速。但是灵活的前提是mybatis无法做到数据库无关性, 如果需要实现支持多种数据库的软件则需要自定义多套sql映射文件,工作量大。 3)Hibernate对象/关系映射能力强,数据库无关性好, 对于关系模型要求高的软件(例如需求固定的定制化软件) 如果用hibernate开发可以节省很多代码,提高效率。 但是Hibernate的缺点是学习门槛高,要精通门槛更高, 而且怎么设计O/R映射,在性能和对象模型之间如何权衡, 以及怎样用好Hibernate需要具有很强的经验和能力才行。 总之,按照用户的需求在有限的资源环境下只要能做出维护性、 扩展性良好的软件架构都是好架构,所以框架只有适合才是最好。 MyBatis的好处是什么? 1)MyBatis把sql语句从Java源程序中独立出来,放在单独的XML文件中编写, 给程序的维护带来了很大便利。 2)MyBatis封装了底层JDBC API的调用细节,并能自动将结果集转换成Java Bean对象, 大大简化了Java数据库编程的重复工作。 3)因为MyBatis需要程序员自己去编写sql语句, 程序员可以结合数据库自身的特点灵活控制sql语句, 因此能够实现比Hibernate等全自动orm框架更高的查询效率,能够完成复杂查询。 简述Mybatis的Xml映射文件和Mybatis内部数据结构之间的映射关系? Mybatis将所有Xml配置信息都封装到All-In-One重量级对象Configuration内部。 在Xml映射文件中,<parameterMap>标签会被解析为ParameterMap对象, 其每个子元素会被解析为ParameterMapping对象。 <resultMap>标签会被解析为ResultMap对象, 其每个子元素会被解析为ResultMapping对象。 每一个<select>、<insert>、<update>、<delete> 标签均会被解析为MappedStatement对象, 标签内的sql会被解析为BoundSql对象。 什么是MyBatis的接口绑定,有什么好处? 接口映射就是在MyBatis中任意定义接口,然后把接口里面的方法和SQL语句绑定, 我们直接调用接口方法就可以,这样比起原来了SqlSession提供的方法我们可以有更加灵活的选择和设置. 接口绑定有几种实现方式,分别是怎么实现的? 接口绑定有两种实现方式,一种是通过注解绑定,就是在接口的方法上面加 上@Select@Update等注解里面包含Sql语句来绑定, 另外一种就是通过xml里面写SQL来绑定,在这种情况下, 要指定xml映射文件里面的namespace必须为接口的全路径名. 什么情况下用注解绑定,什么情况下用xml绑定? 当Sql语句比较简单时候,用注解绑定;当SQL语句比较复杂时候,用xml绑定,一般用xml绑定的比较多 MyBatis实现一对一有几种方式?具体怎么操作的? 有联合查询和嵌套查询,联合查询是几个表联合查询,只查询一次, 通过在resultMap里面配置association节点配置一对一的类就可以完成; 嵌套查询是先查一个表,根据这个表里面的结果的外键id, 去再另外一个表里面查询数据,也是通过association配置, 但另外一个表的查询通过select属性配置。 Mybatis能执行一对一、一对多的关联查询吗?都有哪些实现方式,以及它们之间的区别? 能,Mybatis不仅可以执行一对一、一对多的关联查询, 还可以执行多对一,多对多的关联查询,多对一查询, 其实就是一对一查询,只需要把selectOne修改为selectList即可; 多对多查询,其实就是一对多查询,只需要把selectOne修改为selectList即可。 关联对象查询,有两种实现方式,一种是单独发送一个sql去查询关联对象, 赋给主对象,然后返回主对象。另一种是使用嵌套查询,嵌套查询的含义为使用join查询, 一部分列是A对象的属性值,另外一部分列是关联对象B的属性值, 好处是只发一个sql查询,就可以把主对象和其关联对象查出来。 MyBatis里面的动态Sql是怎么设定的?用什么语法? MyBatis里面的动态Sql一般是通过if节点来实现,通过OGNL语法来实现, 但是如果要写的完整,必须配合where,trim节点,where节点是判断包含节点有 内容就插入where,否则不插入,trim节点是用来判断如果动态语句是以and 或or 开始,那么会自动把这个and或者or取掉。 Mybatis是如何将sql执行结果封装为目标对象并返回的?都有哪些映射形式? 第一种是使用<resultMap>标签,逐一定义列名和对象属性名之间的映射关系。 第二种是使用sql列的别名功能,将列别名书写为对象属性名, 比如T_NAME AS NAME,对象属性名一般是name,小写, 但是列名不区分大小写,Mybatis会忽略列名大小写,
-
数据结构 - 堆(Heap)原理介绍和 Java 代码的完整实现