- 数组(Array)是一种线性表数据结构。它用一组连续的内存空间，来存储一组具有相同类型的数据
- 数组支持随机访问，根据
下标随机访问的时间复杂度为O(1) - 数组的缺点是大小固定，一经声明就要占用整块连续内存空间
- 通过散列函数把元素的键值映射为下标，然后将数据存储在数组中对应下标的位置。当按照键值查询元素时，用同样的散列函数，将键值转化数组下标，从对应的数组下标的位置取数据
装载因子越大，说明空闲位置越少，冲突越多，散列表的性能会下降- 常用的散列冲突解决方法有两类，开放寻址法(open addressing)和链表法(chaining)
- 将链表法中的链表改造为其他高效的动态数据结构，比如跳表、红黑树。极端情况下，所有的数据都散列到同一个桶内，那最终退化成的散列表的查找时间也只不过是 O(logn)。这样也就有效避免了散列碰撞攻击
- 针对散列表，当装载因子过大时，可以进行动态扩容，重新申请一个更大的散列表，将数据搬移到这个新散列表中。为了解决一次性扩容耗时过多的情况，可以将扩容操作穿插在插入操作的过程中，分批完成
- 链表通过指针将一组零散的内存块串联在一起
- 在链表中插入或者删除一个数据，并不需要为了保持内存的连续性而搬移结点，因为链表的存储空间本身就不是连续的。所以，在链表中插入和删除一个数据是非常快速的
- 链表加多级索引的结构，就是跳表
- 在跳表中查询任意数据的时间复杂度就是 O(logn)。查找的时间复杂度跟 N 分查找是一样的，其实是基于单链表实现了 N 分查找
- 跳表插入、删除操作的时间复杂度也是 O(logn)
- 对于按照区间查找数据这个操作，跳表可以做到 O(logn)的时间复杂度定位区间的起点，然后在原始链表中顺序往后遍历就可以了
- 从栈的操作特性上来看，栈是一种
操作受限的线性表，只允许在一端插入和删除数据 - 用数组实现的栈，叫作顺序栈，用链表实现的栈，叫作链式栈
- 操作系统给每个线程分配了一块独立的内存空间，这块内存被组织成
栈这种结构, 用来存储函数调用时的临时变量。每进入一个函数，就会将临时变量作为一个栈帧入栈，当被调用函数执行完成，返回之后，将这个函数对应的栈帧出栈
- 先进者先出，这就是典型的
队列 - 队列也是一种操作受限的线性表数据结构
- 用数组实现的队列叫作顺序队列，用链表实现的队列叫作链式队列
- 红黑树是一种平衡二叉查找树。为了解决普通二叉查找树在数据更新的过程中，复杂度退化的问题而产生的。红黑树的高度近似 log2n，所以是近似平衡，插入、删除、查找操作的时间复杂度都是 O(logn)
- 红黑树是一种性能非常稳定的二叉查找树
- 堆是一个完全二叉树
- 堆中每一个节点的值都必须大于等于(或小于等于)其子树中每个节点的值。堆顶元素存储的就是堆中数据的最大值或者最小值
- 用数组来存储完全二叉树是非常节省存储空间的。不需要存储左右子节点的指针，单纯地通过数组的下标，就可以找到一个节点的左右子节点和父节点