数据结构基础知识校招面经整理、热身

1. 红黑树、B+ 树、B 树、二叉搜索树：

  • 二叉搜索树：又称 BST，是为了实现在 O(logn) 时间内完成对有序集合中的元素完成一次查找，而设计的数据结构。
  • B树：二叉搜索树在最坏情况下，如果元素按顺序插入，会失去平衡退化为链表，查找的效率为 O(n)，为了解决这个平衡问题，引入 AVL 树、 B 树。
    B树中的元素会优先填满每层的结点，达到最大值以后分裂，分裂时会调整父节点和其他子节点，实现平衡。同时 B 树的一层可以设定允许容纳多个节点，进一步降低树高。
  • 红黑树： B 树的一个缺点在于其插入、删除节点时的分裂逻辑较为复杂，对大量写操作不友好。为了解决这个问题，引入红黑树。
    红黑树是某棵确定的 2-3 B树的另一种表现形式（或者说，给定一种旋转规则（LL、LR、RR旋转），则一棵红黑树唯一地映射着一棵 2-3 B 树，反之亦然）。其某个红结点与其父节点（一定为黑色）可以视为对应的 2-3 B 树的某一个结点的2个元素。至此，我们将 B 树的结点分裂规则，转化为了红黑树的旋转规则，大大简化了判断逻辑。
  • B+ 树： B 树的另一缺点在于，对应的数据指针遍布于各个结点当中，因此对顺序访问很不友好，并且结点的数据量因为容纳数据指针而增加了，减小了索引的容量和结点数量。为此，引入其变形 B+ 树。
    B+ 树把所有非叶节点都当作索引，而只在叶节点存储对应的数据指针。同时 B+ 树的所有叶节点之间以指针顺序相连，这就大大方便了顺序访问，同时结点更加小巧，同一层能容纳更多结点，树的层高进一步降低，更适合于文件系统。

2. 一般 HashMap 的实现，哈希冲突解决：

需要一个数组，为了方便后续哈希值的求余操作，我们将数组的容量设置为 2 的 n 次幂。我们将哈希值与 数组的 size - 1 作 & 与运算，获得的余数即为数组下标。
需要一个 Hash 算法，保证我们认为相同的对象算出的 Hash 值一定相等，同时 Hash 算法要尽可能简单，算出的 Hash 值在求余后均匀分布，减少后续的哈希冲突。例如 Java 中 的 HashMap 获得了对象的 hashCode 之后，还要进行扰动处理，将 hashCode 的高 16 位与低 16 位异或，获得的结果再进行求余。
需要一个哈希冲突解决方案，常见的有：

  • 链地址法：直接将冲突的元素放在一个链表中
  • 开放地址法：线性探测（键值加1）、再平方探测（键值加 1、4、9…）、伪随机探测（键值加上一个随机数）
  • 建立公共溢出区：存放所有冲突数据
  • 再哈希法：对于冲突值再哈希直至无冲突

3. 海量数据处理：

  • 数据重复比较多，实际关键词个数能够放进内存
    • 考虑直接用 红黑树、哈希表、AVL 树、Trie 字典树统计次数
  • 海量数据放不下（远大于）内存，找出 Top K 个数据
    • 分治，将数据分成若干部分（比如 1000 份），关键词哈希值取模 （例如，%1000） 后，放入这 1000 个桶中存入硬盘，每次取其中一个桶处理
    • 内存常驻一个 最大/最小堆，假设需要得到 Top K 个数据，就建立一个容量为 K 的最小堆，每次调用一个桶，用桶中的元素维护这个堆
    • 遍历桶之后，即可得到结果
    • 整体复杂度为 O(N logK)
  • 字符串去重
    • 重复量大的话，考虑用 Trie 字典树
  • 找出海量整数中不重复数据的个数、找出中位数等
    • 找不重复：将整数域（假设为 32 位，那么最多有 2^32 个不同的整数）划分为 2^k 份，保证每一份区域能够放进内存。对每一份区域，维护一个长度为 32 的 bitmap。对 bitmap 添加元素时，若每一次都命中了 1，则表示重复，否则不重复。（对于精度要求不高的判重，可以考虑将 bitmap 换为布隆过滤器）
    • 找中位数：思路同上，分区间统计数据（可以先只统计高位，高位确定之后区间即确定），当统计的数据总量达到一半时，表明中位数落在这个区间。

n. 题目：