常问的数据结构与算法

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

 

 

上一篇:HashMap原理及面试高频问题


下一篇:AVL树介绍和各操作实现图文详解