各种乱七八糟的结构都是为了在「特定场景」下尽可能高效地进行增删查改

哈希表（hash table 散列表）

哈希冲突解决办法

拉链法（链地址法）

将所有哈希地址相同的记录都链接在同一链表中。

开放寻址法（开放定址法、开地址法）

从发生冲突的那个单元起，按照一定的次序，从哈希表中找到一个空闲的单元。然后把发生冲突的元素存入到该单元的一种方法。开放定址法需要的表长度要大于等于所需要存放的元素。

线性探查法

线行探查法是开放定址法中最简单的冲突处理方法，它从发生冲突的单元起，依次判断下一个单元是否为空，当达到最后一个单元时，再从表首依次判断。直到碰到空闲的单元或者探查完全部单元为止。

平方探查法

平方探查法即是发生冲突时，用发生冲突的单元 d[i], 加上（或减去） 1²、 2² 等。即 d[i] + 1²，d[i] + 2², d[i] + 3²… 直到找到空闲单元。

伪随机探查法

具体实现时，建立一个伪随机数发生器来生成探查序列
例如，假设哈希表长度 m=11，哈希函数为：H(key)= key % 11，则 H(47)=3，H(26)=4，H(60)=5，假设下一个关键字为 69，则H(69)=3，与 47 冲突。如果用伪随机探测再散列处理冲突，且伪随机数序列为：2，5，9，…，则下一个哈希地址为 H1=(3+2)%11=5，仍然冲突，再找下一个哈希地址为 H2=(3+5)%11=8，此时不再冲突，将 69 填入 8 号单元。

再哈希法（二次哈希法）

当通过哈希函数求得的哈希地址同其他关键字产生冲突时，使用另一个哈希函数计算，直到冲突不再发生。

建立公共溢出区

将发生冲突的元素放到一个公共的溢出区

常用的哈希函数的构造方法有 6 种：直接定址法、数字分析法、平方取中法、折叠法、除留余数法和随机数法。

直接定址法：其哈希函数为一次函数，即以下两种形式：
H（key）= key 或者 H（key）=a * key + b
其中 H（key）表示关键字为 key 对应的哈希地址，a 和 b 都为常数


平方取中法是对关键字做平方操作，取中间得几位作为哈希地址。此方法也是比较常用的构造哈希函数的方法。

例如关键字序列为{421，423，436}，对各个关键字进行平方后的结果为{177241，178929，190096}，则可以取中间的两位{72，89，00}作为其哈希地址。

折叠法是将关键字分割成位数相同的几部分（最后一部分的位数可以不同），然后取这几部分的叠加和（舍去进位）作为哈希地址。此方法适合关键字位数较多的情况。

除留余数法：若已知整个哈希表的最大长度 m，可以取一个不大于 m 的数 p，然后对该关键字 key 做取余运算，即：H（key）= key % p。

随机数法：是取关键字的一个随机函数值作为它的哈希地址，即：H（key）=random（key），此方法适用于关键字长度不等的情况。

树

  • 树节点的度数：该节点孩子的个数。

  • 树的度指其中节点的度最大值

    二叉树

    image.png
    image.png

    二叉搜索树(二叉查找树，二叉排序树Binary Search Tree)

    1、对于 BST 的每一个节点 node，左子树节点的值都比 node 的值要小，右子树节点的值都比 node 的值大。
    2、对于 BST 的每一个节点 node，它的左侧子树和右侧子树都是 BST。

  • BST 的中序遍历结果是有序的（升序）

  • 劣势是最差情况下，会变成一条单链表。平衡度低

    平衡二叉树(AVL树)

    是一种特殊的二叉排序树，其左右子树也是平衡二叉树
    且左右子树高度之差的绝对值不超过1

    红黑树

    一种特殊的二叉查找树，是一种弱平衡树，相对于严格的avl来说旋转次数少，对于搜索插入删除较多时，通常用红黑树
    插入最多两次旋转，删除最多三次旋转，查找插入性能都是logn比较稳定
    通过对任何一条根到叶子的路径上各个节点着色方式的限制，确保没有一条路径会比其他路径长出两倍

每个节点增加了一个存储位表示节点的颜色
每个节点非红即黑
根节点是黑的
每个叶节点是黑的
如果一个节点是红色，则它的子节点必须是黑色
对于任意节点而言，其到叶子点树NULL指针的每条路径都有相同数目的黑节点

B树 B+树区别

  • b+树叶子节点是有指针的，b树没有
  • b+树叶子节点中存了所有元素，并且排好序

  • b+树非叶子节点只有key，数据在叶子节点上，b树keyvalue在一起

    Trie树(字典树、前缀树、单词查找树）

    多叉树，主要应用场景是处理字符串前缀相关的操作

  • 用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补完和拼写检查、前缀匹配，词频统计

  • TrieMap的键必须是字符串类型，值的类型V可以随意
  • 但是和之前的普通多叉树节点不同，TrieNode中children数组的索引是有意义的，代表键中的一个字符。
  • 这里要特别注意，TrieNode节点本身只存储val字段，并没有一个字段来存储字符，字符是通过子节点在父节点的children数组中的索引确定的
  • 插入、搜索、前缀都是O（k) k：字符串长度

形象理解就是，Trie 树用「树枝」存储字符串（键），用「节点」存储字符串（键）对应的数据（值）。所以我在图中把字符标在树枝，键对应的值val标在节点上：

  1. class Trie {
  2.     private:
  3.     vector<Trie*> children;
  4.     bool isEnd;
  6.     Trie* searchPrefix(string prefix) {
  7.         Trie* node = this;
  8.         for (char ch: prefix) {
  9.             ch -= 'a';
  10.             if (node->children[ch] == nullptr) {
  11.                 return nullptr;
  12.             }
  13.             node = node->children[ch];
  14.         }
  15.         return node;
  16.     }
  17.     public:
  18.     Trie() {
  19.         children.resize(26, nullptr);
  20.         isEnd = false;
  21.     }
  23.     void insert(string word) {
  24.         Trie* node = this;
  25.         for (char ch: word) {
  26.             ch -= 'a';
  27.             if (node->children[ch] == nullptr) {
  28.                 node->children[ch] = new Trie();
  29.             }
  30.             node = node->children[ch];
  31.         }
  32.         node->isEnd = true;
  33.     }
  35.     bool search(string word) {
  36.         Trie* node = this->searchPrefix(word);
  37.         return node != nullptr && node->isEnd;
  38.     }
  40.     bool startsWith(string prefix) {
  41.         return this->searchPrefix(prefix) != nullptr;
  42.     }
  43. };

数组

  • 支持随机读写，可以根据索引访问
  • 插入删除效率低

  • 地址连续，固定空间，需要提前分配好空间大小

    链表

  • 不支持随机读写

  • 插入删除效率高，读写效率差

  • 地址不一定连续

    栈

  • 先进后出

    最小栈

    ```cpp class MinStack { public: stack x_stk; stack min_stk;

    /* initialize your data structure here. / MinStack() {

    1.   min_stk.push(INT_MAX);

    }

    void push(int x) {

    1.   x_stk.push(x);
    2.   if (x < min_stk.top()) {
    3.       min_stk.push(x);
    4.   } else {
    5.       min_stk.push(min_stk.top());
    6.   }

    }

    void pop() {

    1.   x_stk.pop();
    2.   min_stk.pop();

    }

    int top() {

    1.   return x_stk.top();

    }

    int min() {

    1.   return min_stk.top();

    } };

/**

  • Your MinStack object will be instantiated and called as such:
  • MinStack* obj = new MinStack();
  • obj->push(x);
  • obj->pop();
  • int param_3 = obj->top();
  • int param_4 = obj->min(); */ ```

    队列

  • 先进先出

    堆

    通常是一个可以被看做一棵树的数组对象
    堆中某个结点的值总是不大于或不小于其父结点的值
    堆总是一棵完全二叉树