日期: 2021 年 6 月 2 日

岛屿数量（JS实现）

1 题目
给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。
示例 1:
输入:
[
[‘1’,‘1’,‘1’,‘1’,‘0’],
[‘1’,‘1’,‘0’,‘1’,‘0’],
[‘1’,‘1’,‘0’,‘0’,‘0’],
[‘0’,‘0’,‘0’,‘0’,‘0’]
]
输出: 1
示例 2:
输入:
[
[‘1’,‘1’,‘0’,‘0’,‘0’],
[‘1’,‘1’,‘0’,‘0’,‘0’],
[‘0’,‘0’,‘1’,‘0’,‘0’],
[‘0’,‘0’,‘0’,‘1’,‘1’]
]
输出: 3
解释: 每座岛屿只能由水平和/或竖直方向上相邻的陆地连接而成。

链接：https://leetcode-cn.com/problems/number-of-islands

2 思路
这道题思路就是图的广度优先遍历，将搜索到的1变为#，然后统计次数就可以了

3代码
/**
* @param {character[][]} grid
* @return {number}
*/
var numIslands = function(grid) {
let res = 0;
let rows = grid.length;
if (rows === 0) return 0;
let cols = grid[0].length;

for (let i=0; i<rows; i++) {
for (let j=0; j<cols; j++) {
if (grid[i][j] === ‘1’) {
res++;
search(i,j);
}
}
}

function search(i, j) {
if (i < 0 || j < 0 || i >= rows || j >= cols || grid[i][j] === ‘0’ || grid[i][j] === ‘#’) return;

grid[i][j] = ‘#’;

search(i+1, j);
search(i-1, j);
search(i, j+1);
search(i, j-1);
}

return res;
};

数字范围按位与（JS实现）

1 题目
给定范围 [m, n]，其中 0 <= m <= n <= 2147483647，返回此范围内所有数字的按位与（包含 m, n 两端点）。
示例 1:
输入: [5,7]
输出: 4
示例 2:
输入: [0,1]
输出: 0

链接：https://leetcode-cn.com/problems/bitwise-and-of-numbers-range

2 思路
这道题可以罗列出几个数，观察一下规律，我们可以发现计算结果只与n和m有关，比如101和111计算结果为4，也就是100，其实就是他们相同的*高位的值

3代码
/**
* @param {number} m
* @param {number} n
* @return {number}
*/
var rangeBitwiseAnd = function(m, n) {
if (m === n) return n;
let res = 0;
let count = 0;
let temp = n;

while(m && n) {
if ((m & 1) !== (n & 1)) {
res = count;
}
m = m >> 1;
n = n >> 1;
count++;
}

if (m || n) return 0;

temp = temp >> (res + 1);
temp = temp << (res + 1);

return temp;

};

快乐数（JS实现）

1 题目
编写一个算法来判断一个数 n 是不是快乐数。
「快乐数」定义为：对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和，然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。如果 可以变为 1，那么这个数就是快乐数。
如果 n 是快乐数就返回 True ；不是，则返回 False 。
示例：
输入：19
输出：true
解释：
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

链接：https://leetcode-cn.com/problems/happy-number

2 思路
这道题我是按照题意直接做的，在题解中有更巧妙的解法，实际上只有一个循环：4 > 16 > 37 > 58 > 89 > 145 > 42 > 20 > 4, 只需检测是否有数进入这个循环就知道结果了

3代码
/**
* @param {number} n
* @return {boolean}
*/
var isHappy = function(n) {
const map = {};
let num = ” + n;

do {
let sum = 0;
for (let i=0; i<num.length; i++) {
sum += Math.pow(parseInt(num[i]), 2);
}
if (sum === 1) return true;
map[num] = true;
num = ” + sum;
}while(!map[num]);

return false;

};

计数质数（JS实现）

1 题目
统计所有小于非负整数 n 的质数的数量。
示例:
输入: 10
输出: 4
解释: 小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。

2 思路
这道题即判断每个数是否为质数，题解中有个更巧妙的方法， Sieve of Eratosthenes算法，即某个若为质数，则其所有倍数都不可能是质数了

3代码
/**
* @param {number} n
* @return {number}
*/
var countPrimes = function(n) {
if (n <= 1) return 0;

let count = 0;
for (let i=2; i<n; i++) {
if (i > 3 && (i % 2 === 0 || i % 3 === 0)) continue;
if (isPrime(i)) count++;
}

return count;

function isPrime(num) {
let p = Math.sqrt(num);

for (let i=2; i<=p; i++) {
if (num % i === 0) return false;
}

return true;
}
};

课程表（JS实现）

1 题目
你这个学期必须选修 numCourse 门课程，记为 0 到 numCourse-1 。
在选修某些课程之前需要一些先修课程。 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们：[0,1]
给定课程总量以及它们的先决条件，请你判断是否可能完成所有课程的学习？
示例 1:
输入: 2, [[1,0]]
输出: true
解释: 总共有 2 门课程。学习课程 1 之前，你需要完成课程 0。所以这是可能的。
示例 2:
输入: 2, [[1,0],[0,1]]
输出: false
解释: 总共有 2 门课程。学习课程 1 之前，你需要先完成​课程 0；并且学习课程 0 之前，你还应先完成课程 1。这是不可能的。

链接：https://leetcode-cn.com/problems/course-schedule

2 思路
这道题就是考察拓扑排序，用于排查图里有没有环，首先建立图的邻接矩阵，然后再进行拓扑排序，逐步删除入度为0的节点

3代码
/**
* @param {number} numCourses
* @param {number[][]} prerequisites
* @return {boolean}
*/
var canFinish = function(numCourses, prerequisites) {
function Vex(value) {
this.val = value;
this.firstEdge = null;
this.in = 0;
}

const vexs = [];

for (let arr of prerequisites) {
if (!vexs[arr[1]]) {
vexs[arr[1]] = new Vex(arr[1]);
}

if (!vexs[arr[0]]) {
vexs[arr[0]] = new Vex(arr[0]);
}

let firstEdge = vexs[arr[1]].firstEdge;
vexs[arr[1]].firstEdge = {vex: vexs[arr[0]], next: firstEdge};
vexs[arr[0]].in++;
}

const stack= [];
let len = 0;
for (let i=0; i<vexs.length; i++) {
if (vexs[i]) {
len++;
if (vexs[i].in === 0) stack.push(vexs[i]);
}
}

let count = 0;
while(stack.length > 0) {
let currentVex = stack.pop();
count++;
let currentEdge = currentVex.firstEdge;
while(currentEdge) {
if (–currentEdge.vex.in === 0) stack.push(currentEdge.vex);
currentEdge = currentEdge.next;
}
}

return len === count;

};

实现 Trie (前缀树)（JS实现）

1 题目
实现一个 Trie (前缀树)，包含 insert, search, 和 startsWith 这三个操作。
示例:
Trie trie = new Trie();
trie.insert(“apple”);
trie.search(“apple”); // 返回 true
trie.search(“app”); // 返回 false
trie.startsWith(“app”); // 返回 true
trie.insert(“app”);
trie.search(“app”); // 返回 true
说明:
你可以假设所有的输入都是由小写字母 a-z 构成的。
保证所有输入均为非空字符串。

链接：https://leetcode-cn.com/problems/implement-trie-prefix-tree

2 思路
这道题就是实现前缀树这种数据结构，这种数据结构有个特点，就是每个节点存储一个元素为指针的数组，数组的索引就指明当前的字母，而数组值就指向下一个指针数组。

3代码
/**
* Initialize your data structure here.
*/
var Trie = function() {
this.startIndex = ‘a’.charCodeAt();
this.root = new TreeNode();
};

/**
* Inserts a word into the trie.
* @param {string} word
* @return {void}
*/
Trie.prototype.insert = function(word) {
let p = this.root;
for (let i=0; i<word.length; i++) {
let index = word[i].charCodeAt() – this.startIndex;
if (!p.list[index]) {
let newNode = new TreeNode();
p.list[index] = newNode;
}
p = p.list[index];
}
p.type = ‘leaf’;
p.word = word;
};

/**
* Returns if the word is in the trie.
* @param {string} word
* @return {boolean}
*/
Trie.prototype.search = function(word) {
let p = this.root;
for (let i=0; i<word.length; i++) {
p = p.list[word[i].charCodeAt() – this.startIndex];
if (!p && i<word.length-1) return false;
}

if (p && p.type === ‘leaf’ && p.word === word) return true;
return false;
};

/**
* Returns if there is any word in the trie that starts with the given prefix.
* @param {string} prefix
* @return {boolean}
*/
Trie.prototype.startsWith = function(prefix) {
let p = this.root;
for (let i=0; i<prefix.length; i++) {
p = p.list[prefix[i].charCodeAt() – this.startIndex];
if (!p) return false;
}
return true;
};

function TreeNode() {
this.type = ‘branch’;
this.list = [];
this.word = ”;
}

/**
* Your Trie object will be instantiated and called as such:
* var obj = new Trie()
* obj.insert(word)
* var param_2 = obj.search(word)
* var param_3 = obj.startsWith(prefix)
*/

Android面试题数据结构篇，由本人整理汇总，后续将继续推出系列篇，如果喜欢请持续关注和推荐

List,Set,Map的区别

Set是*简单的一种集合。集合中的对象不按特定的方式排序，并且没有重复对象。 Set接口主要实现了两个实现类：

HashSet： HashSet类按照哈希算法来存取集合中的对象，存取速度比较快
TreeSet ：TreeSet类实现了SortedSet接口，能够对集合中的对象进行排序。
List的特征是其元素以线性方式存储，集合中可以存放重复对象。

ArrayList() :代表长度可以改变得数组。可以对元素进行随机的访问，向ArrayList()中插入与删除元素的速度慢。
LinkedList():在实现中采用链表数据结构。插入和删除速度快，访问速度慢。
Map 是一种把键对象和值对象映射的集合，它的每一个元素都包含一对键对象和值对象。Map没有继承于Collection接口 从Map集合中检索元素时，只要给出键对象，就会返回对应的值对象。

HashMap：Map基于散列表的实现。插入和查询“键值对”的开销是固定的。可以通过构造器设置容量capacity和负载因子load factor，以调整容器的性能。
LinkedHashMap： 类似于HashMap，但是迭代遍历它时，取得“键值对”的顺序是其插入次序，或者是*近*少使用(LRU)的次序。只比HashMap慢一点。而在迭代访问时发而更快，因为它使用链表维护内部次序。
TreeMap ： 基于红黑树数据结构的实现。查看“键”或“键值对”时，它们会被排序(次序由Comparabel或Comparator决定)。TreeMap的特点在 于，你得到的结果是经过排序的。TreeMap是唯一的带有subMap()方法的Map，它可以返回一个子树。
WeakHashMao ：弱键(weak key)Map，Map中使用的对象也被允许释放: 这是为解决特殊问题设计的。如果没有map之外的引用指向某个“键”，则此“键”可以被垃圾收集器回收。
ArrayMap和HashMap的对比

1、存储方式不同，HashMap内部有一个HashMapEntry<K,V>[]对象，每一个键值对都存储在这个对象里，当使用put方法添加键值对时，就会new一个HashMapEntry对象。
2、添加数据时扩容时的处理不一样，进行了new操作，重新创建对象，开销很大。ArrayMap用的是copy数据，所以效率相对要高。
3、ArrayMap提供了数组收缩的功能，在clear或remove后，会重新收缩数组，是否空间
4、ArrayMap采用二分法查找；
HashMap和HashTable的区别

1 HashMap不是线程安全的，效率高一点、方法不是Synchronize的要提供外同步，有containsvalue和containsKey方法。
hashtable是，线程安全，不允许有null的键和值，效率稍低，方法是是Synchronize的。有contains方法方法。Hashtable 继承于Dictionary 类
HashMap与HashSet的区别

hashMap:HashMap实现了Map接口,HashMap储存键值对,使用put()方法将元素放入map中,HashMap中使用键对象来计算hashcode值,HashMap比较快，因为是使用唯一的键来获取对象。
HashSet实现了Set接口，HashSet仅仅存储对象，使用add()方法将元素放入set中，HashSet使用成员对象来计算hashcode值，对于两个对象来说hashcode可能相同，所以equals()方法用来判断对象的相等性，如果两个对象不同的话，那么返回false。HashSet较HashMap来说比较慢。
HashSet与HashMap怎么判断集合元素重复？
HashSet不能添加重复的元素，当调用add（Object）方法时候，首先会调用Object的hashCode方法判hashCode是否已经存在，如不存在则直接插入元素；如果已存在则调用Object对象的equals方法判断是否返回true，如果为true则说明元素已经存在，如为false则插入元素。

ArrayList和LinkedList的区别，以及应用场景
ArrayList是基于数组实现的，ArrayList线程不安全。 LinkedList是基于双链表实现的。 使用场景：

如果应用程序对各个索引位置的元素进行大量的存取或删除操作，ArrayList对象要远优于LinkedList对象；
如果应用程序主要是对列表进行循环，并且循环时候进行插入或者删除操作，LinkedList对象要远优于ArrayList对象；
数组和链表的区别

数组：是将元素在内存中连续存储的；它的优点：因为数据是连续存储的，内存地址连续，所以在查找数据的时候效率比较高；它的缺点：在存储之前，我们需要申请一块连续的内存空间，并且在编译的时候就必须确定好它的空间的大小。在运行的时候空间的大小是无法随着你的需要进行增加和减少而改变的，当数据两比较大的时候，有可能会出现越界的情况，数据比较小的时候，又有可能会浪费掉内存空间。在改变数据个数时，增加、插入、删除数据效率比较低。
链表：是动态申请内存空间，不需要像数组需要提前申请好内存的大小，链表只需在用的时候申请就可以，根据需要来动态申请或者删除内存空间，对于数据增加和删除以及插入比数组灵活。还有就是链表中数据在内存中可以在任意的位置，通过应用来关联数据（就是通过存在元素的指针来联系）
HashMap的实现原理：

HashMap是基于哈希表的map接口的非同步实现，它允许使用null值作为key和value。在Java编程语言中*基本的结构就是两种，一种是数组，另一种是模拟指针（引用）。所有的数据结构都可以用这两个基本的结构来构造，HashMap也不例外。HashMap实际上是一个“链表散列”的数据结构。即数组和链表的结合体。HashMap底层就是一个数据结构，数组中的每一项又是一个链表。

冲突：
HashMap中调用Hashcode()方法计算Hashclde值，由于Java中两个不同的对象可能有一样的Hashcode。就导致了冲突的产生。

解决：
HashMap在put时候，底层源码可以看出，当程序试图将一个key-value对象放入到HashMap中，首先根据该key的hashCode()返回值决定该Entry的存储位置，如果两个Entry的key的hashCode()方法返回值相同，那他们的存储位置相同，如果这两个Entry的key通过equals比较返回true，新添加的Entry的value将会覆盖原来的Entry的value，但是key不会被覆盖，反之，如果返回false，新添加的Entry将与集合中原有的Entry形成Entry链，新添加的位于头部，旧的位于尾部。

原理

利用key的hashCode重新hash计算出当前对象的元素在数组中的下标。
存储时如果出现hash值相同的key，分两种情况：1、如果key相同，则覆盖原来的值。2、如果key不同（出现冲突），则放在链表中。
获取时，直接找到hash值对应的下标，再进一步判断key是否相同，从而拿到对应的值。
Hashmap的核心就是使用数组进行存储，出现key冲突的时候，就存放在链表中。
ConcurrentHashMap内部实现，HashTable的实现被废弃的原因:

1.HashTable容器在竞争激烈的并发环境下表现出效率低下的原因，是因为所有访问HashTable的线程都必须竞争同一把锁，那假如容器里有多把锁，每一把锁用于锁容器其中一部分数据，那么当多线程访问容器里不同数据段的数据时，线程间就不会存在锁竞争，从而可以有效的提高并发访问效率，这就是ConcurrentHashMap所使用的锁分段技术，首先将数据分成一段一段的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据的时候，其他段的数据也能被其他线程访问。
2.ConcurrentHashMap是由Segment数组结构和HashEntry数组结构组成。Segment是一种可重入锁ReentrantLock，在ConcurrentHashMap里扮演锁的角色，HashEntry则用于存储键值对数据。一个ConcurrentHashMap里包含一个Segment数组，Segment的结构和HashMap类似，是一种数组和链表结构， 一个Segment里包含一个HashEntry数组，每个HashEntry是一个链表结构的元素，每个Segment守护者一个HashEntry数组里的元素,当对HashEntry数组的数据进行修改时，必须首先获得它对应的Segment锁。
说说 LruCache 底层原理
LruCache 使用一个 LinkedHashMap 简单的实现内存的缓存，没有软引用，都是强引用。如果添加的数据大于设置的*大值，就删除*先缓存的数据来调整内存。
maxSize 是通过构造方法初始化的值，他表示这个缓存能缓存的*大值是多少。
size 在添加和移除缓存都被更新值，他通过safeSizeOf 这个方法更新值。safeSizeOf默认返回1，但一般我们会根据 maxSize重写这个方法，比如认为 maxSize 代表是 KB 的话，那么就以KB为单位返回该项所占的内存大小。
除异常外首先会判断size是否超过maxSize，如果超过了就取出*先插入的缓存，如果不为空就删掉，并把size减去该项所占的大小。这个操作将一直循环下去，直到 size 比 maxSize 小或者缓存为空。

本文完~

Android面试题内存&性能篇，由本人整理汇总，后续将继续推出系列篇，如果喜欢请持续关注和推荐

内存分配

RAM（random access memory）随机存取存储器。说白了就是内存。 一般Java在内存分配时会涉及到以下区域：

寄存器（Registers）：速度*快的存储场所，因为寄存器位于处理器内部，我们在程序中无法控制
栈（Stack）：存放基本类型的数据和对象的引用，但对象本身不存放在栈中，而是存放在堆中
堆（Heap）：堆内存用来存放由new创建的对象和数组。在堆中分配的内存，由Java虚拟机的自动垃圾回收器（GC）来管理。
静态域（static field）： 静态存储区域就是指在固定的位置存放应用程序运行时一直存在的数据，Java在内存中专门划分了一个静态存储区域来管理一些特殊的数据变量如静态的数据变量
常量池（constant pool）：虚拟机必须为每个被装载的类型维护一个常量池。常量池就是该类型所用到常量的一个有序集和，包括直接常量（string,integer和floating point常量）和对其他类型，字段和方法的符号引用。
非RAM存储：硬盘等永久存储空间
堆栈存储特点对比：

栈：当定义一个变量时，Java就在栈中为这个变量分配内存空间，当该变量退出该作用域后，Java会自动释放掉为该变量所分配的内存空间，该内存空间可以立即被另作他用。
堆：当堆中的new产生数组和对象超出其作用域后，它们不会被释放，只有在没有引用变量指向它们的时候才变成垃圾，不能再被使用。即使这样，所占内存也不会立即释放，而是等待被垃圾回收器收走。这也是Java比较占内存的原因。
堆栈运行特点对比：

栈：存取速度比堆要快，仅次于寄存器。但缺点是，存在栈中的数据大小与生存期必须是确定的，缺乏灵活性。
堆：堆是一个运行时数据区，可以动态地分配内存大小，因此存取速度较慢。也正因为这个特点，堆的生存期不必事先告诉编译器，而且Java的垃圾收集器会自动收走这些不再使用的数据。
对象引用类型：

引用分为四种级别，这四种级别由高到低依次为：强引用>软引用>弱引用>虚引用。

强引用（strong reference）
如：Object object=new Object（），object就是一个强引用了。当内存空间不足，Java虚拟机宁愿抛出OutOfMemoryError错误，使程序异常终止，也不会靠随意回收具有强引用的对象来解决内存不足问题。
软引用（SoftReference）
只有内存不够时才回收,常用于缓存；当内存达到一个阀值，GC就会去回收它；
弱引用（WeakReference）
弱引用的对象拥有更短暂的生命周期。在垃圾回收器线程扫描它 所管辖的内存区域的过程中，一旦发现了只具有弱引用的对象，不管当前内存空间足够与否，都会回收它的内存。
虚引用（PhantomReference）
“虚引用”顾名思义，就是形同虚设，与其他几种引用都不同，虚引用并不会决定对象的生命周期。如果一个对象仅持有虚引用，那么它就和没有任何引用一样，在任何时候都可能被垃圾回收。
UI优化

a.合理选择RelativeLayout、LinearLayout、FrameLayout,RelativeLayout会让子View调用2次onMeasure，而且布局相对复杂时，onMeasure相对比较复杂，效率比较低，LinearLayout在weight>0时也会让子View调用2次onMeasure。LinearLayout weight测量分配原则。
b.使用标签<include><merge><ViewStub>
c.减少布局层级，可以通过手机开发者选项>GPU过渡绘制查看，一般层级控制在4层以内，超过5层时需要考虑是否重新排版布局。
d.自定义View时，重写onDraw()方法，不要在该方法中新建对象，否则容易触发GC，导致性能下降
e.使用ListView时需要复用contentView，并使用Holder减少findViewById加载View。
f.去除不必要背景，getWindow().setBackgroundDrawable(null)
g.使用TextView的leftDrawabel/rightDrawable代替ImageView+TextView布局
内存优化

主要为了避免OOM和频繁触发到GC导致性能下降

a.Bitmap.recycle(),Cursor.close,inputStream.close()
b.大量加载Bitmap时，根据View大小加载Bitmap，合理选择inSampleSize，RGB_565编码方式；使用LruCache缓存
c.使用 静态内部类+WeakReference 代替内部类，如Handler、线程、AsyncTask
d.使用线程池管理线程，避免线程的新建
e.使用单例持有Context，需要记得释放，或者使用全局上下文
f.静态集合对象注意释放
g.属性动画造成内存泄露
h.使用webView，在Activity.onDestory需要移除和销毁，webView.removeAllViews()和webView.destory()
备：使用LeakCanary检测内存泄露

响应速度优化

Activity如果5秒之内无法响应屏幕触碰事件和键盘输入事件，就会出现ANR，而BroadcastReceiver如果10秒之内还未执行操作也会出现ANR，Serve20秒会出现ANR 为了避免ANR，可以开启子线程执行耗时操作，但是子线程不能更新UI，因此需要Handler消息机制、AsyncTask、IntentService进行线程通信。

备：出现ANR时，adb pull data/anr/tarces.txt 结合log分析

其他性能优化

a.常量使用static final修饰
b.使用SparseArray代替HashMap
c.使用线程池管理线程
d.ArrayList遍历使用常规for循环，LinkedList使用foreach
e.不要过度使用枚举，枚举占用内存空间比整型大
f.字符串的拼接优先考虑StringBuilder和StringBuffer
g.数据库存储是采用批量插入+事务
Android内存泄露及管理

（1）内存溢出（OOM）和内存泄露（对象无法被回收）的区别。 （2）引起内存泄露的原因
（3）内存泄露检测工具—->LeakCanary

内存溢出 out of memory：是指程序在申请内存时，没有足够的内存空间供其使用，出现out of memory；比如申请了一个integer,但给它存了long才能存下的数，那就是内存溢出。内存溢出通俗的讲就是内存不够用。

内存泄露 memory leak：是指程序在申请内存后，无法释放已申请的内存空间，一次内存泄露危害可以忽略，但内存泄露堆积后果很严重，无论多少内存,迟早会被占光

内存泄露原因：

Handler 引起的内存泄漏。
解决：将Handler声明为静态内部类，就不会持有外部类SecondActivity的引用，其生命周期就和外部类无关，如果Handler里面需要context的话，可以通过弱引用方式引用外部类
单例模式引起的内存泄漏。
解决：Context是ApplicationContext，由于ApplicationContext的生命周期是和app一致的，不会导致内存泄漏
非静态内部类创建静态实例引起的内存泄漏。
解决：把内部类修改为静态的就可以避免内存泄漏了
非静态匿名内部类引起的内存泄漏。
解决：将匿名内部类设置为静态的。
注册/反注册未成对使用引起的内存泄漏。
注册广播接受器、EventBus等，记得解绑。
资源对象没有关闭引起的内存泄漏。
在这些资源不使用的时候，记得调用相应的类似close（）、destroy（）、recycler（）、release（）等方法释放。
集合对象没有及时清理引起的内存泄漏。
通常会把一些对象装入到集合中，当不使用的时候一定要记得及时清理集合，让相关对象不再被引用。
JAVA相关性能优化

1 不用new关键词创建类的实例
用new关键词创建类的实例时，构造函数链中的所有构造函数都会被自动调用。但如果一个对象实现了Cloneable接口，我们可以调用它的clone()方法。clone()方法不会调用任何类构造函数。

在使用设计模式（Design Pattern）的场合，如果用Factory模式创建对象，则改用clone()方法创建新的对象实例非常简单。例如，下面是Factory模式的一个典型实现：
public static Credit getNewCredit() {
return new Credit();
}
改进后的代码使用clone()方法，如下所示：
private static Credit BaseCredit = new Credit();
public static Credit getNewCredit() {
return (Credit) BaseCredit.clone();
}
上面的思路对于数组处理同样很有用。

2 使用非阻塞I/O
版本较低的JDK不支持非阻塞I/O API。为避免I/O阻塞，一些应用采用了创建大量线程的办法（在较好的情况下，会使用一个缓冲池）。这种技术可以在许多必须支持并发I/O流的应用中见 到，如Web服务器、报价和拍卖应用等。然而，创建Java线程需要相当可观的开销。 JDK 1.4引入了非阻塞的I/O库（java.nio）。如果应用要求使用版本较早的JDK，在这里有一个支持非阻塞I/O的软件包。

3 慎用异常
异 常对性能不利。抛出异常首先要创建一个新的对象。Throwable接口的构造函数调用名为fillInStackTrace()的本地（Native） 方法，fillInStackTrace()方法检查堆栈，收集调用跟踪信息。只要有异常被抛出，VM就必须调整调用堆栈，因为在处理过程中创建了一个新 的对象。 异常只能用于错误处理，不应该用来控制程序流程。

4 不要重复初始化变量
默认情况下，调用类的构造函数时， Java会把变量初始化成确定的值：所有的对象被设置成null，整数变量（byte、short、int、long）设置成0，float和 double变可柚贸?.0，逻辑值设置成false。当一个类从另一个类派生时，这一点尤其应该注意，因为用new关键词创建一个对象时，构造函数链中 的所有构造函数都会被自动调用。

5 尽量指定类的final修饰符
带有final修饰符的类是不可派生的。在Java核心API中，有许多应用final的例子，例如java.lang.String。为String类指定final防止了人们覆盖length()方法。 另外，如果指定一个类为final，则该类所有的方法都是final。Java编译器会寻找机会内联（inline）所有的final方法（这和具体的编译器实现有关）。此举能够使性能平均提高50%。

6 尽量使用局部变量
调用方法时传递的参数以及在调用中创建的临时变量都保存在栈（Stack）中，速度较快。其他变量，如静态变量、实例变量等，都在堆（Heap）中创建，速度较慢。另外，依赖于具体的编译器/JVM，局部变量还可能得到进一步优化。请参见《尽可能使用堆栈变量》。

7 乘法和除法
考虑下面的代码： for (val = 0; val < 100000; val +=5) { alterX = val * 8; myResult = val * 2; } 用移位操作替代乘法操作可以*大地提高性能。下面是修改后的代码： for (val = 0; val < 100000; val += 5) { alterX = val << 3; myResult = val << 1; }

8.字符串拼接
不要随意的使用stingA=StringB+StringC的写法，有大量拼接操作的地方用StringBuilder代替

本文完~

Android面试题系统原理篇，由本人整理汇总，后续将继续推出系列篇，如果喜欢请持续关注和推荐。

Dalvik虚拟机与JVM有什么区别

Dalvik 基于寄存器，而 JVM 基于栈。基于寄存器的虚拟机对于更大的程序来说，在它们编译的时候，花费的时间更短。 Dalvik执行.dex格式的字节码，而JVM执行.class格式的字节码。

Dalvik基于JVM的改进

几个class变为一个dex，constant pool，省内存 Zygote，copy-on-write shared,省内存，省cpu，省电 基于寄存器的bytecode，省指令，省cpu，省电 Trace-based JIT,省cpu，省电,省内存

apk安装卸载的原理

安装过程：复制apk安装包到data/app目录下，解压并扫描安装包，把dex文件(dalvik字节码)保存到dalvik-cache目录，并data/data目录下创建对应的应用数据目录。

APK打包流程和其内容

1.流程
1.aapt生成R文件
2.aidl生成java文件
3.将全部java文件编译成class文件
4.将全部class文件和第三方包合并成dex文件
5.将资源、so文件、dex文件整合成apk
6.apk签名
7.apk字节对齐
2.内容：so、dex、asset、资源文件
class和dex

1.dvm执行的是dex格式文件，jvm执行的是class文件，android程序编译完之后生产class文件。然后dex工具会把class文件处理成dex文件，然后把资源文件和.dex文件等打包成apk文件。
2.dvm是基于寄存器的虚拟机，而jvm执行是基于虚拟栈的虚拟机。寄存器存取速度比栈快的多，dvm可以根据硬件实现*大的优化，比较适合移动设备。
3.class文件存在很多的冗余信息，dex工具会去除冗余信息，并把所有的class文件整合到dex文件中。减少了I/O操作，提高了类的查找速度
Android采用什么软件架构？整个系统包括哪几个层次？

Android采用堆栈式软件架构，系统分为四个层，从高层到低层分别是：应用程序层、应用程序框架层、系统运行库层和linux核心层。

APP从启动到主页显示经历了哪些过程

①点击桌面App图标，Launcher进程采用Binder IPC向system_server进程发起startActivity请求；
②system_server进程接收到请求后，向zygote进程发送创建进程的请求；
③Zygote进程fork出新的子进程，即App进程；
④App进程，通过Binder IPC向sytem_server进程发起attachApplication请求；
⑤system_server进程在收到请求后，进行一系列准备工作后，再通过binder IPC向App进程发送scheduleLaunchActivity请求；
⑥App进程的binder线程（ApplicationThread）在收到请求后，通过handler向主线程发送LAUNCH_ACTIVITY消息；
⑦主线程在收到Message后，通过发射机制创建目标Activity，并回调Activity.onCreate()等方法。
⑧到此，App便正式启动，开始进入Activity生命周期，执行完onCreate/onStart/onResume方法，UI渲染结束后便可以看到App的主界面。
操作系统如何管理内存的：

1.使用寄存器进行将进程地址和物理内存进行映射
2.虚拟内存进行内存映射到硬盘上增大内存
3.虚拟内存是进行内存分页管理
4.页表实现分页，就是 页+地址偏移。
5.如果程序的内存在硬盘上，那么就需要用页置换算法来将其调入内存中：先进先出、*近未使用*少等等
apk瘦身:

1.classes.dex：通过代码混淆，删掉不必要的jar包和代码实现该文件的优化
2.资源文件：通过Lint工具扫描代码中没有使用到的静态资源
3.图片资源：使用tinypng和webP，下面详细介绍图片资源优化的方案,矢量图
4.SO文件将不用的去掉，目前主流app一般只放一个arm的so包
GC原理

1.搜索算法：
1.引用计数
2.图搜索，可达性分析
2.回收算法：
1.标记清除复制：用于青年代
2.标记整理：用于老年代
3.堆分区：
1.青年区eden 80%、survivor1 10%、survivor2 10%
2.老年区
4.虚拟机栈分区：
1.局部变量表
2.操作数栈
3.动态链接
4.方法返回地址
5.GC Roots:
1.虚拟机栈(栈桢中的本地变量表)中的引用的对象
2.方法区中的类静态属性引用的对象
3.方法区中的常量引用的对象
4.本地方法栈中JNI的引用的对象

本文完~

Android面试题架构篇，由本人整理汇总，后续将继续推出系列篇，如果喜欢请持续关注和推荐。

系列文章目录：

Android面试题View篇
Android面试题进程篇
Android面试题线程篇
Android面试题网络篇

如何实现一个网络框架(参考Volley)

1.缓存队列,以url为key缓存内容可以参考Bitmap的处理方式，这里单独开启一个线程。
2.网络请求队列，使用线程池进行请求。
3.提供各种不同类型的返回值的解析如String，Json，图片等等。
mvc、mvp、mvvm：

1.mvc:数据、View、Activity，View将操作反馈给Activity，Activitiy去获取数据，数据通过观察者模式刷新给View。循环依赖
1.Activity重，很难单元测试
2.View和Model耦合严重
2.mvp:数据、View、Presenter，View将操作给Presenter，Presenter去获取数据，数据获取好了返回给Presenter，Presenter去刷新View。PV，PM双向依赖
1.接口爆炸
2.Presenter很重
3.mvvm:数据、View、ViewModel，View将操作给ViewModel，ViewModel去获取数据，数据和界面绑定了，数据更新界面更新。
1.viewModel的业务逻辑可以单独拿来测试
2.一个view 对应一个 viewModel 业务逻辑可以分离，不会出现全能类
3.数据和界面绑定了，不用写垃圾代码，但是复用起来不舒服
ClassLoader的基础知识

1.双亲委托：一个ClassLoader类负责加载这个类所涉及的所有类，在加载的时候会判断该类是否已经被加载过，然后会递归去他父ClassLoader中找。
2.可以动态加载Jar通过URLClassLoader
3.ClassLoader 隔离问题 JVM识别一个类是由：ClassLoader id+PackageName+ClassName。
4.加载不同Jar包中的公共类：
1.让父ClassLoader加载公共的Jar，子ClassLoader加载包含公共Jar的Jar，此时子ClassLoader在加载公共Jar的时候会先去父ClassLoader中找。(只适用Java)
2.重写加载包含公共Jar的Jar的ClassLoader，在loadClass中找到已经加载过公共Jar的ClassLoader，也就是把父ClassLoader替换掉。(只适用Java)
3.在生成包含公共Jar的Jar时候把公共Jar去掉。
插件化框架描述：dynamicLoadApk为例子

1.可以通过DexClassLoader来对apk中的dex包进行加载访问
2.如何加载资源是个很大的问题，因为宿主程序中并没有apk中的资源，所以调用R资源会报错，所以这里使用了Activity中的实现ContextImpl的getAssets()和getResources()再加上反射来实现。
3.由于系统启动Activity有很多初始化动作要做，而我们手动反射很难完成，所以可以采用接口机制，将Activity的大部分生命周期提取成接口，然后通过代理Activity去调用插件Activity的生命周期。同时如果像增加一个新生命周期方法的时候，只需要在接口中和代理中声明一下就行。
4.缺点：
1.慎用this，因为在apk中使用this并不代表宿主中的activity，当然如果this只是表示自己的接口还是可以的。除此之外可以使用that代替this。
2.不支持Service和静态注册的Broadcast
3.不支持LaunchMode和Apk中Activity的隐式调用。
热修复：Andfix为例子

1.大致原理：apkpatch将两个apk做一次对比，然后找出不同的部分。可以看到生成的apatch了文件，后缀改成zip再解压开，里面有一个dex文件。通过jadx查看一下源码，里面就是被修复的代码所在的类文件,这些更改过的类都加上了一个_CF的后缀，并且变动的方法都被加上了一个叫@MethodReplace的annotation，通过clazz和method指定了需要替换的方法。然后客户端sdk得到补丁文件后就会根据annotation来寻找需要替换的方法。*后由JNI层完成方法的替换。
2.无法添加新类和新的字段、补丁文件很容易被反编译、加固平台可能会使热补丁功能失效
oKhttp原理：

1.同步和异步：
1.异步使用了Dispatcher来将存储在 Deque 中的请求分派给线程池中各个线程执行。
2.当任务执行完成后，无论是否有异常，finally代码段总会被执行，也就是会调用Dispatcher的finished函数，它将正在运行的任务Call从队列runningAsyncCalls中移除后，主动的把缓存队列向前走了一步。
2.连接池：
1.一个Connection封装了一个socket，ConnectionPool中储存s着所有的Connection，StreamAllocation是引用计数的一个单位
2.当一个请求获取一个Connection的时候要传入一个StreamAllocation，Connection中存着一个弱引用的StreamAllocation列表，每当上层应用引用一次Connection，StreamAllocation就会加一个。反之如果上层应用不使用了，就会删除一个。
3.ConnectionPool中会有一个后台任务定时清理StreamAllocation列表为空的Connection。5分钟时间，维持5个socket
3.选择路线与建立连接
1.选择路线有两种方式：
1.无代理，那么在本地使用DNS查找到ip，注意结果是数组，即一个域名有多个IP，这就是自动重连的来源
2.有代理HTTP：设置socket的ip为代理地址的ip，设置socket的端口为代理地址的端口
3.代理好处：HTTP代理会帮你在远程服务器进行DNS查询，可以减少DNS劫持。
2.建立连接
1.连接池中已经存在连接，就从中取出(get)RealConnection，如果没有命中就进入下一步
2.根据选择的路线(Route)，调用Platform.get().connectSocket选择当前平台Runtime下*好的socket库进行握手
3.将建立成功的RealConnection放入(put)连接池缓存
4.如果存在TLS，就根据SSL版本与证书进行安全握手
5.构造HttpStream并维护刚刚的socket连接，管道建立完成
4.职责链模式：缓存、重试、建立连接等功能存在于拦截器中网络请求相关，主要是网络请求优化。网络请求的时候遇到的问题
retrofit的了解

1.动态代理创建一个接口的代理类
2.通过反射解析每个接口的注解、入参构造http请求
3.获取到返回的http请求，使用Adapter解析成需要的返回值。
Xutils, OKhttp, Volley, Retrofit对比

Xutils：
这个框架非常全面，可以进行网络请求，可以进行图片加载处理，可以数据储存，还可以对view进行注解，使用这个框架非常方便，但是缺点也是非常明显的，使用这个项目，会导致项目对这个框架依赖非常的严重，一旦这个框架出现问题，那么对项目来说影响非常大的。

OKhttp：
Android开发中是可以直接使用现成的api进行网络请求的。就是使用HttpClient,HttpUrlConnection进行操作。okhttp针对Java和Android程序，封装的一个高性能的http请求库，支持同步，异步，而且okhttp又封装了线程池，封装了数据转换，封装了参数的使用，错误处理等。API使用起来更加的方便。但是我们在项目中使用的时候仍然需要自己在做一层封装，这样才能使用的更加的顺手。

Volley：
Volley是Google官方出的一套小而巧的异步请求库，该框架封装的扩展性很强，支持HttpClient、HttpUrlConnection， 甚至支持OkHttp，而且Volley里面也封装了ImageLoader，所以如果你愿意你甚至不需要使用图片加载框架，不过这块功能没有一些专门的图片加载框架强大，对于简单的需求可以使用，稍复杂点的需求还是需要用到专门的图片加载框架。Volley也有缺陷，比如不支持post大数据，所以不适合上传文件。不过Volley设计的初衷本身也就是为频繁的、数据量小的网络请求而生。

Retrofit：
Retrofit是Square公司出品的默认基于OkHttp封装的一套RESTful网络请求框架，RESTful是目前流行的一套api设计的风格， 并不是标准。Retrofit的封装可以说是很强大，里面涉及到一堆的设计模式,可以通过注解直接配置请求，可以使用不同的http客户端，虽然默认是用http ，可以使用不同Json Converter 来序列化数据，同时提供对RxJava的支持，使用Retrofit + OkHttp + RxJava + Dagger2 可以说是目前比较潮的一套框架，但是需要有比较高的门槛。

Volley VS OkHttp

Volley的优势在于封装的更好，而使用OkHttp你需要有足够的能力再进行一次封装。而OkHttp的优势在于性能更高，因为 OkHttp基于NIO和Okio ，所以性能上要比 Volley更快。IO 和 NIO这两个都是Java中的概念，如果我从硬盘读取数据，*种方式就是程序一直等，数据读完后才能继续操作这种是*简单的也叫阻塞式IO,还有一种是你读你的,程序接着往下执行，等数据处理完你再来通知我，然后再处理回调。而第二种就是 NIO 的方式，非阻塞式， 所以NIO当然要比IO的性能要好了,而 Okio是 Square 公司基于IO和NIO基础上做的一个更简单、高效处理数据流的一个库。理论上如果Volley和OkHttp对比的话，更倾向于使用 Volley，因为Volley内部同样支持使用OkHttp,这点OkHttp的性能优势就没了， 而且 Volley 本身封装的也更易用，扩展性更好些。

OkHttp VS Retrofit

毫无疑问，Retrofit 默认是基于 OkHttp 而做的封装，这点来说没有可比性，肯定首选 Retrofit。 Volley VS Retrofit 这两个库都做了不错的封装，但Retrofit解耦的更彻底,尤其Retrofit2.0出来，Jake对之前1.0设计不合理的地方做了大量重构， 职责更细分，而且Retrofit默认使用OkHttp,性能上也要比Volley占优势，再有如果你的项目如果采用了RxJava ，那更该使用 Retrofit 。所以这两个库相比，Retrofit更有优势，在能掌握两个框架的前提下该优先使用 Retrofit。但是Retrofit门槛要比Volley稍高些，要理解他的原理，各种用法，想彻底搞明白还是需要花些功夫的，如果你对它一知半解，那还是建议在商业项目使用Volley吧。

Universal-ImageLoader，Picasso，Fresco，Glide对比

Fresco
是Facebook推出的开源图片缓存工具，主要特点包括：两个内存缓存加上 Native 缓存构成了三级缓存

优点：

图片存储在安卓系统的匿名共享内存, 而不是虚拟机的堆内存中, 图片的中间缓冲数据也存放在本地堆内存, 所以, 应用程序有更多的内存使用, 不会因为图片加载而导致oom, 同时也减少垃圾回收器频繁调用回收 Bitmap 导致的界面卡顿, 性能更高。

渐进式加载 JPEG 图片, 支持图片从模糊到清晰加载。

图片可以以任意的中心点显示在 ImageView, 而不仅仅是图片的中心。

JPEG 图片改变大小也是在 native 进行的, 不是在虚拟机的堆内存, 同样减少 OOM。

很好的支持 GIF 图片的显示。

缺点:

框架较大, 影响 Apk 体积
使用较繁琐
Universal-ImageLoader：
（估计由于HttpClient被Google放弃，作者就放弃维护这个框架）

优点：

支持下载进度监听
可以在 View 滚动中暂停图片加载，通过 PauseOnScrollListener 接口可以在 View 滚动中暂停图片加载。
默认实现多种内存缓存算法 这几个图片缓存都可以配置缓存算法，不过 ImageLoader 默认实现了较多缓存算法，如 Size *大先删除、使用*少先删除、*近*少使用、先进先删除、时间*长先删除等。
支持本地缓存文件名规则定义
Picasso

优点

自带统计监控功能。支持图片缓存使用的监控，包括缓存命中率、已使用内存大小、节省的流量等。

支持优先级处理。每次任务调度前会选择优先级高的任务，比如 App 页面中 Banner 的优先级高于 Icon 时就很适用。

支持延迟到图片尺寸计算完成加载

支持飞行模式、并发线程数根据网络类型而变。 手机切换到飞行模式或网络类型变换时会自动调整线程池*大并发数，比如 wifi *大并发为 4，4g 为 3，3g 为 2。 这里 Picasso 根据网络类型来决定*大并发数，而不是 CPU 核数。

“无”本地缓存。无”本地缓存，不是说没有本地缓存，而是 Picasso 自己没有实现，交给了 Square 的另外一个网络库 okhttp 去实现，这样的好处是可以通过请求 Response Header 中的 Cache-Control 及 Expired 控制图片的过期时间。

Glide

优点

不仅仅可以进行图片缓存还可以缓存媒体文件。Glide 不仅是一个图片缓存，它支持 Gif、WebP、缩略图。甚至是 Video，所以更该当做一个媒体缓存。
支持优先级处理。
与 Activity/Fragment 生命周期一致，支持 trimMemory。Glide 对每个 context 都保持一个 RequestManager，通过 FragmentTransaction 保持与 Activity/Fragment 生命周期一致，并且有对应的 trimMemory 接口实现可供调用。
支持 okhttp、Volley。Glide 默认通过 UrlConnection 获取数据，可以配合 okhttp 或是 Volley 使用。实际 ImageLoader、Picasso 也都支持 okhttp、Volley。
内存友好。Glide 的内存缓存有个 active 的设计，从内存缓存中取数据时，不像一般的实现用 get，而是用 remove，再将这个缓存数据放到一个 value 为软引用的 activeResources map 中，并计数引用数，在图片加载完成后进行判断，如果引用计数为空则回收掉。内存缓存更小图片，Glide 以 url、view_width、view_height、屏幕的分辨率等做为联合 key，将处理后的图片缓存在内存缓存中，而不是原始图片以节省大小与 Activity/Fragment 生命周期一致，支持 trimMemory。图片默认使用默认 RGB_565 而不是 ARGB_888，虽然清晰度差些，但图片更小，也可配置到 ARGB_888。
Glide 可以通过 signature 或不使用本地缓存支持 url 过期

本文完~