数据结构有哪几种分类

按照逻辑结构分

  • 集合：没有相互关系的一堆数据
  • 线性结构：元素存在一对一的相互关系
  • 树形结构：元素存在一对多的相互关系
  • 图形结构：元素存在多对多的相互关系

按照物理结构分

  • 顺序存储结构：用一组地址连续的存储空间依次存储线性表的数据元素，也叫顺序存储结构，比如数组
  • 链接存储结构：用一组任意的存储空间来存储线性表中的数据元素，不要求相邻元素在物理位置上也相邻，比如链表
  • 数据索引存储结构：建立附加的索引来标识节点的地址，通过索引，可以很快检索数据
  • 数据散列存储结构：将数据元素的存储位置与关键字之间建立确定的对应关系，加快查找的速度，又叫hash存储

数组和链表在内存中的存储结构有什么区别

数组在内存中是一组连续的存储空间，它随机存取元素性能很高，但是插入和删除操作，需要移动其他元素，因此性能很低

链表在内存中的存储空间可以是不连续的，而在每一个元素中都保存相邻节点的指针，因此它的存储密度相对较小，查找的性能低，因为需要从第一个元素依次遍历，但是它的插入和删除操作性能很高，因为它不需要移动节点，只需要改变相邻节点指针就行了，同时它更容易造成内存的碎片化

说一下散列存储(Hash存储) ， 什么是Hash冲突 ， 有什么解决方案

散列存储，它通过把关键码的值映射到表中的一个位置，来提高查询的速度。而这个映射函数叫做散列函数。

哈希冲突，也叫哈希碰撞，指的是两个不同的值，计算出了相同的hash，也就是两个不同的数据计算出同一个下标，通常解决方案有：

  • 拉链法，把哈希碰撞的元素指向一个链表
  • 开放寻址法，把产生冲突的哈希值作为值，再进行哈希运算，直到不冲突
  • 再散列法，就是换一种哈希算法重来一次
  • 建立公共溢出区，把哈希表分为基本表和溢出表，将产生哈希冲突的元素移到溢出表

说说 数组，链表，循环，嵌套循环的时间复杂度

时间复杂度是用来度量算法执行的时间长短，通常我们用Ｏ(f(n))渐进时间复杂度来衡量，比如说

  • 要在 hash 表中找到一个元素就是 O(1)
  • 要在无序数组中找到一个元素就是 O(n)
  • 访问数组的第 n 个元素是 O(1)
  • 二分搜索的时间复杂度最好的情况是 O(1)，最坏情况（平均情况）下 O(log n)
  • 访问链表的第 n 个元素是 O(n)
  • 一个For循环是O(n)
  • 两个For循环嵌套是O(n2)
  • 三个Foreach嵌套是O(n3)

JDK中线性结构的集合有哪些

数组：按照顺序物理结构存储，ArrayList

链表：按照链式物理结构存储，LinkedList

栈：LIFO后进先出的线性存储结构，分为用数组实现的顺序栈，用链表实现的链栈

队列：FIFO先进先出的线性存储结构，分为顺序队列和链式队列

串：特殊的线性存储结构，String，StringBuffer，StringBuilder

你说一下树形结构对比线性结构的优势

线性结构，对于大量的输入数据，访问时间很长，效率很低，树形结构的优势在于它查找数据性能很高

说一下树的分类，以及你对它们的理解

树有二叉树，多叉树，他们特点如下

  • 二叉树：树中任意节点最多只有两个分叉的树，它又分为二叉排序树，平衡二叉树，赫夫曼树，红黑树
  • 二叉排序树，它是一个有序的二叉树，优势在于查找插入数据的性能很高，但是可能会出现倾斜而变成数组
  • 平衡二叉树，二叉排序树进化形态，要求任何节点的两颗字数高度差不大于1。它的查询性能很高，但是每次增删元素，会重排序导致性能低
  • 红黑树，自平衡二叉树，要求根节点和叶子节点是黑色，其他节点红黑交替，在任何一个子树中，从根节点向下走到空姐点的路径经过的黑节点数相同。从而保证了平衡。它的查询性能比平衡二叉树稍低，插入和删除元素的性能大幅提高。

多叉树：解决二叉树存储大规模数据时，深度过大而导致IO性能低，查询效率低的问题，常见有B树和B+树，字典树，后缀树等等

  • B树，自平衡的树，一个节点可以存储多个key，和拥有key数量+1个分叉，适用于读写相对大的数据块，比如文件系统，数据库索引。因为相对二叉树来说，节点存储key越多，分叉越多，需要的节点越少，树高越矮，IO次数少，查询效率越高。
  • B+树，B树升级版，它的内部节点只存储key，不存储具体数据，叶子节点存放key和具体数据。这就使得每个节点可以存更多的key，树的高度更低，查询更快，同时它每次查询都会到叶子节点，查询速度更稳定。并且所有的叶子节点会组成一个有序链表，方便区间查询

有是二叉树为什么要出现多叉树

因为二叉树在大规模的数据存储中，树会高的没谱，这会导致IO读写过于频繁，查询效率低下

多叉树可以解决这个问题，它每层可以存放更多的数据，因此能大幅度降低树的深度，提高查询性能

B-tree和b+tree的区别

一是节点存储内容上的区别：B树每个节点都可以存放key，存放数据，而B+树所有内部节点只存放key，叶子节点存放key和数据，因此它的节点能存放更多数据，降低树高，查询性能更快

二是B+树所有的叶子节点会构成一个链表结构，方便区间查找和排序

说一下ES用到了什么数据结构

ES是使用了数据索引存储结构，它是通过为关键字建立索引，通过索引找到对应的数据，这种索引也叫倒排索引，可以实现快速检索