一、什么是堆

我们日常生活中经常见到各种堆，比如冬天的雪堆，施工的土堆，都是下面大，上面尖顶的样子，那么数据结构中的堆与日常生活中的堆有哪些异同呢？

1.堆的性质

• 堆是一个完全二叉树(除了最后一层，其他层从左到右的节点都是满的)
• 堆中的节点，都大于等于或小于等于其子节点
• 堆通常使用数组来存储

2.堆的分类

• 大顶堆
  • 所有节点大于或等于其子节点

• 小顶堆
  • 所有节点大于或小于其子节点

二、通过数组实

HashMap是一种以key-value键值对为节点的数据集合

一、HashMap的使用

1.HashMap与其他集合数据结构的关系

(1)HashMap与其他集合的继承关系

(2)HashMap所包含的方法

2.HashMap遍历元素的方式

(1)通过遍历表的所有key，再通过key来获取值

• 适合场景：只需要获取表的key的情况

Map<Integer, String> userMap =

一、散列

散列是为了解决快速插入和快速查找的功能，它是基于数组+链表来实现的

1.散列结构

• 散列的节点：实际存储的节点
• 散列函数：hash函数，它通过一定的算法将所存储节点的key转化为一个整数，我们可以根据这个计算出来的整数值来确定它应该存储到散列表的什么位置
• 散列表：用于存放一系列散列节点的表

注：我们通过key计算出其hashCode值，但不同的key可能其hashCode值相同，这就是所谓的h

一、二叉树到多叉树

1.二叉树的劣势

• 二叉树每个节点至多只有两个子节点，如果整个数据比较大，那么我们的树的深度(高度)将非常大，无论对于插入或者删除，速度将会变得比较缓慢

2.多叉树(多路搜索树)

注：多叉树并不是专业的叫法，这里只是为了更好的理解

M阶多路搜索树

• 每个节点至多M个子节点

二、B树和B+树

1.B树即B-tree

注：这里的B是Balance

(1)B树的性质

B树又叫多路平衡查找树，其

一、红黑树说明

1.红黑树的结构

红黑树是一种特殊的二叉树，它有以下性质：

• 每一个节点或着成红色，或着成红色
• 根是黑色的
• 如果一个节点是红色的，那么它的子节点必须是黑色的(如果这个节点是叶子节点，即没有子节点，不需要满足这个条件，这是在有子节点的情况下)
• 从根节点到叶子节点的每一条路径必须包含相同数目的黑色节点

2.将普通二叉树变成红黑树

• 将节点着色或改变颜色
• 将节点进行旋转操作

二、TreeMap的使用