数据结构复习

逻辑结构：分为了四种结构

集合结构：同一个集合相互关系外，别无其他关系

线性结构：一对一的相互关系

树形结构：一对多的关系

图形结构：多对多的相互关系

2.物理分类    逻辑结构以什么方式放到内存或磁盘

顺序存储结构：数组

链接存储结构：链表

数据索引存储结构：es和mysql

数据散列存储结构 ：也叫hash存储，通过hash函数计算位置存储，hashmap典型案例

2.java常见的数据结构

集合结构

HashMap-->linkedHashMap (有序) TreeMap(排序)

HashSet-->linkedHashSet (有序) TreeSet(排序)

线性结构：数组，栈（先进后出），队列（先进先出），这三个都有顺序结构和链表结构形态，串，一对一的逻辑关系，比如String StringBuilder StringBuffer

这里又牵扯到String StringBuilder StringBuffer这三个之间的关系

树状结构：

二叉树，

二叉查找树：比它小左边，比它大右边。如果插入的数据老是比已有数据大，那么二叉树的子树会向一遍倾斜，那么树的层次就会深，甚至形成链表结构

平衡二叉树：在二叉查找树进行了优化，进行了平衡度计算，但是每次插入删除会进行大量平衡度计算，插入比较耗时，所以又出现了红黑树。

红黑树：红黑树也是一种自平衡二叉树，在平衡二叉树的基础上每个节点又增加了一个颜色的属性，节点的颜色只能是红色或黑色。它进行插入，则是用左旋 右旋，变色，效率还可以。在任何一棵子树中，从根节点向下走到空节点的路径上所经过的黑节点的数目相同，从而保证了是一个平衡二叉树。

红黑树对比平衡二叉树：

avl树查的比较快，插入慢。红黑树，查的较慢，因为多一次比较，插入和删除优与avl树，，AVL树每次插入删除会进行大量的平衡度计算，而红黑树为了维持红黑性质所做的红黑变换和旋转的开销，相较于AVL树为了维持平衡的开销要小得多。

综合下来，红黑树优秀于avl树

多叉树：b树，b+树

图形结构：这个一般是关系

常见算法：

hash算法，散列算法，Hash函数：H(key) = key Mod len ； 解释为：hash值%Hash表长度 = 数组下标

hash冲突解决方案

排序：

数组排序

集合排序

对象集合排序：要实现Comparable

排序算法：

• 选择排序：1.2 选择排序 | 菜鸟教程

• 插入排序：插入排序 | 菜鸟教程

• 快速排序：快速排序---(面试碰到过好几次)-CSDN博客

• 希尔排序：https://www.cnblogs.com/chengxiao/p/6104371.html

• 冒泡排序：1.1 冒泡排序 | 菜鸟教程

查找：

• 顺序查找

• 二分查找--排序后数据

• 插值查找

• 斐波那契查找

• 树表查找

• 分块查找

• 哈希查找