• 记录学习数据结构的总结,希望可以不拘泥于细节和语言,重视应用与推演.

资料来源如下

  • 算法第四版

选择排序

  • 步骤

    • 寻找数组内最小的元素
    • 与未排列的第一个元素交换位置.
    • 重复1 2 知道数组排列完成.
  • 代码

    • 内循环 比较当前元素与已知最小元素
    • 外循环 交换元素位置
  • 性质

    • 运行时间与输入无关..数组有序无序不影响时间.
    • 数据移动最少.交换次数 与 数组长度 为线性关系.
    • 长度为N的数组 , 选择排序 N2/2 次比较,及N次交换.
  • 分析

    • 最直观的排序算法.
    • 无法利用数组的初始状态进行优化.(后续重点)

冒泡排序

  • 步骤

    • 遍历未排列数组,比较两个相邻元素,依照规则 交换/不交换位置.
    • 重复1,直到完成数组排序.
  • 代码

    • 内循环 冒泡整个未排序数组
    • 外循环 控制内循环 冒泡范围
  • 分析

    • 可能是效率最差的
    • 实际效率与选择排序差不多.

插入排序

  • 步骤

    • 从第一个元素开始,该元素可以认为已经被排序
    • 取出下一个元素,比较已排序序列,找到新元素位置
    • 将新元素插入到该位置后
    • 重复步骤直到排序完成.
  • 代码

    • 取出新元素
    • 内循环查找新元素位置
    • 插入新元素
    • 外循环控制
  • 性质

    • 随机数组N, 平均需要 ~ N2/4 次比较及 ~N2/4 次交换.
    • 最坏 N2/2 次比较 N2/2 次交换
    • 最好 N-1 次比较 0 次交换(已经排序好的….😂)
  • 分析

    • 考虑了数组的初始状态,对于大多数元素有序的数组,插入排序可能是最快的.
    • 但对于随机数组 还不够.
  • 优化

    • 查找新元素位置: 二分法查找.而不是遍历.
    • 插入新元素时,算法第四版 建议,内循环改为类似冒泡方式,将大元素右移

希尔排序

  • 对插入排序分析时,有这样的结论: 对于大多数元素有序的数组,插入排序时间最快,时间为线性级别.
    将任意输入的数组 大多数元素有序,然后最后使用 插入排序.

  • 插入排序对于 随机数组的瓶颈 在于,一个元素到达正确位置,一次只能移动一位.那么一次可以移动多位,交换至很远位置,可以改善插入排序的性能.

  • 思路: 将数组等间隔 h 分裂,进行插入排序.拆分后的子数组,插入排序成本较低,进行插入排序.

  • 完成后,原数组的有序性增加 插入排序成本降低,之后再进行颗粒度更细的拆分-排序.一级一级的降低 插入排序成本.直到最后进行 h=1的插入排序.

  • 步骤

    • 对数组进行间隔 h 的插入排序.
    • 依照递增序列,取 h 值,直到 h = 1,为止,排序完成.
  • 代码

    • 内循环为 间隔 h 的插入排序
    • 外循环为 计算 h 值的递增序列.
  • 性质

    • 希尔排序的性质并不容易概括,实际上没有完整概括.
    • 目前可以证明的:希尔排序的运行时间 达不到 N2 级别.
  • 分析

    • 考虑了数组初始状态.是如今提到的排序算法中,第一个可以适用与大容量数组排序的.
    • h 递增序列的选择,会很大程度上影响希尔排序效果.实际工程中适用那种,需要自行选择.
    • 嵌入式系统中没有快排等库函数可选时,首选希尔排序.之后再考虑其他排序算法.

归并排序

  • 归并排序的实现与插入/希尔/选择排序不同.

  • 归并排序依赖于 归并操作.

    • 归并 : 将两个有序数组 合并 为1个有序数组.
  • 自顶向下 递归

    • 实际上是一个 sort 的递归调用.
    • 将数组分为 两个子数组
    • 对子数组调用 调用sort
    • 再对第二层子数组 调用 sort
    • 直到最终子数组元素个数为1.递归返回 开始执行 merge()操作.
  • 自底而上 迭代

    • 直接归并 子元素为1 的各个数组到 子元素为2的数组.
    • 再归并子元素为2 的各个数组 到子元素为4的数组.
    • 最后 可能存在 数组元素不相等,但是不影响归并.
    • 直到归并的数组元素为 N.
  • 实际上 两者执行的过程是一样的,只是调用的角度不同.

  • 性质

    • 空间复杂度不是最优.
    • 时间复杂度 NlogN
    • 空间复杂度 N
  • 优化

    • 原理相同,对小的子数组 使用其他高效排序,再归并.

快速排序

  • 应用最为广泛. 原地排序 时间成本 NlogN

  • 但是! 坑不少…

  • 原理

    • 对于数组中 某个元素 都进行切分操作,大于/小于 该元素的所有元素 都在 一边. 将数组切分为2个子数组. 递归,直到切分子数组元素个数为1,完成排序.
    • 与归并排序 在数组分解上 一致.
  • 步骤

    • 取出数组中某个元素 作为切分元素.
    • 对数组执行切分.
    • 对子数组执行 1 2 直到子数组元素个数为1.递归.
    • 原地切分,创建大量新对象性能上不可接受
    • 保证访问不越界.
    • 慎重处理最大最小元素.
    • 相同元素谨慎处理.
  • 性能改进

    • 切分元素对性能影响及其重要.
      • 最糟糕情况: 大部分元素有序,使用极值去切分.
      • 为避免这种情况,快排之前,将输入数组乱序处理.
      • 对于大型数组 取切分元素时 考虑去3 选 1.
    • 小数组
      • 使用切换到插入排序.
    • 重复元素
      • 一分为二,对于存在大量重复元素的数组,无效的比较次数较多.
      • 改为 三取样切分

三切分取样

  • 切分时,不再一分为二,改为 < = >.三部分
  • 三项切分的信息量最优.
  • 对于存在大量重复元素的数组,三切分取样,直接将时间 由 NlogN 降低到了 N .


  • 记录学习数据结构的总结,希望可以不拘泥于细节和语言,重视应用与推演.

资料来源如下

  • 算法第四版

查找

  • 基于符号表的抽象来组织查找有关内容.分为 key-value ,有时又称字典.
  • 分别介绍 二叉查找树 红黑树 及 散列表 3种经典的实现.

符号表

  • 定义: 存储键值对的数据结构,支持put插入 及 get查找操作.

  • API:

    1
    2
    3
    4
    5
    6
    7
    void put(Key key,Value val)
    Value get(Key key)
    void delete(Key key)
    boolean contains(Key key)
    boolean isEmpty()
    int size()
    Iterable<Key> keys()
  • 规则

    • 没有重复key
    • key不能为空
    • value不能为空
    • 删除操作即使实现.
    • key为不可变类型数据.
  • 成本

    • 使用比较次数来统计成本.
    • 内循环不进行比较时,统计数组访问次数.

其他

  • 有序符号表

    • 额外API
    1
    2
    3
    4
    main()
    max()
    floor(Key key)
    select(int k)
  • 无序符号表

    • 经典的基于链表实现.

二叉查找树BST

  • 数据结构:结点

    • 一个唯一key
    • 对应value
    • 一条左链接
    • 一条右链接
    • 一个节点计数器(该节点的子节点总数)
  • get方法
    表中存在对应方法即返回对应值,否则返回空.
    代码:递归实现

    • 实现get(Node x,Key key)
      • 查找Key 对应值,没有返回null
      • 对比 x 与 key 值.
      • 根据结果返回 get(x.right,key) or get(x.left,key)
    • get由传入根节点调用 get(Node x,Key key)
  • put方法
    存在则更新值,不存在则插入新值.
    代码:递归实现

    • 实现Node put(Node x,Key key,Value val)
      • x为空,则创建新节点并插入key val
      • 对比x key 值
      • x = key,则更新值.
      • 根据结果返回 put(x.right,key,val) or put(x.left,key,val)
      • 更新节点计数器
    • put传入根节点 调用Node put(Node x,Key key,Value val)
  • 分析

    • 如同union-find问题,二叉树生长的方式及平均深度对查找及插入的影响很大.二叉查找树性能非常依赖于 key分布足够随机.

有序符号表

  • 最大最小

    • 传入节点左链接是否为空? 返回传入节点 : 递归调用min(x.left)
    • 传入节点左链接是否为空? 返回传入节点 : 递归调用mam(x.right)
  • 向上/下取整

    • 递归
      • 传入节点左链接 为空.返回 null
      • 传入节点左链接 = key-value 返回 传入节点
      • 传入节点左链接 < key-value 返回 递归传入左链接
      • 传入节点左链接 > key-value 递归传入右链接
        • 判断返回值t 为空?
          • 不为空返回 t
          • 为空返回传入节点.
    • 递归调用.
  • 排名

    • 与节点计数器有关.
    • key = 传入节点,返回左子树节点总数.
    • key < 传入节点,返回 递归左子树.
    • key > 传入节点,返回 递归右子树.
  • 删除最大/最小键

    • 删除最大/最小值,因其子链接均为空,无妨.
  • 删除 -二叉树中间呢?

    • 查找到要删除的节点
    • 保存 父链接 左右子链接.
    • 选择右子树,查找最小节点.(不断选择左子树,直到遇到左子链接为空元素)
    • 将 右子树最小元素 移植到 已删除元素位置.
    • 处理 右子树最小元素 右子链接(直接链接到父节点)
    • 可能存在性能问题.
  • 范围查找

    • 首先遍历操作
      • 递归要不要简单
      • x为空? 返回
      • 过程处理.
      • 不为空, 递归左节点 递归右节点.
    • 在过程处理中进行过滤操作.
    • 因二叉树数值相对有序,舍弃掉不存在想要值的子树.

平衡查找树


  • 只使用二叉树而保持树生长的平衡,代价很高.
  • so,对节点的基础数据结构动一些手脚,引入 2-3 树.
  • 最大的变化在于插入新元素.但随之带来的完美平衡的 2-3 树,让数据结构复杂度很值.

  • 节点可以保存2个key,3个子链接.代表 <a ,a< <b ,>b 3种.

  • 随之带来的好处,树可以一直保持为 完美平衡.所有空链接,到根节点的距离相同.

  • 查找

    • 相对二叉树变动不大.依旧是递归实现.
    • 在判断时加入了2 3节点的指向判断,难度不大,直到遇到空链接为止.
  • 插入

    • 我们所设想的依旧是通过递归的方式实现.尽量统一实现方式.

    • 过程类似,查找插入位置->插入数据->恢复

      • 空节点

        • 直接插入数据即可
      • 2节点

        • 将2节点,变更为3节点.
      • 3节点(比较麻烦)

        • 父节点为空: 直接存入数据->节点变为4节点->4节点分解为3个 2节点,深度+1.
        • 父节点为2节点: 直接存入数据->节点变为4节点->将父节点变为3节点->4节点分解为两个 2节点.
        • 父节点为3节点: 直接存入数据->节点变为4节点->将父节点变为4节点->父节点向上反推过程,直到遇到2节点为止->4节点分解为两个2节点.
        • 整个过程: 存入变4节点,向上反推 直到遇到空节点/2节点为止.分解恢复2-3树.
      • 性能

        • 即使最坏情况下,大小为N的 2-3 树,插入及查找操作访问节点必然不超过 lgN ,因为2-3树保持了完美的平衡.
        • 但额外的维护代码冗余,由此引出红黑树.

红黑树

  • 将2-3树中 1个 3节点 拆分为 2个2节点,中间使用红色链接.

  • 插入/删除 相较于2-3树,复杂.但基础数据结构简单.

  • 牺牲一些平衡性,换来 程序设计的便利.

  • 前置要求

    • 节点是红色或黑色。
    • 根是黑色。
    • 所有叶子都是黑色(叶子是NIL节点)。
    • 每个红色节点必须有两个黑色的子节点。(从每个叶子到根的所有路径上不能有两个连续的红色节点。)
    • 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。
  • 数据结构

    • 在二叉树基础上增加了节点颜色一项.其他不变.

方法实现

基础操作

  • 右/左旋

  • 颜色变化

  • 查找

    • 与二叉树查找相同.
  • 插入

    • 类比2-3树,更加复杂,但基本过程一致.
    • 查找位置->插入节点->修复红黑树.
    • 插入

散列表


  • 记录学习数据结构的总结,希望可以不拘泥于细节和语言,重视应用与推演.

资料来源如下

  • 算法第四版

问题描述

  • 白话文: 一堆网点,随机相连,设计一个算法快速检查两个点是否联通.

  • 物理对应: 闲的一堆金属触点,随机用导线连接,快速查找两个点电路通不通.

  • 精确描述:

    • 定义如下API:

      1
      2
      3
      4
      5
      UF(int N) ;//初始化 N 个点
      void union(int p,int q)//连接p q
      int find(int p)//N个点的分量标识符
      boolean conneted(int p ,int q)//p q联通返回true
      int count()//连通分量数量
    • 设计算法的任务分解为

      • 定义数据结构高效表示连通.
      • 高效实现API方法.

实现算法

  • 叙述原理,不拘泥于代码

quick-find

  • 第一印象,所谓连通两个点,类似物理上的通路,表示两个点的id的值 相同即可.

  • p q 连通,则标识量置为相同值.

  • 分析

    • 非常直观
    • find conneted 非常快.
    • union随着需要连接的节点数量而增大,每次执行 union 都需要遍历整个网格.时间复杂度平方.
    • 大型网格union成本不可接收.
  • 改进

    • 从标识量入手,降低 union 复杂度,即使意味着 find conneted 等成本上升.
    • 平衡各个方法成本.

quick-union

  • 肯定要对标识量下手了,极端一点,将标识量 改为类似树木生长的实现,每个连通拥有一个根元素.
    conneted 判断两个节点的根元素是否相同.
    union 连通 即将两个连通的根元素 链接.
    find 直接返回根节点.

  • 这样 union 的复杂度降低,找到根节点,新建一个链接即可完成.

  • 分析

    • 逻辑上也比较好理解,类似 连通节点,用绳子串起来了.
    • union 的时间复杂度 降低到了线性级别.
    • 但 find 的成本在最糟糕情况下到了 平方 级别.
    • 最糟糕生长情况,从上到下,一个深度只有一个节点.
  • 改进

    • 由导致 find 最糟糕情况入手,避免这种情况.关注点在 树生长的过程.

加权quick-union

  • 我们的目标 控制树的生长,即控制树生长的深度,尽力减少平均深度.

  • 主要做法: union 时,区分大小树,(节点多的树为大),小树只能链接到大树.代码上 要增加一个 数组来标识 一个连通的节点数.

  • 分析

    • 可以很好控制 树生长的高度.
    • 各个方法的时间复杂度,平衡很好.
    • 但是还不是最完美.
  • 改进

    • 继续改进 union 时操作,控制树生长的高度.

路径压缩的加权quick-union

  • 对 union 操作似乎无法继续改进.

  • 但是从直觉上考虑,要控制树的深度,最直接的情况就是所有节点直接连接到根节点.

  • so,在 find 操作中 加入这个转换,将所有节点 直接 连接到根节点.

  • 分析

    • 这是我们目前可以找到的最优解.
    • 但不是所有操作都可以在场数级别.

总结

  • 完整详细定义问题,找到解决问题所必须的抽象操作并定义 API
  • 对于搜索类操作,改进算法的一个方面是: 增加一个数据点可以访问的维度.不限于周围元素,通过某种对应关系,拓展维度.


编程环境

  • Android Studio 3.1.2

问题

  • 升级win10 到了4月份更新1803,启动AS给我来了个 0xc0000005

过程

  • 一切正常升级,除了自己手贱把 Windows Defender 升级到1803 额外的安全全部打开..

解决

  • 万能的stackoverflow 给了答案.问题就在于 Windows Defender 下的 ALSR 好像是内存随机化..(具体意义不太明确)

    https://stackoverflow.com/questions/47500401/android-studio-cannot-be-initialized-0xc0000005

  • 翻译成中文:

    • Windows Defender -> 应用与程序控制 ->Exploit Protection ->程序设置 ->添加程序自定义
    • 找到android stuido安装目录下的 /bin/studio64.exe 一定要完整目录.编辑
    • 找到两个ASLR相关项.强制化ASLR 和 自下而上ASLR ,替换系统设置,关掉.重启AS.

备注

  • win10高级选项 别乱动…


背景

  • 编程环境
    • Android Studio 3.2

解除订阅

  • CompositeDisposable:
    • 得到一个Disposable实例时
    • 调用CompositeDisposable.add()添加到订阅
    • 生命周期结束 CompositeDisposable.clear() 可快速解除.


资料来源如下

常用的Android开发的一些技能点以及BAT公司面试题汇集

  • 感觉自己白学了////😂////

  • 一道一道的找答案..


Android面试题

Android面试题除了Android基础之外,更多的问的是一些源码级别的、原理这些等。所以想去大公司面试,一定要多看看源码和实现方式,常用框架可以试试自己能不能手写实现一下,锻炼一下自己。

一、Android基础知识点

  • 四大组件是什么
  • 四大组件的生命周期和简单用法
  • Activity之间的通信方式
  • Activity各种情况下的生命周期
  • 横竖屏切换的时候,Activity 各种情况下的生命周期
  • Activity与Fragment之间生命周期比较
  • Activity上有Dialog的时候按Home键时的生命周期
  • 两个Activity 之间跳转时必然会执行的是哪几个方法?
  • 前台切换到后台,然后再回到前台,Activity生命周期回调方法。弹出Dialog,生命值周期回调方法。
  • Activity的四种启动模式对比
  • Activity状态保存于恢复
  • fragment各种情况下的生命周期
  • Fragment状态保存startActivityForResult是哪个类的方法,在什么情况下使用?
  • 如何实现Fragment的滑动?
  • fragment之间传递数据的方式?
  • Activity 怎么和Service 绑定?
  • 怎么在Activity 中启动自己对应的Service?
  • service和activity怎么进行数据交互?
  • Service的开启方式
  • 请描述一下Service 的生命周期
  • 谈谈你对ContentProvider的理解
  • 说说ContentProvider、ContentResolver、ContentObserver 之间的关系
  • 请描述一下广播BroadcastReceiver的理解
  • 广播的分类
  • 广播使用的方式和场景
  • 在manifest 和代码中如何注册和使用BroadcastReceiver?
  • 本地广播和全局广播有什么差别?
  • BroadcastReceiver,LocalBroadcastReceiver 区别
  • AlertDialog,popupWindow,Activity区别
  • Application 和 Activity 的 Context 对象的区别
  • Android属性动画特性
  • 如何导入外部数据库?
  • LinearLayout、RelativeLayout、FrameLayout的特性及对比,并介绍使用场景。
  • 谈谈对接口与回调的理解
  • 回调的原理
  • 写一个回调demo
  • 介绍下SurfView
  • RecycleView的使用
  • 序列化的作用,以及Android两种序列化的区别
  • 差值器
  • 估值器
  • Android中数据存储方式

二、Android源码相关分析

  • Android动画框架实现原理
  • Android各个版本API的区别
  • Requestlayout,onlayout,onDraw,DrawChild区别与联系
  • invalidate和postInvalidate的区别及使用
  • Activity-Window-View三者的差别
  • 谈谈对Volley的理解
  • 如何优化自定义View
  • 低版本SDK如何实现高版本api?
  • 描述一次网络请求的流程
  • HttpUrlConnection 和 okhttp关系
  • Bitmap对象的理解
  • looper架构
  • ActivityThread,AMS,WMS的工作原理
  • 自定义View如何考虑机型适配
  • 自定义View的事件
  • AstncTask+HttpClient 与 AsyncHttpClient有什么区别?
  • LaunchMode应用场景
  • AsyncTask 如何使用?
  • SpareArray原理
  • 请介绍下ContentProvider 是如何实现数据共享的?
  • AndroidService与Activity之间通信的几种方式
  • IntentService原理及作用是什么?
  • 说说Activity、Intent、Service 是什么关系
  • ApplicationContext和ActivityContext的区别
  • SP是进程同步的吗?有什么方法做到同步?
  • 谈谈多线程在Android中的使用
  • 进程和 Application 的生命周期
  • 封装View的时候怎么知道view的大小
  • RecycleView原理
  • AndroidManifest的作用与理解

三、常见的一些原理性问题

  • Handler机制和底层实现
  • Handler、Thread和HandlerThread的差别
  • handler发消息给子线程,looper怎么启动?
  • 关于Handler,在任何地方new Handler 都是什么线程下?
  • ThreadLocal原理,实现及如何保证Local属性?
  • 请解释下在单线程模型中Message、Handler、Message Queue、Looper之间的关系
  • 请描述一下View事件传递分发机制
  • Touch事件传递流程
  • 事件分发中的onTouch 和onTouchEvent 有什么区别,又该如何使用?
  • View和ViewGroup分别有哪些事件分发相关的回调方法
  • View刷新机制
  • View绘制流程
  • 自定义控件原理
  • 自定义View如何提供获取View属性的接口?
  • Android代码中实现WAP方式联网
  • AsyncTask机制
  • AsyncTask原理及不足
  • 如何取消AsyncTask?
  • 为什么不能在子线程更新UI?
  • ANR产生的原因是什么?
  • ANR定位和修正
  • oom是什么?
  • 什么情况导致oom?
  • 有什么解决方法可以避免OOM?
  • Oom 是否可以try catch?为什么?
  • 内存泄漏是什么?
  • 什么情况导致内存泄漏?
  • 如何防止线程的内存泄漏?
  • 内存泄露场的解决方法
  • 内存泄漏和内存溢出区别?
  • LruCache默认缓存大小
  • ContentProvider的权限管理(解答:读写分离,权限控制-精确到表级,URL控制)
  • 如何通过广播拦截和abort一条短信?
  • 广播是否可以请求网络?
  • 广播引起anr的时间限制是多少?
  • 计算一个view的嵌套层级
  • Activity栈
  • Android线程有没有上限?
  • 线程池有没有上限?
  • ListView重用的是什么?
  • Android为什么引入Parcelable?
  • 有没有尝试简化Parcelable的使用?

四、开发中常见的一些问题

  • ListView 中图片错位的问题是如何产生的?
  • 混合开发有了解吗?
  • 知道哪些混合开发的方式?说出它们的优缺点和各自使用场景?(解答:比如:RN,weex,H5,小程序,WPA等。做Android的了解一些前端js等还是很有好处的);
  • 屏幕适配的处理技巧都有哪些?
  • 服务器只提供数据接收接口,在多线程或多进程条件下,如何保证数据的有序到达?
  • 动态布局的理解
  • 怎么去除重复代码?
  • 画出 Android 的大体架构图
  • Recycleview和ListView的区别
  • ListView图片加载错乱的原理和解决方案
  • 动态权限适配方案,权限组的概念
  • Android系统为什么会设计ContentProvider?
  • 下拉状态栏是不是影响activity的生命周期
  • 如果在onStop的时候做了网络请求,onResume的时候怎么恢复?
  • Bitmap 使用时候注意什么?
  • Bitmap的recycler()
  • Android中开启摄像头的主要步骤
  • ViewPager使用细节,如何设置成每次只初始化当前的Fragment,其他的不初始化?
  • 点击事件被拦截,但是想传到下面的View,如何操作?
  • 微信主页面的实现方式
  • 微信上消息小红点的原理
  • CAS介绍(这是阿里巴巴的面试题,我不是很了解,可以参考博客: CAS简介


资料来源如下

常用的Android开发的一些技能点以及BAT公司面试题汇集

  • 感觉自己白学了////😂////

  • 一道一道的找答案..


java面试题汇总

熟练掌握java是很关键的,大公司不仅仅要求你会使用几个api,更多的是要你熟悉源码实现原理,甚至要你知道有哪些不足,怎么改进,还有一些java有关的一些算法,设计模式等等。

一、java基础面试知识点

  • java中==和equals和hashCode的区别

    • 关系操作符 ==:
      • 基本数据类型,== 判断的是左右两边操作数的值是否相等
      • 引用数据类型,== 判断的是左右两边操作数的内存地址是否相同,是否是同一个对象。
    • equals方法 基类Object中的实例方法
      • 本质是期望比较 对象的内容
    • hashCode方法,基类Object中的实例方法,返回一个int类型 hash值.
      • 重写上述两个方法,必须保证hashCode与equals的结果一致性,内容相同的对象,hash值相同,比较返回 true
      • hash值为确定对象在哈希表中位置的标识.
  • int、char、long各占多少字节数

    • int 4字节
    • char 2个字节
    • long 8个字节
  • int与integer的区别

    • int为java的内置基本类型
    • integer 为int的包装类
  • 探探对java多态的理解

    • 类之间存在继承关系,子类可以重写父类相同的方法名.
    • 调用时 子类直接调用自己实现的同命方法.
  • String、StringBuffer、StringBuilder区别

    • String 是不可变对象,所有操作都会生成新的String对象
    • StringBuffer StringBuilder 为可变对象.
      • StringBufferd 线程安全
      • StringBuilder 线程不安全,但是单线程性能好
  • 什么是内部类?内部类的作用

    • 内部类主要定义在类的内部
      • 成员内部类
        • 作为外部类的成员,可以直接使用外部类的所有成员和方法,即使是private
        • 外部类要访问内部类的所有成员变量或方法,则需要通过内部类的对象来获取
        • 成员内部类不能含有 static 的变量和方法
      • 局部内部类
        • 指内部类定义在方法和作用域内,就是在外部类的方法中定义的内部类就是局部内部类
        • 局部内部类由于是在方法中定义的,其作用域也是在方法内部中,方法外执行到,则被JVM回收。局部内部类的实例化也只能在方法中进行
        • 局部内部类方法中想要使用局部变量,该变量必须声明为 final 类型
      • 静态内部类
        • 修饰为static的内部类
        • 直接引用 外部类.内部类
        • 实例化: 外部类.内部类 对象 = new 外部类.内部类()
      • 匿名内部类
        • 局部内部类一种
        • 没有名称,只能使用new声明new <类或接口> <类的主体>
        • 使用最多的实例(创建线程):
          1
          2
          3
          4
          5
          6
          7
          8
          9
          10
          11
          12
          public class Demo {
          public static void main(String[] args) {
          Thread t = new Thread() {
          public void run() {
          for (int i = 1; i <= 5; i++) {
          System.out.print(i + " ");
          }
          }
          };
          t.start();
          }
          }
    • 内部类能独立地继承自一个类(接口的)实现,所以无论外围类是否已经继承了某个(接口的)实现,对于内部类都没有影响。内部类使得多重继承的解决方案变得完整。接口解决了部分问题,而内部类有效地实现了“多重继承”。
  • 抽象类和接口区别

    • 抽象类是对事物的抽象,接口是对行为的抽象
  • 抽象类的意义

    • 更利于代码的维护和重用
  • 抽象类与接口的应用场景

    • 接口是为了使用它规范的某一个行为
    • 抽象类是为了使用这个类属性和行为
  • 抽象类是否可以没有方法和属性?

    • 可以
  • 接口的意义

    • 补足多重继承关系.
    • 赋予多态更多的实现方式
  • 泛型中extends和super的区别

    • <? super T> 代表泛型T及其父类 ?的下界
    • <? extends T> 代表泛型T及其子类 ?的上界
    • 频繁往外读取内容的,适合用上界Extends。
    • 经常往里插入的,适合用下界Super。
  • 父类的静态方法能否被子类重写

    • 否 静态方法与对象无关
  • 进程和线程的区别

    • 进程是具有一定独立功能的程序关于某个数据集合上的一次运行活动,进程是系统进行资源分配和调度的一个独立单位。
    • 线程是进程的一个实体, 是CPU调度和分派的基本单位,它是比进程更小的能独立运行的基本单位.线程自己基本上不拥有系统资源,只拥有一点在运行中必不可少的资源(如程序计数器,一组寄存器和栈),但是它可与同属一个进程的其他的线程共享进程所拥有的全部资源。
    • 一个线程可以创建和撤销另一个线程,同一个进程中的多个线程之间可以并发执行。
    • 进程和线程的主要差别在于它们是不同的操作系统资源管理方式。进程有独立的地址空间,一个进程崩溃后,在保护模式下不会对其它进程产生影响,而线程只是一个进程中的不同执行路径。线程有自己的堆栈和局部变量,但线程之间没有单独的地址空间,一个线程死掉就等于整个进程死掉,所以多进程的程序要比多线程的程序 健壮,但在进程切换时,耗费资源较大,效率要差一些。但对于一些要求同时进行并且又要共享某些变量的并发操作,只能用线程,不能用进程。
  • final,finally,finalize的区别

    • final 修饰符 修饰类标识无法再被继承
    • finally 用于错误处理
    • finalize 析构函数,但调用后 资源回收时间由 jvm决定
  • 序列化的方式(待考)

    • 序列化,表示将一个对象转换成可存储或可传输的状态。序列化后的对象可以在网络上进行传输,也可以存储到本地
    • Json,Serializable,Parcelable,ObjectOutputStream
  • Serializable 和Parcelable 的区别

    • Serializable是java api,Parcelable是Android api;
    • Serializable过程需要大量的I/O操作,开销大,效率低
    • Parcelable过程不需要大量的I/O操作,开销小,效率高
  • 静态属性和静态方法是否可以被继承?是否可以被重写?以及原因?

    • 可以被继承,但不能被重写,静态方法和静态属性是属于类.
  • 静态内部类的设计意图

    • 静态内部类可以独立存在,又希望只被外部类使用,private修饰的时候不被同一个包下的其他类使用。
    • 非静态内部类在编译完成之后会隐含地保存着一个引用,该引用是指向创建它的外围内,但是静态内部类却没有。
    • 静态内部类的作用:
    • 只是为了降低包的深度,方便类的使用,
    • 静态内部类适用于包含类当中,但又不依赖与外在的类,不能使用外在类的非静态属性和方法,只是为了方便管理类结构而定义。
    • 在创建静态内部类的时候,不需要外部类对象的引用。
    • 非静态内部类有一个很大的优点:可以自由使用外部类的所有变量和方法
  • 成员内部类、静态内部类、局部内部类和匿名内部类的理解,以及项目中的应用

    • 见上内部类
  • 谈谈对kotlin的理解

    • 代码量下降
    • 语法糖
    • 与java 100%兼容
    • 函数式编程
  • 闭包和局部内部类的区别

  • string 转换成 integer的方式及原理

二、java深入源码级的面试题(有难度)

  • 哪些情况下的对象会被垃圾回收机制处理掉?
  • 讲一下常见编码方式?
  • utf-8编码中的中文占几个字节;int型几个字节?
  • 静态代理和动态代理的区别,什么场景使用?
  • Java的异常体系
  • 谈谈你对解析与分派的认识。
  • 修改对象A的equals方法的签名,那么使用HashMap存放这个对象实例的时候,会调用哪个equals方法?
  • Java中实现多态的机制是什么?
  • 如何将一个Java对象序列化到文件里?
  • 说说你对Java反射的理解
  • 说说你对Java注解的理解
  • 说说你对依赖注入的理解
  • 说一下泛型原理,并举例说明
  • Java中String的了解
  • String为什么要设计成不可变的?
  • Object类的equal和hashCode方法重写,为什么?

三、数据结构

  • 常用数据结构简介

  • 并发集合了解哪些?

  • 列举java的集合以及集合之间的继承关系

  • 集合类以及集合框架

  • 容器类介绍以及之间的区别(容器类估计很多人没听这个词,Java容器主要可以划分为4个部分:List列表、Set集合、Map映射、工具类(Iterator迭代器、Enumeration枚举类、Arrays和Collections),具体的可以看看这篇博文 Java容器类

  • List,Set,Map的区别

  • List和Map的实现方式以及存储方式

  • HashMap的实现原理

  • HashMap数据结构?

  • HashMap源码理解

  • HashMap如何put数据(从HashMap源码角度讲解)?

  • HashMap怎么手写实现?

  • ConcurrentHashMap的实现原理

  • ArrayMap和HashMap的对比

  • HashTable实现原理

  • TreeMap具体实现

  • HashMap和HashTable的区别

  • HashMap与HashSet的区别

  • HashSet与HashMap怎么判断集合元素重复?

  • 集合Set实现Hash怎么防止碰撞

  • ArrayList和LinkedList的区别,以及应用场景

  • 数组和链表的区别

  • 二叉树的深度优先遍历和广度优先遍历的具体实现

  • 堆的结构

  • 堆和树的区别

  • 堆和栈在内存中的区别是什么(解答提示:可以从数据结构方面以及实际实现方面两个方面去回答)?

  • 什么是深拷贝和浅拷贝

  • 手写链表逆序代码

  • 讲一下对树,B+树的理解

  • 讲一下对图的理解

  • 判断单链表成环与否?

  • 链表翻转(即:翻转一个单项链表)

  • 合并多个单有序链表(假设都是递增的)

四、线程、多线程和线程池

  • 开启线程的三种方式?
  • 线程和进程的区别?
  • 为什么要有线程,而不是仅仅用进程?
  • run()和start()方法区别
  • 如何控制某个方法允许并发访问线程的个数?
  • 在Java中wait和seelp方法的不同;
  • 谈谈wait/notify关键字的理解
  • 什么导致线程阻塞?
  • 线程如何关闭?
  • 讲一下java中的同步的方法
  • 数据一致性如何保证?
  • 如何保证线程安全?
  • 如何实现线程同步?
  • 两个进程同时要求写或者读,能不能实现?如何防止进程的同步?
  • 线程间操作List
  • Java中对象的生命周期
  • Synchronized用法
  • synchronize的原理
  • 谈谈对Synchronized关键字,类锁,方法锁,重入锁的理解
  • static synchronized 方法的多线程访问和作用
  • 同一个类里面两个synchronized方法,两个线程同时访问的问题
  • volatile的原理
  • 谈谈volatile关键字的用法
  • 谈谈volatile关键字的作用
  • 谈谈NIO的理解
  • synchronized 和volatile 关键字的区别
  • synchronized与Lock的区别
  • ReentrantLock 、synchronized和volatile比较
  • ReentrantLock的内部实现
  • lock原理
  • 死锁的四个必要条件?
  • 怎么避免死锁?
  • 对象锁和类锁是否会互相影响?
  • 什么是线程池,如何使用?
  • Java的并发、多线程、线程模型
  • 谈谈对多线程的理解
  • 多线程有什么要注意的问题?
  • 谈谈你对并发编程的理解并举例说明
  • 谈谈你对多线程同步机制的理解?
  • 如何保证多线程读写文件的安全?
  • 多线程断点续传原理
  • 断点续传的实现

并发编程有关知识点(这个是一般Android开发用的少的,所以建议多去看看):

平时Android开发中对并发编程可以做得比较少,Thread这个类经常会用到,但是我们想提升自己的话,一定不能停留在表面,,我们也应该去了解一下java的关于线程相关的源码级别的东西。


学习的参考资料如下:

Java 内存模型

  • java线程安全总结
  • 深入理解java内存模型系列文章

线程状态:

  • 一张图让你看懂JAVA线程间的状态转换

锁:

  • 锁机制:synchronized、Lock、Condition
  • Java 中的锁

并发编程:

  • Java并发编程:Thread类的使用
  • Java多线程编程总结
  • Java并发编程的总结与思考
  • Java并发编程实战—–synchronized
  • 深入分析ConcurrentHashMap

面向对象

  • 类 方法 实例
  • 封装 继承 多态

类和实例

  • 示例

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    class Student(object):

    def __init__(self, name, score):
    self.name = name
    self.score = score

    def print_score(self):
    print('%s: %s' % (self.name, self.score))

    bart = Student('Bart Simpson', 59)
  • 定义类的关键词与java一样 class 括号内为继承的父类.没有父类时,选择 object 作为基类.(object是所有类的基类)

  • 变量比较特殊,不像java中有单独字段.python 类中变量定义是在__init__方法

  • 方法的声明和函数类似. def 方法名 (参数)

    • 类中 第一个参数必须是self,意为创建的实例自身.方法中调用类中其他变量都要通过 self.xxx 访问.
  • 一些必须实现的属性在__init__方法中定义.如示例.第一个参数是 self 之后是具体变量值,在方法内 使用self访问类中定义的变量.

  • Python允许对实例变量绑定任何数据,so just do it😈

访问限制

  • 类似java private 字段的python实现

  • 属性的名称前加上两个下划线 __ 该属性就成为了类的私有属性,只能在实例的内部访问.(self.xxx)

  • 获取/修改,使用 get/set 获取或修改对应属性.(一般在set中可以添加类型检查)

  • 类似__xxx__的变量,双下划线开头,并且以双下划线结尾的,是特殊变量.特殊变量是可以直接访问的,不是private变量.也最好不要定义__xxx__变量名

  • 以下划线开头的实例变量名,例如_name.可以在外部访问的,但是,约定俗成,请直接忽视.

  • 特例:

    • 双下划线开头的实例变量不能直接访问是因为Python解释器对外把__name变量改成了_Student__name.仍然可以通过_Student__name来访问__name变量.

    • 一个错误设置示例:

      1
      2
      3
      4
      5
      6
      7
      8
      >>> bart = Student('Bart Simpson', 59)
      >>> bart.get_name()
      'Bart Simpson'
      >>> bart.__name = 'New Name' # 设置__name变量!
      >>> bart.__name
      'New Name'
      >>> bart.get_name() # get_name()内部返回self.__name
      'Bart Simpson'
    • 如同示例,外部代码直接赋给 bart.__name 不会影响实例中原有属性,只会新增一个属性.究其原因,实例中的属性已经被解释器重命名为了bart._Student__name.

继承和多态

  • 继承和多态概念与java类似.不多语了.
  • 那么重点来了:
  • python本身是动态语言,体现在变量/类等各个方面,自由度极高.在继承上,亦是如此.
    • java中定义一个su方法,调用model类实例实现的run方法.su方法可传入的只有 model类或其子类的实例
    • 但python中 只要是定义了 run方法(别管内容/功能一样不一样)类的实例,都可以作为参数传入 su 方法.
  • java中对类的类型的处理,相当于照猫🐱画虎🐯,传入的起码要是个猫科动物. python 中对类的类型处理,额头写个字,哪怕传入具体对象是个猫头鹰🦉,也当作猫科处理了.

  • note:
    判断一个变量是否是某个类型可以用isinstance()

    1
    2
    >>> isinstance(a, list)
    True

获取对象信息


  • 让我想起了java反射..不过能获取的信息要全多了.

type()

  • 示例:

    1
    2
    3
    4
    5
    6
    7
    8
    >>> type(123)
    <class 'int'>

    >>> type(a)
    <class '__main__.Animal'>

    >>> type(123)==type(456)
    True
  • 判断对象类型

  • 由变量指向函数或者类,也可以用type()判断

  • type返回对应的Class类型,可直接 == 类型判断

  • 判断一个对象是否是函数:

    1
    2
    3
    4
    5
    6
    7
    8
    >>> import types
    >>> def fn():
    ... pass
    ...
    >>> type(fn)==types.FunctionType
    True
    >>> type(abs)==types.BuiltinFunctionType
    True

isinstance()

  • 示例:

    1
    2
    3
    4
    5
    >>> isinstance(h, Husky)
    True

    >>> isinstance([1, 2, 3], (list, tuple))
    True
  • 判断继承关系,一打一个准.

  • 能用type()判断的基本类型也可以用isinstance()判断

  • 总是优先使用isinstance()判断类型,可以将指定类型及其子类“一网打尽”。

dir()

  • 示例:

    1
    2
    >>> dir('ABC')
    ['__add__', '__class__',..., '__subclasshook__', 'capitalize', 'casefold',..., 'zfill']
  • 获得一个对象的所有属性和方法.直接返回一个字符串list.

  • 配合getattr()、setattr()以及hasattr(),可以直接操作一个对象的状态.

  • 示例:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    >>> hasattr(obj, 'x') # 有属性'x'吗?
    True
    >>> obj.x
    9
    >>> hasattr(obj, 'y') # 有属性'y'吗?
    False
    >>> setattr(obj, 'y', 19) # 设置一个属性'y'
    >>> hasattr(obj, 'y') # 有属性'y'吗?
    True
    >>> getattr(obj, 'y') # 获取属性'y'
    19
    >>> obj.y # 获取属性'y'
    19
  • 不存在的属性,会抛出AttributeError的错误,可以传入一个default参数,如果属性不存在,就返回默认值.

    1
    2
    >>> getattr(obj, 'z', 404) # 获取属性'z',如果不存在,返回默认值404
    404
  • 也可以获得对象的方法

    1
    2
    3
    4
    5
    6
    7
    8
    9
    >>> hasattr(obj, 'power') # 有属性'power'吗?
    True
    >>> getattr(obj, 'power') # 获取属性'power'
    <bound method MyObject.power of <__main__.MyObject object at 0x10077a6a0>>
    >>> fn = getattr(obj, 'power') # 获取属性'power'并赋值到变量fn
    >>> fn # fn指向obj.power
    <bound method MyObject.power of <__main__.MyObject object at 0x10077a6a0>>
    >>> fn() # 调用fn()与调用obj.power()是一样的
    81
  • 只有在不知道对象信息的时候,才会去获取对象信息.谨记,谨记.

实例属性和类属性

  • 类似java类中静态变量 与 普通变量区别.

  • 类的属性,直接在类的cclass中声明.

    1
    2
    class Student(object):
    name = 'Student'
  • 访问时,类的属性会被实例的同名属性覆盖,但不会被修改,互相独立.

  • 删除实例属性后,再使用相同的名称,访问到的将是类属性

模块

  • 模块是一组Python代码的集合,可以使用其他模块,也可以被其他模块使用。

  • 涉及到概念 包(Package) 和 模块(Module)

  • 创建自己的模块时,要注意:

    • 模块名要遵循Python变量命名规范,不要使用中文、特殊字符;
    • 模块名不要和系统模块名冲突,最好先查看系统是否已存在该模块,检查方法是在Python交互环境执行import abc,若成功则说明系统存在此模块。

使用模块

  • 示例

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    #!/usr/bin/env python3
    # -*- coding: utf-8 -*-

    ' a test module '

    __author__ = 'Michael Liao'

    import sys

    def test():
    args = sys.argv
    if len(args)==1:
    print('Hello, world!')
    elif len(args)==2:
    print('Hello, %s!' % args[1])
    else:
    print('Too many arguments!')

    if __name__=='__main__':
    test()
  • 注释:

    • 第1行注释可以让这个hello.py文件直接在Unix/Linux/Mac上运行
    • 第2行注释表示.py文件本身使用标准UTF-8编码;
    • 第4行是一个字符串,表示模块的文档注释,任何模块代码的第一个字符串都被视为模块的文档注释
    • 第6行使用__author__变量把作者写进去
  • 重点if __name__=='__main__':

  • Python解释器把一个特殊变量__name__置为__main__,而如果在其他地方导入该hello模块时,if判断将失败,因此,这种if测试可以让一个模块通过命令行运行时执行一些额外的代码,最常见的就是运行测试.

作用域

  • Python中,是通过_前缀 标记 private
  • note: python中语法没有限制 _开头的变量/函数!

安装第三方模块

  • pip命令

    1
    pip install xxx
  • 或者在文件中自定义路径.