垃圾回收算法

一、引用计数法

给对象中添加一个引用计数器，每当有一个地方引用它时，计数器值就加1；当引用失效时，计数器值就减1；任何时刻计数器都为0的对象就是不再被使用的，垃圾收集器将回收该对象使用的内存。

引用计数算法实现简单，效率很高，微软的COM技术、ActionScript、Python等都使用了引用计数算法进行内存管理，但是引用计数算法对于对象之间相互循环引用问题难以解决，因此java并没有使用引用计数算法。

二、可达性分析算法

通过一系列的名为“GC Root”的对象作为起点，从这些节点向下搜索，搜索所走过的路径称为引用链(Reference Chain)，当一个对象到GC Root没有任何引用链相连时，则该对象不可达，该对象是不可使用的，垃圾收集器将回收其所占的内存。

主流的商用程序语言C#、java和Lisp都使用根搜素算法进行内存管理。

在java语言中，可作为GC Root的对象包括以下几种对象：

1 、 虚拟机栈（栈帧中的本地变量表）中引用的对象。

2、 本地方法栈中JNI（即一般说的native方法）引用的对象。

3、 方法区中的静态变量和常量引用的对象。

性能分析工具android profiler

android profiler Android studio ide 集成的分析工具

一.cpu profiler
记录暂停,自动分析,傻瓜式操作
1.Method Trace
2.TracceView
3.SysteTrace
4.代码记录文件分析

1
2

//.trace 文件路径,用来分析,最后生成testTraceView.trace文件在sd卡目录中
Debug.startMethodTracing("testTraceView");

1

Debug.stopMethodTracing();

二.memory profiler
三.network profiler
四.energy profiler

adb shell dumpsys batterystats

屏幕适配

数据结构与算法

1.线性表

表示n个数据元素的有限序列.元素的数据可以是字母,数字,符号,对象,结构等

线性表包括线性顺序表,线性链表

1.1线性-顺序表

里面元素的内存空间地址是连续的序存储结构，

#####1.2 线性-链表
链式存储结构,里面节点的内存空间地址不是连续的，是通过指针连起来的。

1.2.1 循环链表

链式存储结构,特点最后一个节点的指针指向头节点

1.2.2 双向链表

双向链表的节点中有两个指针,一个指向后,一个指向前

####1.3 栈

1.3.1定义

栈是定义仅在表尾进行插入或删除的线性表

表尾又叫栈顶,表头端叫栈底
特点后进先出

1.3.2栈的表示和实现

1.3.2.1顺序栈

1.3.2.2链栈

1.4 队列

队列是先进先出的线性表
表的一端差入元素,另一端删除元素

1.4.1用链表表示的队列链队列

1.5 树和二叉树

1.5.1 树

树是n个结点的有限集,有且仅有一个特定的根结点
树是一个结点可以有n个结点点 ,每个结点又是一个树,形成一种递归

度
结点拥有的子树的数量称为结点的度

终端结点
度为0的节点称为叶子或总端结点,度不为0的结点称为非终端结点或分支结点,分支结点又称内部结点

数的度是属内各结点的度的最大值

结点的子树根层次结点的还在,该结点称为孩子双亲

结点的层次是从根开始定义起,根为第一层,根的孩子结点为第二层

双亲在同一层的结点互为堂兄,
树中结点的最大层次称为树的深度或高度

1.5.2二叉树

二叉树
二叉树,每个结点最多两棵子树,二叉树的子树有左右之分

满二叉树
一颗深度为k且有2∧k-1个结点的数据称为满二叉树

完全二叉树
对满二叉树的结点进行连续编号,从根结点起,自上而下,从左至右,深度为k的,有n个结点的二叉树,当且仅当每一个结点与满二叉树中的编号从1至n的结点一一对应时,称之为完全二叉树

性质1
在树的第i层上至多有2∧(i-1)个节点i>=1

性质2
深度为k的二叉树至多有2∧k-1个结点

性质3
度是0的结点数量 = 度是2的结点数量+1

性质4
具有n个结点的完全二叉树的深度为 (log2n)+1

性质5

对任意一个结点i

1.5.3遍历二叉树

先序遍历：
（1）访问根节点；
（2）采用先序递归遍历左子树；
（3）采用先序递归遍历右子树；

中序遍历：
按照左子树->根节点->右子树的顺序访问

后序遍历：
（1）采用后序递归遍历左子树；
（2）采用后序递归遍历右子树；
（3）访问根节点；

平衡二叉搜索树

平衡二叉搜索树（Balanced Binary Tree）具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。常用算法有红黑树、AVL、Treap、伸展树等。在平衡二叉搜索树中，我们可以看到，其高度一般都良好地维持在O（log（n）），大大降低了操作的时间复杂度。

红黑树

红黑树就是一种平衡的二叉查找树，说他平衡的意思是他不会变成“瘸子”，左腿特别长或者右腿特别长。除了符合二叉查找树的特性之外，还具体下列的特性：

1. 节点是红色或者黑色

2. 根节点是黑色

3. 每个叶子的节点都是黑色的空节点（NULL）

4. 每个红色节点的两个子节点都是黑色的。

5. 从任意节点到其每个叶子的所有路径都包含相同的黑色节点。

红黑树相比avl树，在检索的时候效率其实差不多，都是通过平衡来二分查找。但对于插入删除等操作效率提高很多。红黑树不像avl树一样追求绝对的平衡，他允许局部很少的不完全平衡，这样对于效率影响不大，但省去了很多没有必要的调平衡操作，avl树调平衡有时候代价较大，所以效率不如红黑树，在现在很多地方都是底层都是红黑树的天下啦~

红黑树的优势
总结
HashMap在里面就是链表加上红黑树的一种结构，这样利用了链表对内存的使用率以及红黑树的高效检索，是一种很happy的数据结构。

二叉查找树

二叉树的提出其实主要就是为了提高查找效率，比如我们常用的 HashMap 在处理哈希冲突严重时，拉链过长导致查找效率降低，就引入了红黑树。

我们知道，二分查找可以缩短查找的时间，但是它要求 查找的数据必须是有序的。每次查找、操作时都要维护一个有序的数据集，于是有了二叉查找树这个概念。

二叉查找树（又叫二叉排序树），它是具有下列性质的二叉树：

1. 若左子树不空，则左子树上所有结点的值均小于它的根结点的值；

2. 若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值；

```

死锁

两个或者多个线程互相持有对方所需要的资源，导致这些线程处于等待状态，无法前往执行

例子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

public class DeadLock {

    public static void main(String[] args) {
        dead_lock();
    }

    private static void dead_lock() {
		// 两个资源
        final Object resource1 = "resource1";
        final Object resource2 = "resource2";
        // 第一个线程，想先占有resource1,再尝试着占有resource2
        Thread t1 = new Thread() {
            public void run() {
            	// 尝试占有resource1
                synchronized (resource1) {
                	// 成功占有resource1
                    System.out.println("Thread1 1:locked resource1");
                    // 休眠一段时间
                    try {
                        Thread.sleep(50);
                    } catch (InterruptedException e) {
                        e.printStackTrace();
                    }
                    // 尝试占有resource2，如果不能占有，该线程会一直等到
                    synchronized (resource2) {
                        System.out.println("Thread1 1:locked resource2");
                    }
                }
            }
        };
        // 第二个线程，想先占有resource2，再占有resource1
        Thread t2 = new Thread() {
            public void run() {
            	// 尝试占有resource2
                synchronized (resource2) {
                	// 成功占有resource2
                    System.out.println("Thread2 1 :locked resource2");
                    // 休眠一段时间
                    try {
                        Thread.sleep(50);
                    } catch (InterruptedException e) {
                        e.printStackTrace();
                    }
                    // 尝试占有resource1，如果不能占有，该线程会一直等到
                    synchronized (resource1) {
                        System.out.println("Thread2 2:locked resource1");
                    }
                }
            }
        };
        // 启动线程
        t1.start();
        t2.start();
        
        try {
            Thread.sleep(2000);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
       System.out.println("Thread1 state:"+t1.getState());
       System.out.println("Thread2 state:"+t2.getState());
    }
}

输出结果

1
2
3
4

Thread1 1:locked resource1
Thread2 1 :locked resource2
Thread1 state:BLOCKED
Thread2 state:BLOCKED

线程的状态

1.新建状态
当用new操作符创建一个线程时。此时程序还没有开始运行线程中的代码。

2.就绪状态

当线程对象调用start()方法即启动了线程，start()方法创建线程运行的系统资源，JVM调度线程运行run()方法。当start()方法返回后，线程就处于就绪状态。

处于就绪状态的线程并不一定立即运行run()方法，线程还必须同其他线程竞争CPU时间，只有获得CPU时间才可以运行线程。因为在单CPU的计算机系统中，不可能同时运行多个线程，一个时刻仅有一个线程处于运行状态。因此此时可能有多个线程处于就绪状态。对多个处于就绪状态的线程是由Java运行时系统的线程调度程序来调度的。

3.运行状态（running）

当线程获得CPU时间后，它才进入运行状态，真正开始执行run()方法。

4.阻塞状态（blocked）
所谓阻塞状态是正在运行的线程没有运行结束，暂时让出CPU，这时其他处于就绪状态的线程就可以获得CPU时间，进入运行状态。

线程运行过程中，可能由于各种原因进入阻塞状态：

①线程通过调用sleep方法进入睡眠状态；

②线程调用一个在I/O上被阻塞的操作，即该操作在输入输出操作完成之前不会返回到它的调用者；

③线程试图得到一个锁，而该锁正被其他线程持有；

④线程在等待某个触发条件；

堵塞状态是前述四种状态中最有趣的，值得我们作进一步的探讨。线程被堵塞可能是由下述五方面的原因造成的：

(1) 调用sleep(毫秒数)，使线程进入”睡眠”状态。在规定的时间内，这个线程是不会运行的。

(2) 用suspend()暂停了线程的执行。除非线程收到resume()消息，否则不会返回”可运行”状态。

(3) 用wait()暂停了线程的执行。除非线程收到nofify()或者notifyAll()消息，否则不会变成”可运行”（是的，这看起来同原因2非常相象，但有一个明显的区别是我们马上要揭示的）。

(4) 线程正在等候一些IO（输入输出）操作完成。

(5) 线程试图调用另一个对象的”同步”方法，但那个对象处于锁定状态，暂时无法使用。

5.死亡状态（dead）

有两个原因会导致线程死亡：

①run方法正常退出而自然死亡；

②一个未捕获的异常终止了run方法而使线程猝死；

为了确定线程在当前是否存活着（就是要么是可运行的，要么是被阻塞了），需要使用isAlive方法，如果是可运行或被阻塞，这个方法返回true；如果线程仍旧是new状态且不是可运行的，或者线程死亡了，则返回false。

编译打包APK过程

一、打包资料文件，生成R.java文件。(aapt工具)

二、处理aidl文件，生成相应的Java文件。(/)

三、编译工程源代码，生成相应的class文件。(javac编译工程)

四、转换所有的class文件，生成classes.dex文件。(dx工具)

五、打包生成APK文件。(apkbuider脚本)

六、对apk进行签名(jarsigner工具,signapk工具)

七、对签名后apk进行对齐处理(加快apk速度)

设计模式-六大原则

单一职责原则

定义：不要存在多于一个导致类变更的原因。通俗的说，即一个类只负责一项职责。

使用单一职责原则带来哪些好处呢？

类的复杂性降低，一个类只有一个职责，类比较清晰。
可读性、可维护性提高。
变更引起的风险降低。

里氏替换原则

定义：所有引用基类的地方必须能透明地使用其子类的对象。就是说有父类出现的地方，都可以用子类来替换的。

子类必须完全实现父类的地方。
子类可以有自己的特性。
覆盖或实现父类的方法时输入参数可以被放大。
覆盖或实现父类的方法时输出结果可以被缩小。

使用里氏替换原则带来的好处？
增强了程序的健壮性，版本升级时也可以保持非常好的兼容，即使增加子类，原有的子类还可以继续运行。在实际项目中，每个子类对应不同的业务含义，使用父类作为参数，传递不同的子类完成不同的业务逻辑，非常完美。

依赖倒置原则

定义：高层模块不应该依赖低层模块，二者都应该依赖其抽象；抽象不应该依赖细节；细节应该依赖抽象。

接口隔离原则

定义：客户端不应该依赖它不需要的接口；一个类对另一个类的依赖应该建立在最小的接口上。

接口要尽量小。但是在拆分接口的时候，首先必须满足单一职责原则。

接口要高内聚。
首先要明白什么是高内聚？高内聚就是提高接口、类、模块的处理能力，同时减少对外的交互（也就是少暴漏接口出去）。也就是说，尽量减少对外提供的接口，让提供的每个接口的处理能力增强。

定制服务。可以理解为对每个模块提供专用的接口。也可以理解为只提供访问者需要的方法，不需要的方法都不提供。
接口设计是有限度的。

迪米特法则

定义：一个对象应该对其他对象保持最少的了解。
问题由来：类与类之间的关系越密切，耦合度越大，当一个类发生改变时，对另一个类的影响也越大。

解决方案：尽量降低类与类之间的耦合。

开闭原则

定义：一个软件实体如类、模块和函数应该对扩展开放，对修改关闭。

NDK编译多个平台的FFMPEG

编译配置里面的新名词

1. Toolchain — tools that are used for compiling and building of sources.
2. Sysroot  — sysroot 是一个包含针对您的目标的系统标头和库的目录
3. Prefix — directory in which result of building will be written to.
4. Cross-prefix — directory of compiler to be used.
5. ABI — architecture of processor (i.e. x86, arm-v6, armv8–64 and so om).
6. CFLAGS — flags for C-compiler.
7. LDFLAGS — flags for linker.

android支持的7钟CPU架构

armeabi 第5代 ARM v5TE，使用软件浮点运算，兼容所有ARM设备，通用性强，速度慢（只支持armeabi）

armeabi-v7a 第7代 ARM v7，使用硬件浮点运算，具有高级扩展功能（支持 armeabi 和 armeabi-v7a，目前大部分手机都是这个架构）

arm64-v8a 第8代，64位，包含AArch32、AArch64两个执行状态对应32、64bit（支持 armeabi-v7a、armeabi 和 arm64-v8a）

*x86 intel 32位，一般用于平板（支持 armeabi(性能有所损耗) 和 x86）

x86_64 intel 64位，一般用于平板（支持 x86 和 x86_64）

mips 基本没见过（支持 mips）

mips64 基本没见过（支持 mips 和 mips_64）

利用独立工具链接生成不同cpu架构的头文件

https://developer.android.com/ndk/guides/standalone_toolchain

1
2
3
4
5
6
7
8
9
10
11

$ANDROID_NDK/build/tools/make-standalone-toolchain.sh \
--arch=arm --platform=android-21 --install-dir=/home/hx/Downloads/ffmpeg-android/toolchain-android/arm

$ANDROID_NDK/build/tools/make-standalone-toolchain.sh \
--arch=arm64 --platform=android-21 --install-dir=/home/hx/Downloads/ffmpeg-android/toolchain-android/arm64

$ANDROID_NDK/build/tools/make-standalone-toolchain.sh \
--arch=x86 --platform=android-21 --install-dir=/home/hx/Downloads/ffmpeg-android/toolchain-android/x86

$ANDROID_NDK/build/tools/make-standalone-toolchain.sh \
--arch=x86_64 --platform=android-21 --install-dir=/home/hx/Downloads/ffmpeg-android/toolchain-android/x86_64

另外一种利用toolchain方式生成，生成arm64，android 的api 必须对应21 （Android 5.0 API 21 Lollipop）

1
2

$ANDROID_NDK/build/tools/make-standalone-toolchain.sh \
--toolchain=aarch64-linux-android-4.9  --platform=android-21 --install-dir=/home/hx/Downloads/ffmpeg-android/toolchain-android/x86_64

–arch 有4种选项

arm arm64 x86 x86_64

./configure \
–cross-prefix=/home/hx/Downloads/ffmpeg-android/toolchain-android/bin/aarch64-linux-android- \
–sysroot=”/home/hx/Downloads/ffmpeg-android/toolchain-android/sysroot” \
–host=aarch64-linux \
–enable-pic \
–disable-asm \
–enable-static \
–disable-shared \
–disable-opencl \
–prefix=”/home/hx/Downloads/ffmpeg-android/build/arm64-v8a” \
–disable-cli &&
make -j8 &&make install

./configure –target-os=linux –cross-prefix=/home/hx/Downloads/ffmpeg-android/toolchain-android/bin/aarch64-linux-android- –arch=arm64 –cpu=armv8-a –enable-runtime-cpudetect –sysroot=/home/hx/Downloads/ffmpeg-android/toolchain-android/sysroot –enable-pic –enable-libx264 –enable-libass –enable-libfreetype –enable-libfribidi –enable-libmp3lame –enable-fontconfig –enable-pthreads –disable-debug –enable-version3 –enable-hardcoded-tables –disable-ffplay –disable-ffprobe –enable-gpl –enable-yasm –disable-doc –enable-shared –enable-static –pkg-config=/home/hx/Downloads/ffmpeg-android/ffmpeg-pkg-config –prefix=/home/hx/Downloads/ffmpeg-android/build/arm64-v8a –extra-cflags=-I/home/hx/Downloads/ffmpeg-android/toolchain-android/include –extra-ldflags=-L/home/hx/Downloads/ffmpeg-android/toolchain-android/lib –extra-libs=’-lpng -lexpat -lm’ –extra-cxxflags= &&make -j 8 && make install

错误：checking host system type… Invalid configuration `aarch64-linux-android’:
解决方法：更新config.sub and config.guess，或者更新整个类库

armeabi 兼容是最全的，armeabi-v7速度比较块，但有些arm的cpu不兼容

ANR超时

Activity 超时 5秒
ActivityManagerService.java

1
2

// How long we wait until we timeout on key dispatching.
    static final int KEY_DISPATCHING_TIMEOUT = 5*1000;

前台service 超时默认20秒 后台service 超时200秒
android framework 源码中 ActiveServices.java

1
2
3
4
5

// How long we wait for a service to finish executing.
static final int SERVICE_TIMEOUT = 20*1000;

// How long we wait for a service to finish executing.
static final int SERVICE_BACKGROUND_TIMEOUT = SERVICE_TIMEOUT * 10;

1
2
3
4
5
6
7
8

void serviceTimeout(ProcessRecord proc) {
       //...
       //proc.execServicesFg 是否前台执行任务

            final long maxTime =  now -
                    (proc.execServicesFg ? SERVICE_TIMEOUT : SERVICE_BACKGROUND_TIMEOUT);
          //...
    }

广播,前台 10秒 后台60秒
ActivityManagerService.java

1
2
3

// How long we allow a receiver to run before giving up on it.
   static final int BROADCAST_FG_TIMEOUT = 10*1000;
   static final int BROADCAST_BG_TIMEOUT = 60*1000;