Java工程师修炼手册：Java数据结构面试题

Java数据结构面试题一直都是面试官喜欢问到的问题，在我们去面试Java的相关岗位时，肯定会被提问到，所以我们就需要提前做好准备，轻松的去应对：

1. 数据结构定义

数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。

• 数组：物理存储单元上连续、顺序的存储结构
• 链表：链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
• 队列：队列(queue)是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。
• 栈：栈(stack)又名堆栈，它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。
• 堆：堆通常是一个可以被看做一棵完全二叉树的数组对象。将根结点最大的堆叫做最大堆或大根堆，根结点最小的堆叫做最小堆或小根堆。建堆时间复杂度O(n)，堆总是满足下列性质：堆总是一棵完全二叉树;堆中某个结点的值总是不大于或不小于其父结点的值;
• 散列表：(Hash table，也叫哈希表)，是根据关键码值(Key value)而直接进行访问的数据结构

2. 堆的创建、插入、删除、堆排序

• 堆的插入：在已经建成的最小堆的后面插入元素，堆的结构可能被破坏，再向上调整使其满足性质。
• 堆的删除：删除时每次删除堆顶元素，删除方法：

1. 将堆中最后一个元素代替堆顶元素。
2. 将堆中元素个数减少一个，相当于将堆中最后一个元素删除。
3. 此时堆的结构可能被破坏，在向下调整使其满足性质。

• 堆排序：

1. 将堆顶元素与第size-1个元素交换。
2. hp->size–
3. 将其余的元素调整为最小堆
4. 重复1、2、3步hp->size-1次。

3.布隆过滤器

bloom算法类似一个位图，用来判断某个元素(key)是否在某个集合中。和一般的位图不同的是，这个算法无需存储key的值，对于每个key，只需要k个比特位，每个存储一个标志，用来判断key是否在集合中。

• 应用场景：比如网络爬虫抓取时url去重，邮件提供商反垃圾黑名单Email地址去重，之所以需要k个比特位是因为我们大多数情况下处理的是字符串，那么不同的字符串就有可能映射到同一个位置，产生冲突。
• 优点：不需要存储key，节省空间
• 缺点：算法判断key在集合中时，有一定的概率key其实不在集合中，已经映射的数据无法删除

4. (Tire)字典树

• 定义：又称单词查找树，Trie树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串(但不仅限于字符串)，所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。
• 3个基本性质：

1. 根节点不包含字符，除根节点外每一个节点都只包含一个字符;
2. 从根节点到某一节点路径上经过的字符连接起来，为该节点对应的字符串;
3. 每个节点的所有子节点包含的字符都不相同。

5. 海量数据找出前K大的数

top K类问题，通常比较好的方案是分治+Trie树/hash+小顶堆(就是上面提到的最小堆)，即先将数据集按照Hash方法分解成多个小数据集，然后使用Trie树活着Hash统计每个小数据集中的query词频，之后用小顶堆求出每个数据集中出现频率最高的前K个数，最后在所有top K中求出最终的top K。

以上就是“Java工程师修炼手册：Java数据结构面试题”，你能回答上来吗?如果想要了解更多的相关内容，可以关注极悦Java官网。