算法与数据结构
程序 = 数据结构 + 算法。
一般而言，二者是职业生涯中的门槛，不了解它们，你会非常迅速地碰到职业的天花板。
什么是算法，什么是数据结构
算法实战：动手实现二分查找
算法实战：动手实现快速排序
数据结构实战：动手实现栈
数据结构实战：动手实现链表
ArrayList源码分析
HashMap源码分析
为什么我们需要算法和数据结构?
- 计算机世界的基石，是程序员的内功
- 对代码效率的提升是本质的R
- 面试需要……
今天的所有算法和数据结构 都要求能够手写
基本数据结构
数组
- 随机寻址
- 常数时间
- 插入/删除
- 线性时间
- 查找
- 无序：线性时间
- 有序：对数时间（二分查找）
- 【要求】手写二分查找
链表
- 寻址
- 线性时间
- 插入/删除
- 常数时间
- 查找
- 线性时间
- 【要求】手写
- 翻转链表
- 判断链表是否成环
栈 Stack
- FILO (First In Last Out)
- 应用：方法栈
- 【要求】手写一个栈的实现
队列Queue
- FIFO (First In First Out)
- 应用：线程池
- 【要求】手写一个队列的实现
哈希表
- 查找/插入/删除操作都是0(1)
- 哈希算法与碰撞
- 哈希桶的内部实现
二叉树
- 二叉树有两个孩子
- 相应的，多叉树有多个孩子
- 【要求】手写：
- 二叉树的深度优先遍历
- 二叉树的广度优先遍历
搜索二叉树
- —棵经过精心设计的二叉树
- 可以将搜索效率降低到对数时间
- 致命缺点：可能会退化成链表
- 红黑树
算法
算法的复杂度
- 时间复杂度
- O(1) - 哈希桶/数组随机寻址(常数)
- O(n) - 遍历(线性)
- O(log(n)) - 二分查找，二叉树(对数)
- 使用条件：查找序列是顺序结构，有序
- 优点 比较次数少，查找速度快，平均性能好
- 缺点 要求待查表为有序表，且插入删除困难
- O(n*log(n)) - 基于比较的排序算法的下界
- O(n^2) - 冒泡排序(平方)
- 时间复杂度的计算是忽略常数的
- 即O(n)=O(2n)
- 时间复杂度的计算中，高阶复杂度会吞并低阶复杂度
- O(n^2)+O(n)=O(n^2)
排序算法-综述
- 最基础的算法
- 基于比较的排序算法的复杂度下界是O(nlog(n))
- 排序的稳定性
- Java默认用什么排序算法？
排序算法-冒泡排序
- 最直观，最容易理解的排序算法
- 想象一下你是体育委员，要对班级同学排序
- 效率低，始终是0(^2)
- 【要求】能手写
排序算法-快速排序
- 每次将等待排序的数据划分成两部分
- 递归进行
- 直到所有数据有序
排序算法-归并排序
- 分而治之
- 将一个大问题分解成小问题
- 解决小问题
- 递归地解决大问题
- 空间复杂度0(n)
拷问灵魂深处的问题
-
HashMap默认容量？
- 16个桶
-
HashMap如何扩容？
- 超过容量 * 负载因子
- 扩容是之前的2倍
-
HashMap的数组大小为什么一定要是2的幂？
- hash & （length - 1)
- 只有长度是2的n次方的时候对它 -1 操作才能拿到二进制全是1的值，再进行按位与，用位运算快速拿到数组下标并且分布均匀
-
- javadoc描述此实现不是同步的
- HashMap底层是一个Entry数组,采用拉链法解决碰撞冲突
-
Java 7到8做了哪些改进？为什么？
-
Java 7的HashMap的问题
-
非常容易碰到的死锁
-
潜在的安全隐患
-
CVE-2011-4858 , Tomcat邮件组的讨论
-
Java 8的HashMap
-
数组+链表/红黑树
-
扩容时插入顺序的改进
-
函数方法
- forEach
- compute系列
-
Map的新API
- merge
- replace
-
哈希表简介
- 核心是基于哈希值的桶和链表
- O(1)的平均查找、插入、删除时间
- 致命缺陷是哈希值的碰撞(collision)
举例子：- 电话本：A-Z把姓放到对应的字母
- 哈希值：A-Z
- 哈希桶：Z-张三-张三丰
- 碰撞：张三-张三丰3
- 桶的实现基于int hashCode
- 哈希表：A-Z哈希桶