高频面经汇总:https://blog.csdn.net/qq_40262372/article/details/116075528
十三、数据结构与算法
13.1 (2次)哈希表
介绍
一个哈希表包含一个数组,通过特殊的关键码(也就是key)来访问数组中的元素。哈希表的主要思想是通过一个哈希函数, 把关键码映射的位置去寻找存放值的地方 ,读取的时候也是直接通过关键码来找到位置并存进去。
哈希算法
MD4、MD5、SHA-1
MD4算法的一般步骤如下:
1、数据填充。将输入数据填充到数据长度是512位的倍数。具体的填充规则在下文进一步说明。
2、分组处理。将填充后的数据每512位(即64字节)划分为一组,再对每组数据进行处理。
3、处理完成后得到的128位结果即为MD4码。
如何避免哈希冲突
1.开放地址法:
线性探测在散列:放入元素,如果发生冲突,就往后找没有元素的位置
平方探测在散列:如果发生冲突,放到(冲突+1的平方)位置,如果还发生,就放到(冲突-1的平方)的位置;如果还有冲突,就放到(冲突+2平方)的位置,以此类推,如果算出负数,比如-1,那么就是算倒数第一个位置。
2.拉链法:
如果发生冲突,就继续往前一个元素上连接,形成一个链表
3.再哈希
如果发生冲突,在用另一个方法计算hashcode,两次结果值不一样就不会发生hash冲突
4.建立公共溢出区
将哈希表分为基本表和溢出表两个部分,凡是和基本表发生冲突的元素,一律填入溢出表。
应用场景
Hashmap源码
3.2二叉搜索树(BST)与平衡搜索树(AVL)
二叉搜索树要求:1.若它的左子树不空,则左子树所有节点的值小于它的根节点的值
2.若它的右子树不空,则右子树所有节点的值都大于它根节点的值
3.它的左、右子树分别为二叉搜索树。
插入都是插入叶子节点。
删除有三种情况:
1.删除没有子节点的节点
要删除子节点,只需要改变该节点的父节点引用该节点的值,即将其引用改为Null即可。
2.删除有一个子节点的节点。
删除有一个子节点的节点,我们只需要将其父节点原本指向该节点的引用,改为指向该节点的子节点即可。
3.删除有两个节点的节点
找到要删除节点的后继节点
可以直接加一个删除标记。逻辑删除。避免调节元素。
二叉搜索树的缺点,可能链化:
如果能插入的时候自我平衡就不会出现链化了。 所以二叉平衡搜索树(AVL)出现了
AVL的特点:
1.具有二叉查找树的全部特性。
2.每个节点的左子树和右子树的高度差最多等于1
所以AVL树 插入性能不好。 红黑树插入比AVL树好。
AVL的插入:
1.找到平衡因子是2的节点。
2.对这个节点进行红黑树那种左旋右旋。
就算4个全在左边,取右上三个,进行右旋,还是平衡的,这样把小的放在根了(因为插入了一个最小的)
13.3队列的底层数据结构
底层实现:
循环队列:
链队列:
动态数组:
13.4优先队列的数据结构
最大堆、最小堆
首先介绍堆的数据结构:特别的完全二叉树
完全二叉树是指,如果我们去掉最后一层,二叉树是全满;而且一层的叶子节点也是全部靠左的。满足这两个条件才是完全二叉树!
特别在哪里:比如大顶堆的话,父节点比子节点都大;小顶堆,父节点都比子节点都小,每条枝干一路下去都是递减。
更神奇的是:这个完全二叉树是可以用数组来存储的。
比如当前数组的下标为i,那么它左子节点的下标为2*i+1,它的右子节点为2*i+2,它的父节点是(i-1)/2;
堆的插入:
填入末尾9号位置,比如插入105,先和父节点比较,大的交换,一路找父节点,知道小于为止。
堆的删除:
删除肯定把最后一个元素作为替补元素,然后根节点删除后,看子节点操作,子节点一路往上走,最后空了一个位置出来,就把替补元素放入那个空的位置。
13.6双向链表
13.5排序算法
汇总概念
具体请看以下链接:动图+代码解释
十大经典排序算法(动图演示) - 一像素 - 博客园 (cnblogs.com)