标签：排序 队列 复杂度 链表 查找 key 数据结构
- 评判规则：量化算法执行的操作/执行步骤的数量；
- 最重要的项：时间复杂度表达式中最有意义的项
- 大O记法：O(最重要的一项)
- O(1)表示一个特殊复杂度，含义为某个任务通过有限可数的资源即可完成，于输入数据量n无关；
- 一个顺序结构的代码，时间负责度是O(1)；
- 二分查找法，分而治之的二分策略，时间复杂度为O(logn)；
- 一个简单的for循环或并列两个for循环，时间复杂度是O(n);
- 两个嵌套的for循环，时间复杂度是O(n^2);
- 散列函数：先用H(key)=key MOD7有冲突后解决方法
- Hash冲突
- 将产生冲突的值以链表的形式连接起来，将相同hash值的对象以链表的形式进行存储，当链表过长时转换成红黑树；
- 冲突处理：线性探测法 （向下顺延1个）
- 二次探测法：di=1^2,-1^2,2^2,-2^2 Hi=(H0+di+m)%m
- 双散列法：ReHash(key)=keyMOD11+1 Hi=(H0+i*ReHash(key))%m
- 动态扩容
- HashMap的初始容量是16;
- 扩容阈值是0.75;
- 何时扩容:
- HashMap中存储的数据个数超过数组长度*0.75,就要扩容;
- 如果单个链表的长度超过8,但是数组的长度没有超过64,就扩容;
- 何时树化:
- 单链长度超过8,数组长度超过64(包含)才进行树化;
- 哪个链超过了阈值就哪个链树化;
- 如果树化后的节点数小于6,就退树化,变成链表;
- 位图
- 平衡二叉树
- 二叉查找树
- 平衡二叉查找树
- 安全二叉树
- 满二叉树
- B树
- B+树
- 2-3树
- 2-3-4树
- 红黑树
- 大根堆
- 小根堆
- 优先级队列
- 斐波那契堆
- 二顶堆
- 权重
- 有权图
- 无权图
- 方向
- 有向图
- 无向图
- 连续存储--数组
- 离散存储--链表
- 单向链表
- 双向链表
- 循环链表
- 非循环链表
- 跳表
- 栈
- 顺序栈
- 链式栈
- 队列
- 普通队列
- 双端队列
- 阻塞队列
- 并发队列
- 阻塞并发队列
- 交换排序
- 冒泡排序
- 快速排序
- 插入排序
- 简单插入排序
- 希尔排序
- 选择排序
- 简单选择排序
- 堆排序
- 归并排序
- 二路归并排序
- 多路归并排序
- 计数排序
- 桶排序
- 基数排序
标签：排序,
队列,
复杂度,
链表,
查找,
key,
数据结构
From： https://www.cnblogs.com/wxy01/p/17977753