常问的数据结构与算法

高频面经汇总：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)