SOUSIC

哈库呐玛塔塔

0%

数据结构

发表于 更新于 分类于 Valine：
本文字数： 2.3k 阅读时长 ≈ 2 分钟
数据结构笔记

链表和数组的区别在哪里？

链表和数组都可以叫线性表，数组又叫顺序表，主要区别在于：

  • 存储形式：数组是一块连续的空间，声明时就要确定长度。链表是一块可不连续的动态空间，长度可变，每个结点要保存相邻结点指针。
  • 数据查找：数组的线性查找速度快，查找操作直接使用偏移地址。链表需要按顺序检索结点，效率低。
  • 数据插入或删除：链表可以快速插入和删除结点，而数组则可能需要大量数据移动。
  • 越界问题：链表不存在越界问题，数组有越界问题。

说明：在选择数组或链表数据结构时，一定要根据实际需要进行选择。数组便于查询，链表便于插入删除。数组节省空间但是长度固定，链表虽然变长但是占了更多的存储空间。

hash冲突怎么办

  1. 开放地址法
    • 线性探测
    • 二次探测：左右左右…
    • 伪随机数
  2. 再哈希法
  3. 链地址法
  4. 建立公共溢出区

HashMap扩容机制

HashMap的容量是有限的。当经过多次元素插入的时候，使得HashMap达到一定的饱和度，Key映射位置的几率不断变大。这个时候（扩容因子=0.75），HashMap就需要扩容了，也就是Resize。一般是增加1倍。

扩容因子：数组中元素的个数/数组容量

B树和B+树

B树

B树是一颗多路平衡查找树。

  • 每个节点最多有m-1个关键字（可以存有的键值对）。
  • 根节点最少可以只有1个关键字。
  • 非根节点至少有m/2个关键字。
  • 每个节点中的关键字都按照从小到大的顺序排列，每个关键字的左子树中的所有关键字都小于它，而右子树中的所有关键字都大于它。
  • 所有叶子节点都位于同一层，或者说根节点到每个叶子节点的长度都相同。
  • 每个节点都存有索引和数据，也就是对应的key和value。

所以，根节点的关键字数量范围：1 <= k <= m-1，非根节点的关键字数量范围：m/2 <= k <= m-1。

另外，我们需要注意一个概念，描述一颗B树时需要指定它的阶数，阶数表示了一个节点最多有多少个孩子节点，一般用字母m表示阶数。

B+树

B+树其实和B树是非常相似的。

相同点：

  • 根节点至少一个元素
  • 非根节点元素范围：m/2 <= k <= m-1

不同点：

  • B+树有两种类型的节点：内部结点（也称索引结点）和叶子结点。内部节点就是非叶子节点，内部节点不存储数据，只存储索引，数据都存储在叶子节点。
  • 内部结点中的key都按照从小到大的顺序排列，对于内部结点中的一个key，左树中的所有key都小于它，右子树中的key都大于等于它。叶子结点中的记录也按照key的大小排列。
  • 每个叶子结点都存有相邻叶子结点的指针，叶子结点本身依关键字的大小自小而大顺序链接。
  • 父节点存有右孩子的第一个元素的索引。

B+树相对于B树的优势

可以归结为下面几点：

  • 单一节点存储的元素更多，使得查询的IO次数更少，所以也就使得它更适合做为数据库MySQL的底层数据结构了。
  • 所有的查询都要查找到叶子节点，查询性能是稳定的，而B树，每个节点都可以查找到数据，所以不稳定。
  • 所有的叶子节点形成了一个有序链表，更加便于查找。
  • 叶子结点连起来还可以范围查询。

红黑树

平衡二叉树就是为了解决二叉查找树退化成一颗链表而诞生。

虽然平衡树解决了二叉查找树退化为近似链表的缺点，能够把查找时间控制在 O(logn)，不过却不是最佳的，因为平衡树要求每个节点的左子树和右子树的高度差至多等于1，这个要求实在是太严了，导致每次进行插入/删除节点的时候，几乎都会破坏平衡树的第二个规则，进而我们都需要通过左旋和右旋来进行调整，使之再次成为一颗符合要求的平衡树。

显然，如果在那种插入、删除很频繁的场景中，平衡树需要频繁着进行调整，这会使平衡树的性能大打折扣，为了解决这个问题，于是有了红黑树，红黑树具有如下特点：

  1. 具有二叉查找树的特点；
  2. 根节点是黑色的；
  3. 每个叶子节点都是黑色的空节点（NIL），也就是说，叶子节点不存数据；
  4. 任何相邻的节点都不能同时为红色，也就是说，红色节点是被黑色节点隔开的(但是黑色节点可以相连)；
  5. 每个节点，从该节点到达其可达的叶子节点是所有路径，都包含相同数目的黑色节点。

红黑树和AVL树的区别：

AVL 和 RBT 都是二叉查找树的优化。其性能要远远好于二叉查找树。他们之间都有自己的优势，其应用上也有不同。

  • 结构对比：AVL的结构高度平衡，RBT的结构基本平衡。平衡度AVL > RBT.
  • 查找对比：AVL 查找时间复杂度最好，最坏情况都是O(logN)。RBT 查找时间复杂度最好为O(logN)，最坏情况下比AVL略差。
  • 插入删除对比：
    1. AVL的插入和删除结点很容易造成树结构的不平衡，而RBT的平衡度要求较低。因此在大量数据插入的情况下，RBT需要通过旋转变色操作来重新达到平衡的频度要小于AVL。
    2. 如果需要平衡处理时，RBT比AVL多一种变色操作，而且变色的时间复杂度在O(logN)数量级上。但是由于操作简单，所以在实践中这种变色仍然是非常快速的。
    3. 当插入一个结点都引起了树的不平衡，AVL和RBT都最多需要2次旋转操作。但删除一个结点引起不平衡后，AVL最多需要logN 次旋转操作，而RBT最多只需要3次。因此两者插入一个结点的代价差不多，但删除一个结点的代价RBT要低一些。
    4. AVL和RBT的插入删除代价主要还是消耗在查找待操作的结点上。因此时间复杂度基本上都是与O(logN) 成正比的。

3老鼠确定8瓶子原理

  1. 二分法：每次取一半混合给小鼠喝。但是瓶子太多就不好混合了。
  2. 二进制：每只老鼠代表一位，n只老鼠可以检测2^n个瓶子。